[3-1] 알고리즘과 자료구조: HashSet

HashSet

내부 동작 방식

HashSet은 해시 테이블을 이용해 데이터를 저장하는 구조로, HashMap을 사용해 데이터를 저장한다. 이를 통해 값이 키가 되는 독특한 구조를 가진다.

중복 제거 매커니즘

HashSet은 두 번의 필터링을 거쳐 순서로 중복을 제거한다.

• 1차 필터링: hasCode() 호출
  • 객체의 해시코드를 계산해 저장할 위치를 결정
  • 해시코드가 다르다면 다른 객체로 간주하고 즉시 저장
• 2차 필터링: 해쉬코드가 같다면 equals() 호출
  • equals() 메소드로 실제 값이 같은지 한번 더 비교
  • equals()까지 true라면 중복으로 판단

효과

HashSet은 전수 조사를 하지 않기 때문에 효율적이다.

• 리스트 vs HashSet의 중복 제거 매커니즘 시간 복잡도
  
  • 리스트: O(n), 모든 데이터와 하나씩 대조해야 함
  • HashSet: O(1), 해시 함수를 통해 데이터가 있어야 할 위치를 바로 계산

일반적인 리스트에서 중복을 찾으려면 모든 데이터와 하나씩 대조해야 하기 때문에 O(n)의 시간 복잡도를 가진다. 반면, HashSet은 해시 함수를 통해 데이터가 있어야 할 위치를 바로 계산하여 O(1)의 시간 복잡도를 가진다.

 

정리

결과적으로 HashSet은 해싱(Hashing)을 기술을 통해 데이터의 고유성을 보장하는 효과적인 방법을 제시한다. 무작위로 늘어선 데이터 사이를 헤매는 대신, 수학적 계산을 통해 데이터의 주소를 즉시 찾아가는 방식은 대규모 시스템에서 중복 체크 비용을 획기적으로 낮춰준다. 따라서 데이터의 순서보다 중복 방지와 탐색 속도가 최우선인 시나리오라면, HashSet은 개발자가 선택할 수 있는 가장 효율적인 도구가 될 수 있다.