[Java] HashSet, TreeSet

2019. 7. 24. 23:56

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

HashSet

HashSet 은 Set 인터페이스를 구현한 가장 대표적인 컬렉션이며 Set 인터페이스의 특징대로 중복된 요소를 저장하지 않는다. HashSet 에 이미 저장된 요소와 중복된 요소를 추가하고자 하면 false 를 반환함으로써 추가에 실패했다는 것을 알린다. (이러한 HashSet 의 특징을 이용하면 컬렉션 내의 중복 요소들을 쉽게 제거할 수 있다.) 또한 저장 순서를 유지하지 않으므로 저장 순서를 유지하고자 한다면 LinkedHashSet 을 사용해야 한다.

HashSet의 메서드

생성자 or 메서드	설 명
HashSet( )	HashSet 객체를 생성
HashSet(Collection c)	주어진 컬렉션을 포함하는 HashSet 객체 생성
HashSet(int initialCapacity)	주어진 값을 초기용량으로 하는 HashSet 객체를 생성
HashSet(int initialCapacity, float loadFactor)	초기용량( initialCapacity )과 load factor( loadFactor )를 지정하는 생성자 load factor는 컬렉션 클래스에 저장공간이 가득 차기전에 미리 용량을 확보하기 위한 것으로 이 값을 0.8로 지정하면, 저장공간의 80%가 채워졌을때 저장공간이 두배로 늘어난다. default는 0.75
boolean add(Object o)	새로운 객체를 저장
boolean addAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 추가
void clear( )	저장된 모든 객체를 삭제
Object clone( )	HashSet 을 복제해서 반환(얕은 복사)
boolean contains(Object o)	지정된 객체를 포함하고 있는지 알려줌
boolean containsAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 포함하고 있는지 알려줌
boolean isEmpty( )	HashSet 이 비어있는지 알려줌
Iterator iterator( )	Iterator 를 반환
boolean remove(Object o)	지정된 객체를 HashSet 에서 삭제 성공하면 true, 실패하면 false
boolean removeAll(Collection c)	주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 Hashset 에서 모두 삭제
boolean retainAll(Collection c)	주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제
int size( )	저장된 객체의 개수를 반환
Object[ ] toArray( )	저장된 객체들을 객체배열의 형태로 반환
Object[ ] toArray(Object[ ] a)	저장된 객체들을 주어진 객체배열( a )에 담는다.

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		Object[] objArr = {"1", new Integer(1), "3", "3", "2", "2", "4", "4", "4", "4", };
		Set set = new HashSet();
		
		for(int i = 0 ; i < objArr.length ; i++) {
			set.add(objArr[i]);	//HashSet에 objArr의 요소들을 저장
		}
		
		//HashSet에 저장된 요소들을 출력
		System.out.println(set);
	}
}

HashSet 의 특징을 확인하는 간단한 예제이다. 결과를 보면 중복된 값은 저장되지 않는다는 것을 확인할 수 있다. add( ) 는 객체를 추가할 때 HashSet 에 이미 같은 객체가 있으면 중복으로 간주하고 저장하지 않는다. 그리고 작업이 실패했다는 의미로 false 를 반환한다. 실행결과에서 1 이 2개 있는데 하나는 String 인스턴스이고 하나는 Integer 인스턴스로 서로 다른 객체라서 중복으로 간주하지 않는다. 그리고 Set 을 구현한 컬렉션 클래스는 List 를 구현한 컬렉션 클래스와 달리 순서를 유지하지 않기 때문에 저장한 순서와 다를 수 있다.

■ 중복 제거

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		HashSet set = new HashSet();
		
		set.add("abc");
		set.add("abc");
		set.add(new Person("David", 10));
		set.add(new Person("David", 10));
		
		System.out.println(set);
	}
}

class Person{
	String name;
	int age;
	
	Person(String name, int age){
		this.name = name;
		this.age = age;
	}
	
	/*
	//add()가 호출하는 equals( )를 오버라이딩 해야함.
	public boolean equals(Object obj) {
		if(obj instanceof Person) {
			Person tmp = (Person)obj;
			return name.equals(tmp.name) && (age == tmp.age);
		}
		
		return false;
	}
	
	//add()가 호출하는 haschCode( )도 오버라이딩 해야한다.
		public int hashCode() {
			return Objects.hash(name, age);	//return(name + age).hashCode();도 가능하긴 함
		}
	*/
	
	public String toString() {
		return name + " : " + age;
	}
	
}

HashSet 은 각각의 값이 같음에도 서로 다른 인스턴스인 경우에 다른 값으로 인식해서 추가가 되는 경우가 있다. 이때 각각의 인스턴스를 다른 것으로 인식하게 하려면 추가적인 처리를 해주어야 한다. HashSet 의 add 메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 요소의 equals( ) 와 hashCode( ) 를 호출한다. 따라서 이 두 함수를 목적에 맞게 오버라이딩 해서 쓰면 된다. 위의 코드에서는 주석 부분을 풀면 중복이 제외된 결과가 출력된다.

hashCode( ) 를 오버라이딩할 때 만족시켜야 하는 조건

