[Java] HashSet의 내부 동작 방식과 중복 제거 메커니즘

WeeklyPaper 주제:  HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.

 

내부 동작 방식

Java의 HashSet은 놀랍게도 HashMap으로 구성이 되어 있다. 

• HashSet을 만들어서 데이터를 추가하고 싶을 때, HashMap의 put메서드를 사용한다 - map.put(element, PRESENT)
  • element = 추가하고 싶은 데이터 (key로 저장됨)
  • PRESENT = HashSet 내부에서 사용하는 고정된 dummy value
    • private static final Object PRESENT = new Object();
• 즉, 실제로 HashMap의 key만 사용하는 구조이다 -> HashSet은 사실상 key만 사용하는 HashMap이라고 생각할 수 있다.

중복 제거 메커니즘

HashSet은 데이터를 추가할 때 hashCode() -> equals() 순서로 비교를 한다:

1. 객체의 hashCode()를 호출해서 해시값을 계산 (element.hashCode()) 
2. 해당 해시값을 기반으로 해당 객체가 저장될 버킷(bucket) 을 찾음 (인덱스 역할)
   
   • 버킷은 hash table에서 데이터를 저장하는 공간/슬롯의 개념.
   • 1번 처럼, hash table에서는 데이터를 저장할 때 각 데이터를 어디에 저장할지 결정하기 위해서는 해시 함수를 사용함
3. 버킷 안에 같은 hashCode를 가진 객체가 있다면 그 항목들과 equals() 메서드를 사용해 내용이 동일한지 비교함
   • equals() 결과가 true (해시값 + 내용 같음) - 중복으로 판단하고 추가하지 않음
   • equals() 결과가 false (해시값 같음, 내용 다름) - 충돌 처리 후 추가함 (체이닝 등)
4. hashCode를 가진 객체가 없다면, HashSet은 별다른 충돌 처리 없이 해당 버킷에 바로 추가함

왜 HashSet이 빠를까?

해시 기반 구조의 핵심은, 값을 일일이 비료하지 않고, 해시값으로 위치를 바로 찾아내기 때문이다.

얘를 들면 ArrayList로 비교해보면:

ArrayList.contains() // O(n) - 모든 원소를 비교해야함
HashSet.contains() // O(1) - 바로 해시값 계산하고 버킷으로 이동해 equals() 확인함

 

즉, 해시값 계산 + equals() 한두 번 비교가 끝이기 때문에 탐색 속도가 매우 빠르다 (O(1)).