> 2024.03.03일자 위클리 페이퍼

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

Set의 특징

1. 종복되지 않는 요소를 저장한다.

2. 순서를 보장하지 않는 경우가 많다.

이러한 HashSet은 Set의 특징을 그대로 상속받아 사용된다.

HashSet의 특징

1. 해시를 이용하여 내부적으로 요소를 저장한다.

2. 중복 여부를 판단할 때 hashCode()와 equals()메서드를 사용한다.

1. HashSet의 내부 동작 방식

1.1 요소의 저장

• HashSet에 저장되는 요소는 내부적으로 HashMap의 key로 저장된다.

• HashMap의 value는 고정된 더미 객체가 들어간다. 즉, HashSet은 오직 key값 만을 활용하고
  value는 사용되지 않는 객체로 처리한다.

1.2 조회 과정

• 요소가 HashSet에 포함되어 있는지 조회할 때도 내부적으로 HashMap의 key를 기준으로 요소를 찾게 된다.

1.3 삭제 과정

• 삭제 역시 HashMap에서 해당 key를 제거하는 방식으로 수행된다.

HashSet은 내부적으로 HashMap을 사용하여 구현된다. HashSet의 각 요소는 HashMap의 키로 저장되며, HashMap의 값 자리에는 고정 된 더미 객체가 들어간다. HashMap은 키의 중복을 허용하지 않는 자료구조이기에 자연스럽게 HashSet또한 중복을 허용하지 않게 된다.

2. HashSet의 중복 제거 매커니즘

2.1 중복 제거의 핵심 원리

HashSet은 hashCode(),equals()를 사용하여 중복을 판단한다.

hashCode(): 객체의 해시 코드를 계산하여 저장 위치(버킷)를 결정한다.

equals(): 해시 코드가 같은 경우, 실제로 두 객체가 동일한지 비교한다.
이 두 메서드를 적절히 활용하여 HashSet은 중복을 판단하고, 중복된 요소는 저장하지 않는다.

2.2 중복 제거 과정

HashSet에 새로운 요소를 추가할 때, 다음과 같은 단계로 중복을 체크한다.

1) hashCode()를 통한 버킷 결정

• 새로운 요소를 추가할 때, 먼저 해당 요소의 hashCode() 메서드를 호출하여 해시 값을 계산한다.

• 이 해시 값을 기반으로 HashMap의 버킷을 결정한다.

• 해시 값은 HashMap의 내부 배열 인덱스로 사용된다.

2) 버킷 내 요소 비교

• 결정된 버킷에 이미 다른 요소가 있는지 확인한다.

• 버킷이 비어 있다면, 새로운 요소를 해당 버킷에 추가한다.

• 버킷에 이미 요소가 있다면, 해시 충돌이 발생한 것으로 인지하고 다음 단계로 넘어간다.

3) equals()를 통한 중복 확인

• 버킷에 이미 존재하는 요소들과 새로운 요소를 equals() 메서드로 비교한다.

• equals()가 true를 반환하면, 두 요소는 동일한 것으로 판단하고 중복을 허용하지 않는다.

• equals()가 false를 반환하면, 두 요소는 다른것으로 판단하고 버킷에 새로운 요소를 추가한다.

마지막으로, HashSet의 중복 제거가 효율적인 이유 :

• 해시 테이블 해시 값을 통해 직접 버킷을 찾기 때문에 평균적으로 O(1)의 시간 복잡도로 요소를 검색할 수 있다.
• hashCode()를 통해 버킷을 빠르게 찾고, equals()를 통해 정확한 중복 여부를 확인하기 때문에 두개를 적절히 사용하면 효율적으로 중복체크가 이뤄진다.