( equals 메서드의 구현에 사용된 멤버변수의 값이 바뀌지 않는다고 가정할 때) 실행중인 애플리케이션의 동일한 객체에 대해서 여러번 hashCode( ) 를 호출해도 동일한 int 값을 반환해야한다.(실행시마다 동일한 int 값을 반환할 필요는 X)
: String 클래스는 문자열의 내용으로 해시코드를 만들어 내기 때문에 같은 문자열에 대한 hashCode( ) 는 항상 동일한 해시코드를 반환한다. 반면 Object 클래스는 객체의 주소로 해시코드를 만들어 내기 때문에 실행할 때마다 해시코드가 달라질 수 있다.
equals 메서드를 이용한 비교에 의해서 true 를 얻은 두 객체에 대해 각각 hashCode( ) 를 호출한 결과는 반드시 같아야한다.
equals 메서드를 호출했을 때 false 를 반환하는 두 객체는 hashCode( ) 호출에 대해 같은 int 을 반환하는 경우가 있어도 괜찮지만, 해싱(hashing)을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int 값을 반환하는것이 좋다.
: 서로다른 객체에 대해서 해시코드값이 중복되는 경우가 많아질수록 해싱을 사용하는 Hashtable , HashMap 과 같은 컬렉션의 검색속도가 떨어진다.

TreeSet

TreeSet 은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리는 정렬, 검색, 범위 검색(range search)에 높은 성능을 보이는 자료구조이며 TreeSet 은 이진트리의 성능을 향상시킨 '레드-블랙 트리(Red - Black tree)'로 구현되어 있다. 그리고 Set 인터페이스를 구현한 것이라서 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장 순서를 유지하지도 않는다.

이진트리(binary tree)는 링크드 리스트처럼 여러 개의 노드(node)가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 루트(root)라고 불리는 하나의 노드에서 시작해서 확장해 나갈 수 있다. 위아래로 연결된 노드를 부모 - 자식관계 에 있다고 하며 위의 노드를 부모노드 , 아랫부분을 자식노드 라고 한다. 부모 - 자식관계 는 상대적이며 하나의 부모 노드는 최대 2개의 자식 노드와 연결될 수 있다. 예를 들어 A 는 B 와 C 의 부모 노드이고, B 와 C 는 A 의 자식 노드가 된다.

class TreeNode{
    TreeNode left;	//왼쪽 자식노드(참조변수)
    Object element;	//객체를 저장하기 위한 참조변수
    TreeNode right;	//오른쪽 자식노드(참조변수)
}

이진트리의 코드는 위와 같이 데이터를 저장하기 위한 Object 타입의 참조 변수 하나와 양쪽의 노드를 참조하기 위한 2개의 참조 변수가 선언되어 있다. 이진 검색 트리(binary search tree)는 부모 노드의 왼쪽에는 부모 노드의 값보다 작은 값의 자식 노드를, 오른쪽에는 큰 값의 자식 노드를 저장하는 이진트리이다.

이진 검색 트리(binary search tree)

모든 노드는 최대 2개의 자식노드를 가질 수 있다.
부모노드를 기준으로 왼쪽 자식노드의 값은 부모노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모노드의 값보다 커야한다.
순차적으로 저장하지 않으므로 노드의 추가/삭제에 시간이 걸린다.
검색(범위검색)과 정렬에 유리하다.
중복된 값을 저장하지 못한다.

만약 이진 검색 트리에 7 , 4 , 9 , 1 , 5 순서대로 값을 저장하면 위의 그림과 같은 순서대로 진행된다. 첫 번째로 저장되는 값은 루트가 되고 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 자식 노드가 없을 경우 기준이 되는 값(초록색) 보다 작은 값은 왼쪽 노드(파란색), 큰 값은 오른쪽 노드(빨간색)에 배치된다. 이런 식으로 값을 채워나가면 최종 트리에서 왼쪽 마지막 레벨이 제일 작은 값( 1 )이 되고, 오른쪽 마지막 레벨의 값이 가장 큰 값( 9 )이 된다. 위의 예시는 숫자라서 쉽게 비교할 수 있지만 객체 간의 비교 시에는 비교 기준이 필요하다. TreeSet 에 저장되는 객체가 Comparable 을 구현하던가 Comparator 를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면 TreeSet 에 객체를 저장할 때 예외가 발생한다.

왼쪽 마지막 값부터 오른쪽 값까지의 값을 왼쪽노드 → 부모노드 → 오른쪽노드 순으로 읽어오면 오름차순으로 된 정렬방법을 얻을 수 있다. TreeSet 은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위 검색(range search)이 매우 빠르다. 저장된 값의 개수에 비례해서 검색시간이 증가하긴 하지만 값의 개수가 10배 증가해도 값을 찾기 위한 비교 횟수가 3~4번만 증가할 정도로 검색효율이 뛰어난 자료구조이다. 하지만 트리는 데이터를 순차적으로 저장하는 것이 아니라 저장 위치를 찾아서 저장해야 하고, 삭제하는 경우 트리의 일부를 재구성해야 하므로 Linked List 보다 데이터의 추가/삭제 시간이 더 오래 걸린다. 대신 배열이나 Linked List 에비해 검색과 정렬 기능이 더 뛰어나다.

