HashSet & TreeSet

HashSet

• Set 인터페이스를 구현한 대표적인 컬렉션 클래스 : 순서 X, 중복 X

• 순서를 유지하고 싶으면, LinkedHashSet class를 사용.

• 객체를 저장하기 전에, 기존에 같은 객체가 있는지 확인한다.
  -> 같은 객체가 없으면 저장, 있으면 저장하지 않음.
  

• boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출하여 중복 여부를 확인한다.
  -> 우리가 만든 class는 반드시 equals()와 hashCode()가 오버라이딩 되어 있어야 한다.
  -> equals()는 iv간 비교하도록 작성
  -> hashCode()는 Objects.hash()를 이용하여 작성

// ex
public boolean equals(Object obj) {
	if (!(obj instanceof Person)) return false;
    
    // Person 클래스의 iv를 사용하기 위해, obj 형변환
    Person tmp = (Person) obj;
    
    // this와 obj 비교
    return name.equals(tmp.name) && age == tmp.age;
}

public int hashCode() {
	return (name + age).hashCode();	// String 클래스의 해쉬코드 호출
    
    // 요즘엔 이렇게 작성한다.
    return Objects.hash(name, age);
   
}

TreeSet

• 범위 검색(이진 탐색)과 정렬에 유리한 컬렉션 클래스

• Data가 많을수록, HashSet보다 데이터 추가/삭제에 더 많은 시간이 소요 됨. (비교 횟수 증가로 인해)

• 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리함.

• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖는다. (0개, 1개, 2개)

• 각 요소(node)가 나무 형태로 연결 됨. (LinkedList의 변형)

class TreeNode {
	TreeNode left;
    Object element;
    TreeNode right;
}

• 이진 탐색 트리 : 부모 Node보다 작은 값은 왼쪽 Node에, 큰 값은 오른쪽 Node에 저장.

• 데이터 저장 : boolean add(Object o)
  add 메서드 내에서, equals(), hashCode()를 호출한다. (중복을 허용하지 않기 때문)
  순서대로 비교해가며 저장한다.
  

• TreeSet() 은 비교 기준이 반드시 필요하다.
  객체가 Comparable을 갖고 있던가,
  TreeSet()에 비교 기준을 넘겨주어야 함.
  

• 이진 트리의 모든 노드들을 한 번씩 읽는 것 -> "트리 순회(Tree traversal)" 이라고 함

  전위 순회 : preorder. 부모를 먼저 읽고, 자식들을 읽음.

  후위 순회 : postorder. 자식들을 먼저 읽고, 부모를 마지막에 읽음.

  중위 순회 : inorder. 부모 기준 왼쪽부터 읽고, 부모를 읽은 후, 오른쪽을 읽음.

  레벨 순회 : 한 층씩, 왼쪽부터 순서대로 읽음.

  -> 중위 순회로 읽을 시, 오름차순으로 정렬 된 결과가 나온다.