[Java] HashMap 구현

출처

ChatGPT

자바 1.8 소스 코드

---

자바의 HashMap은 자바 컬렉션 프레임워크에서 가장 많이 사용되는 자료구조 중 하나로, 키-값 쌍(key-value pair)을 저장하는 데 사용된다. HashMap은 해시 테이블 기반으로 동작하며, 키를 하시 함수로 변환해 데이터를 빠르게 저장하고 검색할 수 있도록 설계되었다.

 

1. HashMap의 주요 특징

상수 시간 성능

일반적으로 HashMap에서 삽입, 삭제, 조회는 O(1) 시간 복잡도를 가진다. 즉, 매우 빠른 접근 성능을 제공한다. 하지만 해시 충돌이 많아질 경우, 성능은 O(n)까지 떨어질 수 있다.

비동기적

HashMap은 기본적으로 동기화되지 않으며, 멀티스레드 환경에서 동시에 수정될 경우 안전하지 않다. 동기화가 필요한 경우, Collections.sysnchronizedMap()으로 동기화된 맵을 사용할 수 있다.

null 허용

HashMap은 null 키와 null 값을 허용한다. 단, null 키는 하나만 저장할 수 있으며, null 값은 여러 개 저장할 수 있다.

 

2. HashMap의 내부 구조

HashMap은 내부적으로 배열과 연결 리스트(또는 트리 구조)를 사용해 데이터를 저장한다. 이 배열은 버킷(bucket)이라고 하며, 각 버킷에는 해시 충돌이 발생한 경우를 처리하기 위한 연결 리스트 또는 트리가 저장된다.

• 관련 글 -> [Java] 버킷 Butcket

1. 해시 버킷 구조

• HashMap은 해시 함수를 사용해 키를 특정 인덱스로 변환하고, 해당 인덱스(버킷)에 값을 저장한다.
• 동일한 해시 값이 발생하면, 해당 버킷의 연결 리스트(혹은 트리)에 데이터를 저장해 충돌을 처리한다.

2. Node 클래스

HashMap의 내부적으로 사용되는 각 항목(키-값 쌍)은 Node라는 내부 클래스로 표현된다. Node는 하나의 키-값 쌍을 나타내며, 해시 값을 포함하고 있다.

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;
    }
}

 

• hash : 키의 해시 값으로, 해시 테이블에서 버킷을 찾는 데 사용된다.
• key : HashMap에 저장된 키
• value : 키에 매핑된 값
• next : 동일한 해시 값으로 충돌이 발생했을 때, 연결 리스트의 다음 노드를 가리킨다.

 

3. 해시 함수와 충돌 처리

1. 해시 함수

HashMap은 키의 해시 값을 계산하기 위해 hashCode() 메서드를 사용한다. hashCode()는 객체의 해시 코드를 반환하는 메서드로, 이 값은 HashMap이 데이터를 버킷에 저장할 위치를 결정하는 데 사용된다.

• 관련 글 -> [Java] 객체의 해시 코드란 무엇인가

• 관련 글 -> [Java] hashCode() 오버라이드 시 equals()도 함께 오버라이드 해야하는 이유

 

하지만 hashCode()는 매우 다양한 32 비트 정수 값을 반환할 수 있지만, HashMap의 유한한한 배열 크기에 한계가 있으므로, 해시 값은 배열의 크기에 맞게 비트 연산을 조정된다. 이를 통해 버킷 인덱스를 구한다.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

이 메소드은 키의 해시 값을 계산한 후, 해시 값의 상위 비트를 하위 비트와 XOR 연산해 해시 값의 분포를 더 균일하게 만든다.

2. 충돌 처리

• 관련 글 -> [자료구조] 해시 충돌 Hash Collision

해시 충돌이 발생하는 경우, 연결 리스트 또는 트리르 사용해 충돌을 처리한다.

• 연결 리스트 : 같은 버킷에 저장되는  모든 항목은 Node 객체로 연결 리스트 형태로 저장된다.
• 트리 : 자바 8부터, 충돌이 많이 발생할 경우(리스트의 크기가 8 이상일 때), HashMap은 연결 리스트 대신 레드-블랙 트리로 구조를 변경해 탐색 성능을 향상시킨다. 트리로 변환되면 시간 복잡도는 O(n)에서 O(log n)으로 개선된다.

if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

 

THEEIFY_THRESHOLD는 기본값으로 9이다. 리스트가 8개 이상의 노드를 가지면 트리로 변환된다.

• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

4. HashMap의 기본 동작

1. 데이터 삽입 (put 메소드)

데이터를 HashMap에 삽입할 때는 키의 해시 값을 계산한 후, 해당 해시 값을 기반으로 버킷 인덱스를 찾는다. 버킷이 비어 있지 않으면, 충돌이 발생할 것이므로 연결 리스트나 트리로 데이터를 삽입한다.

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

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)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // key already exists
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

 

• hash(key) : 키의 해시 값을 계산한다.
• resize() : 테이블이 꽉 차면 해시 테이블의 크기를 늘린다.
• treeifyBin() : 충돌이 많아지면 연결 리스트를 트리로 변환한다.

2. 데이터 조회 (get 메소드)

데이터를 조회할 때도, 키의 해시 값을 계산하여 해당 해시 값에 맞는 버킷에서 연결 리스트 또는 트리 구조를 탐색한다.

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash &&  // check if first node matches
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {  // check if next nodes match
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

 

키의 해시 값을 기반으로 해당 버킷에서 요소를 찾는다. 만약 충도로이 발생하면 연결 리스트 또는 트리에서 키를 찾는다.

 

5. 리해싱과 성능 최적화

HashMap은 데이터가 많아지면 자동으로 테이블의 크기를 늘리는데, 이 과정을 리해싱(rehashing)이라고 한다. 테이블의 크기가 75%가 차면 resize() 메소드를 통해 크기를 늘리고, 기존 데이터를 다시 해시하여 새로운 테이블에 재배치한다.

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null)
                        loTail.next = null;
                    newTab[j] = loHead;
                    if (hiTail != null)
                        hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
    return newTab;
}

 

기본적으로 두 배로 크기를 확장하며, 기존 데이터를 해로운 해시 테이블로 재배치한다.

 

6. 결론

HashMap은 자바에서 가장 중요한 자료구조 중 하나로, 해시 테이블을 기반으로 빠른 성능을 제공한다. 키와 값을 기반으로 해시 버킷에 데이터를 저장하고, 충돌이 발생하면 연결 리스트 또는 트리 구조를 사용하여 성능을 유지한다. HashMap은 리해싱을 통해 동적으로 크기를 조정하며, 주어진 데이터에 대해 매우 효율적으로 동작한다.