[인프런 김영한 실전 자바 - 중급편] 컬렉션 프레임워크 - Set

Set

• Set : 중복을 허용하지 않고 순서를 보장하지 않는 자료 구조
  • 수학에서 집합의 특성을 가지고 있다.

---

HashSet

• HashSet의 특징
  
  • 해시 자료 구조를 사용해서 요소를 저장한다.
    • 해시 함수로 각 데이터의 해시 코드를 구한 후 특정 연산을 통해 해시 인덱스를 구해서 저장한다.
  • 요소들은 특정한 순서 없이 저장된다.
  • 주요 연산(추가, 삭제, 검색)은 평균적으로 O(1) 소요된다.
  • 데이터의 유일성만 중요하고 순서가 중요하지 않은 경우에 사용한다.

 

• 해시 기반 자료 구조를 사용하는 경우 통계적으로 입력 데이터 수가 배열 크기의 75%를 넘어서면 해시 충돌이 자주 발생한다.
  • 잦은 해시 충돌로 인해 같은 해시 인덱스에 들어간 데이터를 모두 탐색하며 O(n)으로 성능이 나빠진다.
  • 데이터의 양이 배열 크기의 75%를 넘어서면 배열의 크기를 2배로 늘리고 모든 요소에 다시 해시 인덱스를 적용한다. 이런 과정을 rehashing(재해싱)이라고 한다.

---

 

LinkedHashSet

• LinkedHashSet의 특징
  
  • HashSet에 LinkedList를 추가해서 요소들의 순서를 유지한다.
    • 연결 리스트 형태로 입력한 순서에 맞게 데이터를 노드로 저장을 한 후 데이터를 추가한 순서의 앞, 뒤 노드끼리 서로 연결한다.
  • 요소들은 추가한 순서대로 유지되며 순서대로 조회시 추가 된 순서대로 반환된다.
  • 주요 연산에 대해서 평균적으로 O(1) 소요된다.
  • 데이터의 유일성과 함께 삽입 순서를 유지해야할 때 사용한다.
  • 연결을 통해 순서를 유지해야하므로 HashSet보다는 조금 더 무겁다.
    • 연결은 데이터를 입력한 순서대로 연결되며 양방향 연결이다.

---

TreeSet

• TreeSet의 특징
  
  • 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.
    • 정렬 기준을 기반으로 기준 값보다 작은 수는 좌측에 큰 수는 우측에 정렬한다.
  • 요소들은 정렬된 순서로 저장되며 순서의 기준은 Comparator로 변경할 수 있다.
  • 주요 연산은 평균적으로 O(log n) 소요되며 HashSet보다 느리다.
  • 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야할 때 사용한다.
    • 범위 검색이나 정렬된 데이터가 필요한 경우에 유용하다.

 

• 트리 구조
  
  • 트리는 부모 노드와 자식 노드로 구성된다.
  • 가장 상단에 있는 노드를 루트라고 한다.
  • 자식이 2개까지 올 수 있는 트리를 이진 트리라고 한다.
    • 노드의 왼쪽 자손은 더 작은 값을 가지고 오른쪽 자손은 더 큰 값을 가지는 트리는 이진 탐색 트리다.
  • TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 사용한다.

 

• 이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관하는 것.
• 이진 탐색 트리의 계산의 핵심은 한 번에 절반의 데이터를 날릴 수 있다.
  
  • 해당 수보다 큰지 작은지에 따라 크면 작은쪽은 비교하지 않아도 되고 작다면 큰 쪽은 비교하지 않아도 된다.
• 이진 탐색 트리는 O(log n)의 성능을 가지기에 빠른 성능을 가지고 있다.
  
  • Big O 표기법은 상수를 제거하므로 O(log n)으로 표기가 되며 대부분은 이진 로그인  O(log2n)이다.

 

• 이진 탐색 트리가 한쪽으로 치우치게 된다면 LinkedList와 같은 형태가 되고 O(n)의 성능을 가지게 된다.
  
  • 한쪽으로 치우친 이진 탐색 트리를 개선하기 위해서 트리의 균형이 너무 깨진 경우 동적으로 균형을 다시 맞춘다.
    ex) AVL 트리, 레드-블랙 트리와 같은 균형을 맞추는 알고리즘들이 존재한다.

 

• 이진 탐색 트리 - 순회
  
  • 데이터를 차례로 순회하려면 중위 순회를 사용한다.
    중위 순회 : 왼쪽 서브트리를 방문 -> 현재 노드를 방문 -> 오른쪽 서브 트리를 방문
  • 중위 순회 시 이진 탐색 트리의 특성상 노드를 오름차순(점점 커짐)으로 방문한다.
  • 위에 이진 탐색 트리를 예시로 들면
    10 방문 -> 5 방문 -> 1 출력 -> 5 출력 -> 6 출력 -> 10 출력 -> 15 방문 -> 11 출력 -> 15 출력 -> 16 출력

순회 : 데이터를 순서대로 조회한다는 의미.

 

• TreeSet에서 크다 작다를 비교하는 기준은?
  • TreeSet에서 숫자로 표현할 수 있는 정수형, 문자열 등은 숫자로 변환한 후 크기를 비교해서 정렬한다.
  • 사용자 정의 타입 (Member, Book ...)의 객체는 크다, 작다의 기준을 제공하기 위해서 Comparable, Comparator 인터페이스를 구현해야한다.

 

• iterator() 메소드를 통해 컬렉션을 활용한 루프를 쉽게 사용할 수 있다.
  
  • 데이터를 순서대로 꺼낼 수 있다.
• List.of(배열명)를 통해 배열을 컬렉션으로 변환할 수 있다.

---

출처: [인프런 김영한 실전 자바 - 중급편]

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard

김영한의 실전 자바 - 중급 2편 강의 | 김영한 - 인프런