[JAVA] 자바의 정석 _ HashSet, TreeSet

 * HashSet - 순서 X, 중복 X

- Set 인터페이스 구현한 대표적인 컬렉션 클래스.

- 순서를 유지하려면, LinkedHashSet 클래스를 사용하면 된다.

1. 생성자 -  HashSet(), HashSet(Collection c), HashSet(int initialCapacity), HashSet(int initialCapacity, float loadFactor)

loadFactor가 0.8 이면 80% 정도 데이터가 차면 Capacity 2배

2. 추가, 삭제 - boolean add (Object o)       :추가

                       boolean remove (Object o) : 삭제

                       boolean addAll (Collection c)       : c와 합집합

                       boolean removeAll (Collection c) : c와 교집합

                       boolean retainAll (Collection c)    : c와 차집합

                       void clear() : 모두 삭제

3. 포함 여부 - boolean contains (Object o) : o가 포함됐는지 확인

                       boolean containsAll (Collection c) : 여러 객체 모두 포함 여부 확인

4. Iterator - Iterator iterator()

5. 기타 - boolean isEmpty() : 비었는지?

              int size() : 저장된 객체 수

              Object[] toArray() : 객체 배열로 반환

- 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인함. 없으면 저장하고 있으면 안 함.

  --> 저장할 객체의 equals()와 hashCode()를 호출해 확인.

따라서 저장할 객체에서 equals()와 hashCode()가 오버라이딩 되어 있어야 함.

//HashSet에 Person 저장하기 전 오버라이딩 하기
class Person{
    String name;
    int age;
    
    Person(String name, int age){
    	this.name = name;
        this.age = age;
    }
    Person(){
    	Person("홍길동", 25)
    }
    public String toString(){
    	return name+":"+age;
    }
    
    public boolean equals(Object obj){ // 오버라이딩 통해 name, age 비교하도록 함
    	if(!(obj instanceof Person)) return false;
        Person tmp = (Person)obj;
        return name.equals(tmp.name) && age == tmp.age;
    }
    
    public int hashCode(){
    	return Objects.hash(name,age);
    }

 

 * TreeSet - 순서 X, 중복 X

- 범위 검색과 정렬에 유리한 컬렉션 클래스

- HashSet보다 데이터 추가 삭제에 시간 더 걸림.

- 이진트리: 최대 2개의 하위 노드를 갖는 노드로 구성됨. (LinkedList의 변형)

class TreeNode{
    TreeNode left;	// 왼쪽 자식노드
    Object element;	// 저장할 객체
    TreeNode right;	// 오른쪽 자식노드
}

- 이진 탐색 트리(binary search tree): 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한 이진트리. TreeSet은 이진 탐색 트리로 구성됨.

 단점 : 데이터가 많아질수록 추가, 삭제에 시간이 걸림.

1. 생성자 - TreeSet(), TreeSet(Collection c), TreeSet(Comparator comp) : comp를 정렬 기준으로 하는 TreeSet 생성

Comparator입력 안 해주면 Comparable을 정렬 기준으로 함. 즉 객체에 Comparable이 구현돼 있어야 함!

2. 추가(데이터 저장) - boolean add(Object O) : 중복 check를 위해 compare()를 호출해 비교.

 - Collection에서 가진 메서드는 동일하니 생략 (add(), size(), remove(), isEmpty(), iterator())

Object first()	정렬된 순서에서 첫 번째 객체 반환
Object last()	정렬된 순서에서 마지막 객체 반환
Object ceiling (Object o)	o와 같은 객체 반환, 같은게 없으면 o보다 큰 값을 가진 객체 중 제일 가까운 값의 객체 반환
Object floor (Object o)	o와 같은 객체 반환, 같은게 없으면 o보다 작은 값을 가진 객체 중 제일 가까운 값의 객체 반환
Object higher (Object o)	o보다 큰 값을 가진 객체 중 o와 가장 가까운 값
Object lower (Object o)	o보다 작은 값을 가진 객체 중 o와 가장 가까운 값
SortedSet subSet (Object fromElement, Object toElement)	from과 to 사리의 결과를 반환. (toElement는 포함 x)
SortedSet headSet (Object toElement)	toElement보다 작은 값의 객체 반환
SortedSet tailSet (Object fromElement)	fromElement보다 큰 값의 객체 반환

이진 탐색 트리이기 때문에 범위 검색에 유리함!

n보다 작은 값을 모두 출력 --> n의 왼쪽 가지 전부.

** 트리 순회(tree traversal)

- 이진트리의 모든 노드를 한 번씩 읽는 것

4 가지 방법이 있음. (전위 순회, 후위 순회, 중위 순회, 레벨 순회)