java -HashSet

🔹 HashSet 클래스

• Set 인터페이스를 구현한 클래스 중 하나로, 중복을 허용하지 않는 데이터 집합을 관리하는 컬렉션
• HashMap을 기반으로 동작
• 요소의 순서를 보장하지 않음
• 해싱을 사용하여 효율적인 데이터 저장과 검색이 가능
• null 저장 가능

🔹 TreeSet 클래스

• Set 인터페이스를 구현한 클래스 중 하나로, 중복을 허용하지 않고 요소를 자동 정렬하는 Set 컬렉션
• TreeMap 기반으로 동작
• 이진 탐색 트리 (Binary Search Tree) 의 일종인 Red-Black Tree 구조를 사용
• 검색 및 조회 성능: O(log n)
• Comparator를 사용하면 커스텀 정렬 가능

🔹 LinkedHashSet 클래스

• Set 인터페이스를 구현한 클래스 중 하나로, 중복을 허용하지 않고 요소의 삽입 순서를 유지
• Set의 속성을 유지하면서 순서를 보장하고 싶을 때 사용
• TreeSet처럼 정렬 기능은 없음

---

🔧 HashSet 내부 구조

• 내부적으로 HashMap<K, V>를 사용하여 요소 저장
• 중복을 허용하지 않고, 요소의 순서를 보장하지 않음
• 요소를 추가할 때:
  1. hashCode()를 사용하여 저장 위치 결정
  2. equals()로 중복 여부 확인

---

⚙️ HashSet 내부 동작 과정

✅ Step 1: hashCode()로 해시 버킷(bucket) 위치 결정

• HashSet은 hashCode()를 이용해 요소를 저장할 해시 버킷을 결정
• 배열 기반과 연결 리스트로 구성
• 예: 배열 길이가 5라면 hashCode() % 5로 저장 위치 계산

✅ Step 2: 해시 충돌(Collision) 여부 확인

• 동일한 해시값을 가진 요소가 이미 존재하는 경우 충돌 발생
• Java 7 이하: LinkedList 사용해 같은 버킷 내 요소 연결
• Java 8 이상: 일정 개수를 초과하면 Red-Black Tree로 변환 → 성능 최적화

✅ Step 3: equals() 비교 후 저장

• 같은 해시 버킷에 여러 요소가 존재할 수 있음
• equals()로 동일 객체 확인
  • 동일하면 중복으로 간주, 추가하지 않음
  • 다르면 새로 추가

✅ Step 4: 저장 완료

• HashSet은 내부적으로 HashMap을 사용하므로
• add(E e) 호출 시 → 내부적으로 put() 호출됨

---

🔍 HashSet에서 요소 검색

1. hashCode()를 이용해 저장된 버킷 탐색
2. 해당 버킷 내에서 equals()로 대상 요소 비교
3. 일치하면 true, 아니면 false 반환

⏱️ 검색 시간 복잡도

• 최선: O(1) → 해시 충돌이 적을 경우
• 최악: O(n) → 모든 요소가 동일한 해시값을 가질 경우

---

❌ HashSet에서 요소 삭제

1. hashCode()를 이용해 저장된 버킷 탐색
2. 해당 버킷 내에서 equals()로 대상 요소 확인
3. 존재하면 삭제 후 연결 관계 정리하여 컬렉션 유지