ch 11-37,38 HashSet(2/2)

HashSet - 예제

• HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인 같은 객체가 없으면 저장하고, 있으면 저장하지 않는다. (set은 순서가 없고 중복이 존재하지 않기 때문에)
• boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출, equals()와 hashCode()가 오버라이딩 되어 있어야 함
  
  
• 원래는 String + int = String 형식으로 만들어야 하지만, return Objects.hash(String, int)로 만들 수 있다.

ch 11-39~41 TreeSet(1/2)

TreeSet - 범위 탐색, 정렬

• 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리.
• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)(0개~2개)
  
• B와 C의 부모는 A

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

LinkedList의 구조
class Node {
	Node next;	// 다음 요소의 주소를 저장
    Object obj; // 데이터를 저장
}

• LinkedList는 한개의 요소만 가르키게 되는데, TreeNode는 두개의 요소를 가르키게 된다.

이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽 큰 값은 오른쪽에 저장
  
  
• 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

TreeSet - 데이터 저장과정 boolean add(Object o)

• HashSet은 equals(), hashCode()로 비교 / TreeSet은 compare()를 호출해서 비교
• TreeSet에 7,4,9,1,5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.
  (루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장)