HashSet은 왜 HashMap으로 만들었을까?

우선, set에 대해 알아야 하는 이유를 생각해 보자.

인터뷰에서 Set은 항상 등장하는 질문 중 하나이다.

단순히 “중복 가능 여부”에 대한 특징을 알고 있는지를 확인하기 위함은 아닐 것이다.

실무에서 자주 쓰는 Set이라는 자료구조를 왜 선택해야 하는지 이해하고 있는지를 확인하려는 질문이라고 생각한다.

 

특히 List, Map 등 다양한 자료구조 중 Set은 내부적으로 HashMap 기반으로 동작하기 때문에,

구조를 이해하고 있는지 보면 깊이가 바로 보이는 질문 중 하나라고 생각한다. 

 

HashMap의 특성상

1. 중복을 허용하지 않고 2. 순서가 없으며 3. 조회는 평균적으로 O(1)에 가깝다.

 

그래서 대량 데이터에서 “존재 여부”를 빠르게 판단해야 할 때 List보다 훨씬 적합하다.

따라서 자료구조를 공부할 때 그 구조가 왜 그렇게 동작하고, 어떤 상황에서 어떤 선택이 더 적절한지

스스로 설명할 수 있는지를 얘기할 수 있으면 좋을 거 같다.

 

그런 의미에서 나도 다시 한 번 자료구조 중 HashSet과 HashMap에 대해 개념적으로 자세히 기술해보려고 한다. 

 

Set의 보편적인 특징과 내부 자료구조 선택 

Set의 보편적인 특징은 다음과 같다.

• 중복을 허용하지 않음
• 요소 간의 순서를 보장하지 않음(※ 단, 입력 순서를 유지하는 LinkedHashSet은 예외)

이 두 가지는 Set이 어떤 내부 자료구조를 사용하든
“집합(Set)”이라는 추상적 개념에서 비롯된 공통 특징이다.

즉, Set자료구조는 처음부터 “중복이 없어야 한다”는 집합의 성질을 만족시키기 위해
각 구현체가 서로 다른 방식(Map, LinkedMap, Tree)을 사용해 이를 실현하는 것이다.

대표적인 구현체는 다음과 같다.

HashSet → HashMap 기반 LinkedHashSet → LinkedHashMap 기반 (입력 순서 유지) TreeSet → TreeMap 기반 (정렬된 구조)

 

이 중에서도 실무에서 가장 많이 쓰이는 구현체가 바로 HashSet이다.
HashSet은 내부적으로 HashMap을 기반으로 작동하고,
HashMap의 Key 구조를 그대로 활용하여 Set이 요구하는 “중복 없음”이라는 특성을 자연스럽게 만족한다.

 

만약 다음과 같은 코드가 있다고 하자

HashSet<String> set = new HashSet<>();
set.add("김민제");

⇒ 이는 내부적으로 사실

map.put("김민제", PRESENT);

이렇게 값이 들어간다.

PRESENT는 그냥 private static final Object 하나의 상수로, 실제 값 의미는 없다.

 

실제로 HashSet의 add method 내부를 보면 다음과 같다.

 

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;
    // 모든 value는 동일한 상수
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

⇒ 실제 Set 구현체로 들어가보면 이렇게 구현되어있다.

왜 저 의미없는 PRESENT 값을 넣냐면

private transient HashMap<E,Object> map;

여기서 확인할 수 있듯이, hashSet은 HashMap으로 구현되어 있기 때문이다.

Map은 Key , value의 한 쌍의 값이기 때문에 Value로 의미없는 값이라도 넣어주는 것이다.

 

 

 

 

왜 HashSet이 HashMap으로 구현됐을까

⇒ 이는 Set의 특성이 Hash 기반 Map의 Key 구조와 거의 완전히 일치하기 때문이다.

