Java HashMap 의 동작 원리 (Java 8 이상에서)

Map 은 key - value 쌍으로 데이터를 저장하기 위한 자료구조이다.

HashMap은 Map의 구현체 중 하나로, 기본적인 아이디어는 다음과 같다.

Map은 Key를 통해 Value에 접근할 수 있어야 한다.
Key를 해싱해 배열의 index로 사용하고, 거기에 Value를 두면 되지 않을까?

이 아이디어를 구현하기 위해, HashMap은 객체의 hashCode() 값을 사용하여 Key를 배열의 index에 매핑한다.

HashMap이 Key를 index로 매핑하는 법

HashMap은 객체의 hashCode() 값을 사용한다.
HashMap은 Key를 배열의 index로 매핑시키기 위해 객체의 hashCode() 값을 length와 함께 연산해 index를 구한다.

왜 해시값에 length를 사용한 추가 연산을 할까? 🤔

해당 객체를 배열의 index 중 하나로 매핑시키기 위함이다.(연산 과정 참고)

연산 과정은 다음과 같다.

우선, 해시 보조 함수를 통해 해시값을 구한다.

hash = key.hashCode() ^ (hash >>> 16);

왜 이런 연산을 할까?

** 객체의 hashCode() 를 호출하면, 32비트 값이 얻어진다(hashCode() 는 int를 반환하기 때문이다)
HashMap에서는 배열 index 를 계산할 때 비트 연산을 이용하는데, 기본적으로 index = hash & (length - 1) 방식을 사용한다.
하지만, 이 방식은 배열 length의 하위 비트만 사용하기 때문에, 비트 분포가 균일하지 않으면 해시 충돌이 많이 발생할 위험이 있다.

배열 length의 하위 비트만 사용?

배열 length는 일반적으로 2의 거듭제곱이다. HashMap의 기본 크기는 16이고, 두 배씩 커지기 때문이다.

다음과 같은 상황을 생각해 보자.
hash
=> 00010010001101000101011001111000

length - 1 = 128 - 1
=> 00000000000000000000000111111111

둘을 이래에 나오는 나머지 연산을 하게 되면, length의 하위 비트인 111111111 만 사용하게 된다.

이를 방지하기 위해 hashCode() 와 hashCode() 를 16 만큼 bit shift 한 값을 XOR 연산하여 섞는다. 이를 해시 보조 함수라고 하고, Java 8 부터는 위 코드를 통해 해시 보조 함수를 구현한다. 해시 값의 분포를 더욱 균등하게 만들어 해시 충돌 가능성이 줄어들게 하기 위해 해시 보조 함수를 사용한다.

해시 보조 함수 연산 과정

Person A의 hashCode() 와 A의 hashCode() 를 16 만큼 bit shift 한 값을 XOR 연산한다. (참고: XOR 은 서로 달라야만 1)

00010010001101000101011001111000 : Person A의 hashCode()
0000000000000001001000110100 : h >>> 16
------------------------------------------------- XOR 연산
00010010001101010111011100111000

이제 해시값을 구했으니, 이 해시값을 알맞은 index로 매핑시키면 된다.
index로 매핑하기 위해서 자바의 HashMap은 다음과 같은 과정을 거친다. (일반적으로, 나머지 연산과 동일하다)

index = (n - 1) & hash // HashMap 의 putVal 메서드 내부 구현으로, 나머지 연산이라고 생각하면 된다.

n은 HashMap의 크기로, 배열의 length이다.
length - 1과 나머지 연산을 통해 length를 넘지 않는 Index를 구할 수 있다.

그럼 Value는 어떻게 저장할까?

Key의 hashCode() 와 배열의 length를 사용해 index를 구하다 보면, 다른 Key가 동일한 index값을 가지는 경우가 생길 수밖에 없다. 이를 해시 충돌이라고 한다.
해시 충돌이 발생했다고 가정해 보자. Person A가 index 0으로 매핑되어 있는 상황에서, Person B를 해싱해 index를 구했더니, index 가 0이 나왔다.
이를 해결하기 위한 방법은 크게 두 가지가 있다.

1. Open Addressing

Open Addressing은 해시 충돌이 발생하면 다른 빈 index를 찾고, 해당 index에 데이터를 저장하는 방식이다. Java의 HashMap은 이 방식을 사용하지 않는다.
Open Addressing의 빈 index탐사 방식은 세 종류가 있다.

