[Java] HashSet과 HashMap 성능 차이

Java

 몇 달 전에 알고리즘 문제를 풀었는데 이상하게 시간이 오래 걸렸습니다. 분명 로직은 맞는데 HashMap을 쓴 코드와 HashSet을 쓴 코드의 성능 차이가 많이 났습니다. 왜 Why? 지금부터 여기에 대해서 파보려고 합니다.

 

1. HashMap과 HashSet의 차이점?

HashMap: 키-값(key-value) 쌍을 저장하는 자료구조입니다. 키는 고유하며 값은 중복될 수 있습니다. 주로 put(key, value), get(key), remove(key) 같은 작업이 이루어집니다.

 

HashSet: 중복되지 않는 고유한 요소들의 집합을 저장하는 자료구조입니다. 내부적으로 HashMap을 사용하여, 각 원소를 HashMap의 키로 저장하고, 값은 고정된 더미 객체(PRESENT)를 사용합니다.

 

잠시만요. HashSet에서는 HashMap을 쓴다고 합니다. 심지어 key의 value는 더미 객체를 집어넣습니다.

 

엥, 그래도 이론적으로는 HashSet이 HashMap과 동일한 해시 기반 구조를 사용하기 때문에 상수 시간 O(1) 성능을 기대할 수 있지 않습니까..?

 

모든 일이 기대에 미치는 수준이면 얼마나 좋겠습니까. 궁금증 해결을 위해서는 HashMap과 HashSet의 코드를 한번 뜯어봐야 합니다.

 

2. 왜 HashSet이 더 느릴 수도 있나요..?

HashMap의 put() 메서드

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

 먼저 HashMap부터 코드를 하나하나 파고 들어가 보겠습니다. 데이터를 추가하는 put() 메서드입니다.

 

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

 실제로 값을 넣는 putVal() 메서드의 구조.

 

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

 HashMap의 구성요소인 Node 클래스.

 

HashSet의 구조

HashSet

 HashSet의 구현 코드를 열자마자 HashMap이 보입니다. 추가로 더미 객체인 PRESENT도 있습니다. PRESENT야 클래스 로딩할 때, 딱 한번 생성해 두고 재사용하는 거라 오버헤드가 발생하지는 않겠지만..

 

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

 HashSet의 add() 메서드. HashMap의 put() 메서드에 더미 객체와 함께 key를 넣는 것을 볼 수 있습니다. 이 과정에서 추가적인 메서드 호출이 발생하기 때문에 작은 오버헤드가 생기겠죠? 요런 부분뿐만이 아니라... 여러 가지 복합적인 사정이 있습니다.

 

불필요한 값 비교: HashMap의 put() 메서드는 새로운 키-값 쌍을 삽입할 때, 값이 변경되었는지 확인하는 과정을 거칩니다. HashSet에서는 값이 항상 동일한 PRESENT 객체임에도 비교연산이 수행됩니다.

 

해시 충돌 처리 시 값 처리: 해시 충돌이 발생할 때, HashMap은 동일한 해시 값을 가진 다른 키와 값을 연결하는 구조(체이닝 방식 등)를 사용합니다. 이때 값 비교 및 업데이트 로직이 포함됩니다. 그러나 HashSet에서는 항상 동일한 값(PRESENT)을 사용하므로 이 과정 역시 불필요합니다.

 

 

뭐 .. 최적화 정도의 차이라고 보면 될 것 같습니다. HashMap을 가져다 썼기 때문에 발생한 이슈.

 

// HashSet
for (int i = 0; i < 10000000; i++) {
            hashSet.add(i);
}

// HashMap
for (int i = 0; i < 10000000; i++) {
            hashMap.put(i, i);
}

 

실제로 1000만 개 정도의 데이터를 HashSet과 HashMap에 넣고 걸린 시간을 측정해 보면 어떻게 나올까요?

 

HashSet 걸린 시간: 8294567209ns
HashMap 걸린 시간: 5129179416ns

엄청난 차이를 보입니다..

이런 이유로 Set보다는 Map을 쓰라는 말이 나오는 것 같고...

 

 

라기엔 데이터 100만 개를 넣었을 때는 다음과 같은 성능을 보입니다.

HashSet 걸린 시간: 166217542ns
HashMap 걸린 시간: 615533667ns

왜 이러는 걸까요?

 

이건 HashMap은 데이터가 적을 때 Linked List로, 많을 땐 Red Black Tree로 관리하는데... 다음 시간에 알려드리도록 하겠습니다.