TreeSet의 생성자와 메서드

생성자 or 메서드	설 명
TreeSet( )	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet 을 생성
TreeSet(Comparator comp)	주어진 정렬조건으로 정렬하는 TreeSet 을 생성
TreeSet(SortedSet s)	주어진 SortedSet 을 구현한 컬렉션을 저장하는 TreeSet 을 생성
boolean add(Object o) boolean addAll(Collection c)	지정된 객체( o ) 또는 Collection(c) 의 객체들을 Collectioin 에 추가
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
void clear( )	저장된 모든 객체 삭제
Object clone( )	TreeSet 을 복제하여 반환
Comparator comparator( )	TreeSet 의 정렬기준( Comparator )를 반환
boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체( o )또는 Collection 의 객체들이 포함되어 있는지 확인
NavigableSet descendingSet( )	TreeSet 에 저장된 요소들을 역순정렬해서 반환
Object first( )	정렬된 순서에서 첫번째 객체를 반환
Object floor(Object o)	지정된 객체와 같은 객체를 반환 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환
NavigableSet headSet(Object toElement, boolean inclusive)	지정된 객체보다 작은 값의 객체들을 반환 inclusive가 true이면 같은 값의 객체도 포함
Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
boolean isEmpty( )	TreeSet 이 비어있는지 확인
Iterator iterator( )	TreeSet 의 Iterator 를 반환
Object lase( )	정렬된 순서에서 마지막 객체를 반환
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체중 제일 가까운 값의 객체를 반환, 없으면 null
Object pollFirst( )	TreeSet 의 첫번째 요소(제일 작은 값의 객체)반환
Object pollLast( )	TreeSet 의 마지막번째 요소(제일 큰 값의 객체)를 반환
boolean remove(Object o)	지정된 객체 삭제
boolean retainAll(Collection c)	주어진 컬렉션과 공통된 요소만을 남기고 삭제
int size( )	저장된 객체의 개수를 반환
Spliterator spliterator( )	TreeSet 의 spliterator 를 반환
SortedSet subSet(Object fromElement, Object toElement)	범위검색( fromElement 와 toElement 사이)의 결과를 반환 ( toElement 는 범위에 포함되지 X)
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	범위검색( fromElement 와 toElement 사이)의 결과를 반환 (fromInclusive가 true면 시작값이 포함되고, toInclusive가 true면 끝 값이 포함된다.)
SortedSet tailSet(Objecct fromElement)	지정된 객체보다 큰 값의 객체들을 반환
Object[ ] toArray( )	지정된 객체를 객체배열로 반환
Object[ ] toArray(Object[ ] a)	저장된 객체를 주어진 객체배열에 저장하여 반환

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		
		String from = "b";
		String to = "d";
		
		set.add("abc");
		set.add("alien");
		set.add("bat");
		set.add("car");
		set.add("Car");
		set.add("disc");
		set.add("dance");
		set.add("dZZZZ");
		set.add("dzzz");
		set.add("elephant");
		set.add("elevator");
		set.add("fan");
		set.add("flower");
		
		System.out.println(set);
		System.out.println("range search : from " + from + " to " + to);
		System.out.println("result1 : " + set.subSet(from, to));
		System.out.println("result 2 : " + set.subSet(from, to + "zzz")); //dzzz보다 앞에있는 단어 -> d로시작하는 모든단어
	}
}

TreeSet 의 문자열 정렬 방식을 확인하는 예제이다. 소문자보다 대문자를 우선시하기 때문에 Car 가 abc 앞에 있고, dZZZZ 가 dzzz 보다 앞에 있는 것을 확인할 수 있다. 이처럼 대소문자가 섞여있는 경우에는 의도한 것과 다른 범위 검색 결과를 얻을 수 있다. 그래서 가능하면 대문자나 소문자 중 하나로 통일해서 저장하는 것이 좋다.(섞여있어야 하는 경우에는 Comparator 를 사용해야 함)

subSet 은 끝 범위를 포함하지 않지만 만약 위의 예제처럼 d 로 시작하는 단어까지 포함시키고 싶다면 해당 문자열 + "zzz" 하면 된다. dzzz 보다 뒤에 오는 단어는 없기 때문에 d 시작하는 모든 단어들이 오게 된다.

문자열의 정렬순서 (문자의 코드값이 기준)

오름차순일 경우 : 공백 → 숫자 → 대문자 → 소문자
내림차순일 경우 : 공백 ← 숫자 ← 대문자 ← 소문자

저작자표시 비영리 변경금지

'Back end > Java' 카테고리의 다른 글

[Java] 해싱(hashing)과 해시함수(hash function) (0)	2019.07.25
[Java] HashMap과 Hashtable, TreeMap (0)	2019.07.25
[Java] Iterator, Arrays, Comparator (0)	2019.07.23
[Java] 스택(Stack)과 큐(Queue) (1)	2019.07.22
[Java] 연결리스트(Linked List)와 이중 연결리스트(Doubly linked list), 이중 원형 연결리스트(Doubly circular linked list) (0)	2019.07.19

pridiot