선형 탐사
- 고정된 간격으로 다음 index에 데이터를 채워 넣는다.
- ex) 3번 index가 이미 사용 중이라면, 4번 index에 데이터를 넣는다.
장점: 연속된 메모리에 데이터를 저장하므로, Cache Hit Rate가 높다.

단점: 연속된 메모리에 데이터를 저장하므로, 클러스터링(배열의 특정 부분에만 데이터가 몰리는 상황)이 발생할 수 있다. 클러스터링이 발생하면 탐색 시간이 오래 걸린다는 단점이 있다.(계속 다음 데이터를 찾아 나서야 하므로)
제곱 탐사
- i^2 만큼 뒤에 있는 index에 데이터를 저장한다.
- ex) 3번 index가 이미 사용 중이라면, 4번((3 + 1^2) % length) index에 데이터를 넣는다. 만약, 그다음에도 3번 index에 값을 넣어야 한다면, 7번((3 + 2^2) % length) index에 데이터를 넣는다.
장점: 선형 탐사해 비해 클러스터링 문제가 어느 정도 해결 가능하다. 데이터를 i^2 만큼 띄어 저장하기 때문에, 연속된 부분에 데이터를 저장하지 않기 때문이다.

단점: 배열 크기가 2의 거듭제곱인 경우, 같은 index 패턴이 반복될 수 있다(length가 16일 때, i^2 % 16을 하면 같은 위치를 반복할 가능성이 높아진다). 또한, 선형 탐사에 비해 클러스터링 문제가 어느 정도 해결되었다고 해도, 여전히 클러스터링 문제는 존재한다.
이중 해싱
- 선형 탐사와 제곱 탐사의 클러스터링 문제를 해결하기 위해 나온 개념이다.
- 해시 충돌이 발생하면, 또 다른 해시 함수를 통해 새로운 해시 값을 얻어 재시도한다.
- 공식은 다음과 같다.
- index = (hash1(key) + i * hash2(key)) % table_size
- 해시 충돌이 생겨 추가 해싱을 했는데도 해시 충돌이 발생하면, i 값이 ++된다(hash2(key) 만큼 더 이동한다).
장점: 클러스터링 문제가 해결된다. 연속된 메모리에 저장될 확률이 낮기 때문이다.

단점: 해시 함수를 두 개 사용하게 되므로, 속도가 비교적 느리다. 또한, 배열 크기가 소수가 아니면 특정 패턴이 반복될 수 있다.

2. Chaining

Chaining은 각 index에 Value를 저장하는 대신, Node를 사용해 데이터를 저장하는 방식이다.
Node는 LinkedList와 같이 서로 연결되어 있다.
해시 충돌이 발생하면 해당 index의 맨 마지막 Node뒤에 새로운 Node를 만들어 해당 Node에 데이터를 저장하는 방식이다.

Node는 최소한 Key와 Value, 그리고 nextNode를 가지고 있어야 한다.

장점: 테이블 크기를 늘리지 않고도 체이닝 방식으로 충돌을 처리할 수 있다.
단점: Node인스턴스를 통해 데이터를 관리하므로, 추가적인 메모리가 필요하다(Key, nextNode)

Java의 HashMap은 해시 충돌을 처리하기 위해 Chaining방식을 채택했다.

HashMap의 구현

HashMap은 내부적으로 Node클래스의 배열을 가진다. 위의 Chaining방식을 생각하면 된다.

// HashMap 내부
Node<K, V>[] table;

Node클래스의 구현을 보자.

HashMap의 Node클래스

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

Node클래스는 다음과 같은 필드를 가진다.

hash: int (key의 hashCode() 를 사용한 hash 연산 결과이다)
key: K
value: V
next: Node

Node에 hash를 저장하는 이유는 뭘까?

이를 이해하기 위해 HashMap의 두 가지 동작에 대해 알고 있어야 한다.

리사이징

배열은 초기화 시 크기가 필요하다. HashMap의 Node배열은 기본 크기가 16이다.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap은 리사이징을 위한 임계값으로 기본 0.75를 제공한다.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashMap은 기본적으로, 현재 최대 크기의 0.75 만큼 size(저장된 Node의 개수)가 차면 리사이징을 수행한다. 리사이징이 일어나면, 배열의 최대 크기가 두 배 증가한다(16 → 32 → 64 …)