Set은 “Key만 존재하는 Map”의 형태에 가깝고 HashMap은 이미 수십년 동안 최적화·검증된 해시 기반 자료구조이며 새로운 자료구조를 처음부터 만들 필요 없이 HashMap을 얇게 감싼 형태로 구현 비용·성능·메모리 효율을 모두 챙길 수 있기 때문이다.

즉, HashSet은 “키만 필요한 상황을 위해 설계적으로 최소한의 래핑만 한 자료구조”라고 보면 된다.

 

 

 

 

다시 본론으로 돌아와

HashSet<String> set = new HashSet<>();
set.add("김민제");

이런 코드가 있다면 다음과 같이 내부적으로 동작한다.

 

 

순서대로 봐보자.

 

1. hashTable의 key값을 hash function의 모듈러 연산을 통해 정수로 계산한다.

    * 참고로 HashFunction은 Java.Lang.String에 다음과 같이 구현 되어있다.

for (byte v : value) {
    h = 31 * h + (v & 0xff);
}

 

=> 위의 계산을 거쳐 정수로 나온 값을 Hash값이라고 부른다.

=> 정수값이기 때문에 특정 값은 해시 값이 같게 나올 수 있다는 것을 유념해야 한다.

 

2. 계산된 hash 값을 버킷 배열 크기로 모듈러 연산하여 index 산출 

모듈러 연산  (hash 값 % 버킷 사이즈) = index

 

3. 해당 버킷에 Node(=entry)로 저장 => Key, Value, Hash값, Next Node 참조 값이 있다.

4. 충돌이 발생하면 체이닝(Linked List) 혹은 TreeNode 구조로 보관한다

 

 

Hash 충돌 시 데이터 저장 법 

JDK 8 이전에는 모두 LinkedList 방식이었다. 

JDK 8 이후로는 LinkedList로 시작했다가 

한 버킷에 노드가 8개 이상 모이면 

red-black-tree로 자동 변환된다. 

 

bucket[1]
   ↓
           (root)
         /        \
    ("ABC")     ("XYZ")
      /  \         /  \
   ...  ...     ...  ...

다음과 같이 트리가 되면, 

탐색 속도가 O(log n)이되기 때문에 LinkedList의 O(n) 탐색 속도보다 빨라진다는 장점이 생기는 것이다. 

 

 

Hash값을 왜 저장할까

⇒ 이유는 검색최적화 이다.

특히나 위와 같이 해시 충돌이 일어나서 O(n) 혹은 O(log n)의 탐색을 하게 될 때이다. 

• get(key)나 contains(key)를 호출할 때, 먼저 hash 값만 비교한다.
• hash 값이 다르면 key 비교 안 하고 바로 건너뛴다 → 문자열 비교 같은 비용 큰 연산 최소화
• hash 값이 같으면 → 실제 key.equals()로 최종 확인
• 앞서 말했듯, Hash 값은 드물게 같은 값이 나올 수 있기 때문에 최종적으로 문자열 비교를 시행한다.

예시:
bucket[2]
 ├─ Node(hash=1234567890, key="김민제", ...)
 ├─ Node(hash=987654321 , key="이수현", ...)

• 검색: "김민제" 찾을 때
  1. 먼저 hash("김민제") → 1234567890
  2. 버킷 2 확인
  3. Node 하나씩 비교 → hash 일치하면 key.equals() 확인
  4. → hash 값 다르면 key.equals() 안 해도 된다 어차피 다른 값이니까 ! 

 

 

근데 여러분은 HashMap의 기본 버킷 사이즈가 16인 이유가 뭔지 아시나요 ??

JDK 8의 HashMap의 기본 capacity는 16이다. 

단순히 뭐 적당한 메모리 사이즈를 지정해줬다고 생각할 수도 있을 거 같다.

핵심부터 말하자면, 비트연산을 통한 인덱스 계산 최적화 이다. 

 

이에 대해서는 

https://programmingmy-00.tistory.com/63

CPU 관점에서 다시 보는 HashMap의 비트 연산과 초기 용량 16의 의미

다음의 글에서 자세히 기술해봤다 !!