Java에서는 HashMap이 어떻게 구현되고 무슨 자료구조를 가지고 있을까?

HashMap

HashMap은 Key-Value가 1:1로 Mapping 되는 자료구조이다.
Key는 Uniqueness 해야하고 Value는 중복을 허용한다.
Key와 Value를 Mapping 하기 때문에 삽입/삭제/검색이 평균적으로 O(1)이 된다.

Java HashMap의 클래스 구조

HashMap은 해시 값과 키 값으로 키 버킷 인덱스(hash(key) % M)를 만들고 이 인덱스를 키로 하는 value인 해시 노드를 가지고 있다. 해시 노드는 (key, value)쌍으로 이루어져 있다. 이때 M은 버킷 사이즈이다.

예를 들어 이런식이다.

Bucket Index 1: HashNode("ex_key", "ex_val") -> HashNode("ex_key2", "ex_val2")
Bucket Index 2: 
Bucket Index 3: HashNode("ex_key3", "ex_val3")
... 

Java에서는 해시 충돌(Hash Collision)을 어떻게 해결할까?

해시 충돌 시 해결 방법에는 Open Addressing과 Chaining 방법이 있다.

자바에서 해시 충돌 시에는, (Seperate) Chaning 방식을 사용하고 있다.
(해시값%M)이 이미 키로 사용되고 있다면 HashNode를 사용해 연결 리스트로 구현한다.

아래는 M = 10인 버킷이다.
해시 값인 hash("ex_key")가 11이면 버킷 인덱스는 11%10인 1이 된다.
만약 이후에 버킷 인덱스가 1인 "ex_key"가 아닌 다른 키 값이 추가되어야 한다면(충돌 상황),
(”ex_key”, “ex_val”) 해시노드 다음 노드로 연결 리스트 형태로 이어지게 된다.

Bucket Index	HashNode
1	(”ex_key”, “ex_val”)
2
3
4
5
6	(”ex_key6”, “ex_val6”)
7
8
9
10

만약 하나의 (해시값%M)에 해당하는 (key-value) 쌍이 8개가 되면 링크드리스트를 TreeMap(레드 블랙 트리) 구조로 바꾼다.

LinkedList 보다 Tree 구조의 메모리 오버헤드가 크고 데이터 추가/삭제/수정 시 균형을 맞추기 때문에 링크드리스트보다 느릴 수 있다. 반면, 데이터 갯수가 많고 검색 성능이 중요하면 Tree 구조가 좋다.

구현 코드

다음은 gpt가 HashMap 로직을 추상화하여 보여준 코드이다.

// HashNode 클래스: 각 버킷에 저장되는 키-값 쌍을 나타내는 노드
class HashNode<K, V> {
    K key;
    V value;
    HashNode<K, V> next; // 다음 노드를 연결하기 위한 링크

    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

// HashMap 클래스: 해시 테이블을 관리하는 클래스
class HashMap<K, V> {
    private static final int INITIAL_CAPACITY = 10; // 초기 배열 크기
    private HashNode<K, V>[] buckets; // 해시 테이블 (배열)
    private int size; // HashMap에 저장된 키-값 쌍의 개수

    @SuppressWarnings("unchecked")
    public HashMap() {
        this.buckets = new HashNode[INITIAL_CAPACITY];
        this.size = 0;
    }

    // 해시 함수: 키의 해시코드를 이용하여 배열 인덱스를 계산
    private int getBucketIndex(K key) {
        int hashCode = key.hashCode();
        return Math.abs(hashCode) % buckets.length;
    }

    // 키-값 쌍을 HashMap에 저장
    public void put(K key, V value) {
        int index = getBucketIndex(key);
        HashNode<K, V> newNode = new HashNode<>(key, value);

        // 해당 인덱스의 버킷에 노드 추가
        if (buckets[index] == null) {
            buckets[index] = newNode;
        } else {
            HashNode<K, V> current = buckets[index];
            while (current.next != null) {
                if (current.key.equals(key)) {
                    current.value = value; // 이미 존재하는 키라면 값을 갱신
                    return;
                }
                current = current.next;
            }
            current.next = newNode; // 마지막 노드 뒤에 새 노드 추가
        }

        size++; // 사이즈 증가
    }

    // 키에 해당하는 값을 가져옴
    public V get(K key) {
        int index = getBucketIndex(key);
        HashNode<K, V> current = buckets[index];

        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }

        return null; // 해당 키가 없는 경우 null 반환
    }

    // HashMap의 크기(저장된 키-값 쌍의 개수) 반환
    public int size() {
        return size;
    }
}

put(K, V)

put(K, V)을 할 때는 해당 키값으로 버킷 인덱스를 가져와서 처음 등록되면 노드를 추가해준다. 이미 있는 버킷 인덱스였다면 HashNode의 다음 노드로 연결하게 된다.

static final int TREEIFY_THRESHOLD = 8;

하나의 버킷 인덱스에 저장할 수 있는 HashNode의 최대 갯수는 8개이고 8개가 넘어가게 되면 treeifyBin()으로 트리화 하게된다.

get(K)

get(K)을 할 때는 해당 키로 버킷 인덱스를 가져와 해당 HashNode를 가져온다. 그리고 연결리스트로 되어있는 노드를 하나씩 비교하여 실제 키 값과 일치하는 것을 찾아 반환한다.