Java로 자료구조 이해하기 4편(Set)

Set

• Collection interface의 구현체이다.

HashSet

---

특징

• 순서가 없다.
• 중복이 안된다.
  • 즉, 같은 객체가 없으면 저장하고
• 로또 생성기 같은거 만들 때 유용
• Hash를 기반으로 하기 때문에 equals()와 hashCode()를 같이 오버라이딩 해주어야 한다.
  • 참고(hasCode와 toString)

HashSet

• Set 인터페이스를 구현한 컬렉션 클래스
• 순서를 유지하려면 LinkedHashSet 사용

TreeSet

---

• 이진 탐색 트리(binary ssearch tree)로 구현. 범위 탐색과 정렬에 유리
• HashSet보다 데이터 추가 및 삭제는 느리다.
• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖는다.
  • binary라는 뜻이 2개라는 의미이므로 그렇다.

이진 탐색 트리

그림

• 부모 보다 작은 값은 왼쪽, 큰 값은 오른쪽으에 저장한다.
• 데이터의 추가 삭제가 느린 이유는 처음 부터 끝까지 왼쪽, 오른쪽을 모두 찾아가며 비교해야 하기 때문에 느리다.