[java] HashSet 과 TreeSet

<HashSet>

주요 메서드	설명
boolean add(Object c)	새로운 객체 저장
boolean addAll(Collection c )	컬렉션에 저장된 모든 객체들을 저장한다.
Iterator iterator()	Iterator 반환
boolean contains (Object c )	지정된 객체를 포함하는지 알려준다.
int size()	객체의 개수를 반환한다
boolean remove (Object c)	주어진 객체를 삭제한다.
boolean removeAll(Collection c)	주어진 컬렉션과 동일한 것을 모두 삭제한다. (차집합)
boolean retainAll(Collection c)	주어진 컬렉션과 동일한 것만 남기고 삭제한다. (교집합)

set 인터페이스를 구현한 클래스로 중복값을 저장하지 않고, 저장순서도 유지하지 않는다.

HashSet은 저장하는 객체의 equals() 와 hashCode( )를 호출하고, 이를통해 동일한 객체가 저장되어 있는지 확인한다.

만약 사용자가 정의한 클래스를 HashSet에 저장할때는 equals( ) 와 hashCode( )를 적절히 오버라이딩해야한다.

우리가 자주사용하는 String , Integer 클래스에는 이미 오버라이딩 되어있다.

오버라이딩 시에는 다음 세가지 원칙을 지켜야한다.

 

1. 실행중인 애플리케이션 내에서는 hashCode( )를 호출해도 동일한 int값을 반환해야한다. (다음 실행때는 바뀔 수 있음)

2. equals( ) 메서드가 true 라면, hashCode( )의 결과도 반드시 같아야 한다. (필수조건)

3. equals( ) 메서드가 false 라면 hashCode( ) 의 결과는 다른것이 좋다.  (필수는 아님)

  - 해시코드값이 중복될수록 , 검색속도가 떨어진다.

 

 

 

<TreeSet>

주요 메서드	설명
boolean add(Object o) boolean addAll(Collection c )	새로운 객체(o) 또는 컬렉션(c) 저장
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Comparator comparator( )	TreeSet의 정렬기준을 반환
void clear( )	저장된 모든 객체 삭제
boolean contains (Object c )	지정된 객체를 포함하는지 알려준다.
Iterator iterator( )	Iterator 호출
SortedSet subset (Object  frontElement , Object toElement)	범위검색 (front 와 toElement 사이) 의 결과를 반환
SortedSet tailSet (Object fromElement)	fromElement 보다 큰 값 반환

TreeSet 역시 Set 인터페이스를 구현하였으므로 중복값 저장되지 않고 순서도 유지되지 않는다.

TreeSet은 이진 검색 트리 (binary search tree)를 사용하여 값을 정렬하여 저장한다.

- 모든 노드는 최대 2개의 자식 노드를 가진다

- 왼쪽 자식은 부모노드보다 작고 오른쪽 자식은 부모노드보다 크다

 

이때문에 TreeSet은 값의 추가/수정이 느리다. (리스트에 비해)

하지만 검색과 정렬기능이 뛰어나다.