[Java] HashSet

1. HashSet이란?

• Set 인터페이스를 구현한 컬렉션으로, 중복을 허용하지 않는다.
• 내부적으로 HashMap을 사용하여 데이터를 저장한다.
• 해시 충돌(Hash Collision)이 거의 없다면 매우 빠른 성능을 낸다.
  • 평균적으로 add, remove, contains 연산이 O(1).
• 해시 충돌이 많이 발생하면 동일 버킷에 값들이 모이므로
  • 최악의 경우 O(n)까지 성능이 떨어질 수 있다.

---

2. Hash Table 동작원리

1. Key(키)가 입력된다.
2. Hash 함수가 Key를 정수(Hash Code)로 변환한다.
3. 변환된 정수를 Hash Table의 크기(Table의 row 수)로 나눈 나머지를 구한다. → index
   • index = hashCode % tableSize
4. 이 index를 이용해 해당 버킷(bucket)에 데이터를 저장한다.
5. 만약 동일한 index에 이미 데이터가 있다면 (Collision 발생):
   • 보통 "체이닝(LinkedList)" 또는 "오픈 어드레싱"으로 해결한다.

Hash Table 예시 그림

https://www.geeksforgeeks.org/dsa/implementation-of-hash-table-in-python-using-separate-chaining/

 

https://www.geeksforgeeks.org/dsa/implementation-of-hash-table-in-python-using-separate-chaining/

 

---

3. Hash Table이 중복체크에 효율적인 이유

Hash Table은 Key를 해시 함수로 계산한 위치만 확인하면 되기 때문에
전체 탐색 필요 없으며 평균 O(1) 시간에 중복 여부를 판단할 수 있다.