리사이징이 일어나면 기존의 항목들을 새 배열로 복사하면서 각 항목의 index를 다시 계산한다.

재배치

리사이징이 일어나면 크기가 두 배인 새로운 배열이 생성된다.
새로운 배열이 생성되면, 기존 배열에 존재하던 객체들의 해시를 다시 계산해서 새로운 배열의 index에 위치시켜야 한다.
index를 구하기 위해서는 length가 필요하므로, length가 바뀐다면 Index도 바뀌어야 하기 때문이다.

이를 바탕으로 Node에서 hash를 저장하는 이유를 알 수 있다.

리사이징이 발생할 때, 기존의 항목을 새로운 배열 내부로 재배치해야 한다. 이 과정에서 해시 보조 함수를 통해 계산된 해시 값과 Node배열의 length를 사용하여 새로운 index를 계산해야 한다. 하지만, 해시 보조 함수를 통해 계산되는 해시 값은 Node배열의 length와는 독립적이다. Key의 hashCode() 만을 사용하기 때문이다. 그러므로, Node내부에 해시 보조 함수를 통해 계산된 해시값을 저장해 놓으면 이 값을 바로 사용할 수 있어 더 효율적인 연산을 할 수 있다.
만약 Node내부에 해시 보조 함수를 통해 계산된 해시값이 저장되어 있지 않다면, 리사이징 시마다 hashCode() 메서드를 호출하여 해시값을 재계산해야 하므로 불필요한 연산이 발생한다.

Node에 key, next를 저장하는 이유는 뭘까?

삽입 과정에서 해시 충돌이 발생했다고 가정해 보자.

HashMap은 해시 충돌이 일어나면, Node들을 순회하며 Node에 있는 hash가 Key를 해싱한 결과와 동일한지, Node의 Key가 삽입할 Key와 동일한지 확인한다.

만약, 동일한 해시와 Key를 가지고 있지 않다면, 새로운 Node를 생성해 해당 index의 마지막 Node뒤에 붙인다 (Linked List 방식).
Chaining 방식 구현을 위해 Node의 next를 사용한다.

마지막으로, HashMap이 Node를 TreeNode로 전환하는 메커니즘을 알아보자.

버킷(Node 배열의 각 Index)의 크기가 커지면 TreeNode로 전환

버킷은 Node배열의 각 index이다.
버킷에 해당되는 Node의 수는 해시 충돌에 따라 계속 늘어나거나 줄어들 것이다.
만약 해시 충돌이 많이 발생해 하나의 버킷이 많은 데이터를 저장하게 되면, 조회 시간복잡도가 계속 늘어나게 될 것이다.

HashMap은 이를 개선하기 위해 버킷에 특정 개수 이상의 Node들이 쌓이면 해당 버킷의 Node를 TreeNode로 변경한다. TreeNode를 통해 이진 탐색 트리를 구성하면 조회 시간복잡도가 O(log n)이 되기 때문이다.

LinkedList방식의 조회 시간복잡도 = O(n)
Binary Search Tree의 조회 시간복잡도 = O(log n)

**주의 : 해당 버킷의 Node들만 변경한다. 다른 버킷의 Node들은 변경하지 않는다.

각 버킷의 Node들이 Treeify를 하기 위해서는 최소 64 개의 Node배열 크기를 가져야 한다.

static final int MIN_TREEIFY_CAPACITY = 64;

HashMap은 하나의 버킷에 8개 이상의 Node가 존재함과 동시에, Node배열 크기가 64 이상이 되면 Treeify를 수행한다.

static final int TREEIFY_THRESHOLD = 8;

또한, HashMap은 하나의 버킷에 6개 이하의 Node만 남게 되면 unTreeify를 수행한다.

static final int UNTREEIFY_THRESHOLD = 6;

6개, 8개로 지정한 이유는 만약 차이가 1이라면 어떤 한 key-value 쌍이 반복되어 삽입, 삭제되는 경우 불필요하게 TreeNode와 Node사이의 변환이 반복되어 성능 저하가 발생할 수 있기 때문이다.

저작자표시 비영리 변경금지

DevLog