HashSet 파고들기 - 중복 제거 메커니즘

Java의 HashSet(또는 일반적인 해시 기반 집합 자료구조)이 중복을 제거(= 같은 원소가 두 번 들어오지 않도록)할 수 있는 이유와, 이를 빠르고 효율적으로(평균 O(1)) 수행할 수 있는 원리를 단계별로 작성하였습니다.

---

1. 중복 제거 메커니즘

HashSet의 내부는 사실상 HashMap<Key, DummyValue>와 동일합니다.

• HashSet에 어떤 객체 obj를 추가(add)하면, 내부적으로 HashMap.put(obj, DUMMY_VALUE)가 호출됩니다.
• HashMap에는 Key가 중복될 수 없으므로, 이미 동일한 Key가 존재한다면 새로 삽입되지 않습니다.
• HashSet은 이 “Key”에 해당하는 것이 바로 HashSet에 넣으려는 “원소”가 됩니다.

삽입(add) 과정에서 중복 여부를 검사하는 핵심 로직은 다음과 같습니다:

1. hashCode()로 버킷 위치 확인
   • 먼저 obj.hashCode()를 계산하여, 적절한 해싱 연산을 거쳐 배열(버킷) 인덱스를 결정합니다.
2. 동일 해시 버킷 내 노드 순회
   • 만약 해당 버킷에 이미 다른 원소가 있다면, 연결 리스트 또는 트리 노드를 순회하며 equals()로 비교합니다.
3. equals() 결과
   • 기존에 “equals()가 true”인 원소가 발견되면, 이미 같은 원소가 존재하는 것으로 보고 삽입을 무시합니다.
   • 찾지 못하면(= 중복 없음) 새 노드를 이어붙여 삽입합니다.

결국, 해시 값(=hashCode)과 동등성 판단(=equals)을 통해 중복을 철저히 가려내는 것입니다.

---

2. 효율적인 중복 체크가 가능한 이유

2.1. 해싱 기반의 평균 O(1) 접근

• 버킷 인덱스 계산: hash & (table.length - 1) 등으로 고정 크기 배열의 특정 위치를 순식간에 찾아갑니다.
  평균적으로 충돌이 많지 않다면, 한두 번의 버킷 접근만으로 목표 노드(또는 없음을) 확인할 수 있습니다.

• 충돌(bucket 내 노드가 여러 개) 처리: 버킷 내 원소가 많아지는 경우 연결 리스트를 레드-블랙 트리로 변환하여 최악의 경우도 O(log n)로 성능 보완이 가능합니다.

• 실질적으로 equals() 비교를 대량으로 수행할 상황이 거의 없어(분산이 좋은 해시 함수를 전제로) 평균 O(1)에 가까운 성능이 보장됩니다.

2.2. Load Factor와 리사이징(Resize)

• Load Factor(기본 0.75)를 초과하면, 내부 배열 크기가 2배로 재할당되고 모든 원소를 재해싱(rehash)합니다.
• 이렇게 버킷 크기를 늘리면 충돌이 분산되어, 중복 체크(equals 검사)에도 과도한 비용이 들지 않도록 합니다.

2.3. 해시 코드와 equals의 역할

• hashCode()가 객체를 분산시켜 주는 1차 필터 역할을 하여, 다른 객체는 다른 버킷으로 보내도록 합니다(충돌이 적어짐).
• equals()는 최종적으로 “이 두 객체가 진짜 같은지”를 판별하는 2차 필터 역할을 합니다.
• 즉, 해시 코드가 다르면 대부분 별도의 버킷으로 분산되어 애초에 비교조차 안 하게 되는 점이 큰 이점입니다.

---

3. 요약

• HashSet이 중복을 제거하는 핵심은:
  1. hashCode로 해당 객체가 들어갈 버킷을 찾고
  2. 같은 버킷 내에서 equals로 진짜 같은 객체인지 최종 확인
  3. 이미 있는 객체와 equals가 true면, 추가 삽입을 거부 (중복 불허).
• 평균적으로 버킷 접근이 O(1)이기 때문에, 효율적으로 중복 체크가 가능합니다.
• 내부적으로는 해시 충돌이 많아지지 않도록 Load Factor에 따라 리사이징을 통해 버킷을 늘리고, 연결 리스트가 지나치게 길어지면 트리로 바꿔서 충돌로 인한 탐색 시간을 줄입니다.