시작하기 전에
- 이 글은 자바언어에서 HashMap의 구조에 대해서 설명하고 있습니다.
- 다음 포스트에서는 ConcurrentHashMap등의 HashMap에서 동기화문제를 어떻게 해결하는지에 대해서 다루려고 합니다.
Java HashMap은 어떻게 동작할까?
- 이 글은 Java 7과 Java 8을 기준으로 HashMap이 어떻게 구현되어 있는지 설명합니다. HashMap 자체의 소스 코드는 Oracle JDK나 OpenJDK나 같기 때문에, 이 글이 설명하는 HashMap 구현 방식은 Oracle JDK와 OpenJDK 둘 모두에 해당한다고 할 수 있습니다.
1. HashMap이란?
- 데이터를 key-value의 쌍으로 저장하며 키에 대한 해시 값을 활용하여 Amortization cost O(1)에 데이터를 조회, 추가, 삭제할 수 있는 Associate Array이다.
Asscociate Array
- index 값을 통해 random Access하는 일반적인 배열과 달리 어떠한 key값을 통해 데이터의 위치를 알아낼 수 있는 자료구조이다.
Hash And HashCollision
- 해싱(Hashing) 이란? 특정 데이터를 일관된 절차를 통해 고정된 크기의 데이터로 변환하는 과정을 말한다.
int index = X.hashCode()- 자바에서는 데이터에 대한 해쉬 값이 2^32가지의 정수형을 가질 수 있다.
- 문제는 데이터의 종류는 사실상 무한하기 때문에 서로다른 데이터가 같은 해쉬 값을 가지는 경우가 생기고 이 경우를 hash Collision(해쉬 충돌)이라고 한다. 일반적으로 해쉬 함수는 해쉬 충돌을 줄일 수 있는 방향을 추구해야한다.
Open Addresssing vs Seperate Chaining
- 일반적으로 데이터크기가 많아질 수록, 삭제 처리시 Seperate Chaining이 더 효율적이다. HashMap에서는 Seperate Chaining을 활용한다.
2. Sequence Chaining 동작 원리
- 내부에 해쉬 버켓이라는 데이터를 담는 Node<key, value> 배열을 가지고 있다.
- 그림 왼쪽에 있는 배열이 해쉬 버켓에 해당한다.
특정데이터 삽입 시 Sequence Chaining은 다음과 같이 동작한다.
1) 먼저, 미리정의된 객체(key)의 HashCode함수와 해쉬 버켓의 크기(N)를 활용하여 key에 대한 해시값을 구한다.
int index = key.hashCode() % N2) index값에 해당하는 배열에 위치에 접근하여 데이터를 추가하는데 만약 해당위치에 이미 데이터가 있다면 해당위치에 데이터를 추가할 수 없으므로 해당 위치데이터의 링크드리스트를 따라가면서 자신의 key값과 같은 데이터가 있다면 덮어씌우고 없다면 다음으로 계속 이동하면서 같은 데이터를 발견하지 못했을 경우 마지막에 데이터를 추가한다.
Hash Collision 문제
- 위에서 설명한 것 처럼 데이터를 추가할 때 최악의 경우 서로 다른 데이터가 같은 index값으로 결정되고 하나의 버켓에 몰려 chain의 길이가 요소의 전체개수에 비례하는 경우가 생길 수 있다.
- 이 경우 검색, 삭제, 삽입 모두에서 O(N)의 시간복잡도가 발생할 수 있으며, 이는 Associate Array자료구조를 잘 만들기 위해 꼭 해결해야하는 문제이다.
- 이 문제를 해결하기 위해 HashMap은 해쉬 충돌이 적은 해쉬함수활용, 보조 해쉬함수 사용, 해시 버켓 확장 재할당, chain을 tree(레드 블랙 트리)로 바꾸는 등의 여러 방식을 활용하고 있다.
3.HashMap동작 원리-해쉬 버켓 중첩 문제 해결 중심
주요 변수
transient Node<K,V>[] table;
//해쉬 버켓배열
transient int size;
//저장된 Node 요소의 개수
int threshold;
//해시 테이블 재구축 기준
final float loadFactor;
//해시 테이블 재구축 기준 비율
transient int modCount;
//해시 테이블 재구축 회수
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// aka 16, 기본 해쉬 버켓의 개수
static final int MAXIMUM_CAPACITY = 1 << 30;
// 최대 해쉬버켓의 개수, 2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 기본 load_factor
static final int TREEIFY_THRESHOLD = 8;
//기본 링크드리스트를 트리로 변환할 기준
// 한 해쉬 버켓에 연결된 노드의 개수가
//이 기준을 넘어가면 트리로 만듬 레드블랙트리로 만들어짐.해시 버킷 동적 확장
- HashMap은 키-값 쌍 데이터 개수(size)가 threshold(load factor * 현재의 해시 버킷 개수)이상이 되면, 해시 버킷의 개수를 두 배로 늘린 배열을 재할당 한다.
// 인자로 사용하는 newCapacity는 언제나 2a이다.
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// MAXIMIM_CAPACITY는 230이다.
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// 새 해시 버킷을 생성한 다음 기존의 모든 키-값 데이터들을
// 새 해시 버킷에 저장한다.
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 모든 해시 버킷을 순회하면서
for (Entry<K,V> e : table) {
// 각 해시 버킷에 있는 링크드 리스트를 순회하면서
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 해시 버킷 개수가 변경되었기 때문에
// index 값(hashCode % M)을 다시 계산해야 한다.
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}보조해쉬 함수 사용
- 배열의 크기를 2배씩 늘리 경우 해쉬 버켓의 크기가 2^n 곱을 가지기 때문에 hashCode()의 하위특정 비트만 사용하게 되고 해쉬 충돌이 쉽게 발생할 수 있다.
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } - 따라서 다음과 같은 보조 해쉬 함수를 활용하여 균등한 분포를 만들어준다.
버켓의 링크드리스트 체인을 레드블랙트리로 변환
- 특정 버켓에 연결된 노드의 개수가 TREEIFY_THRESHOLD(8)을 넘어가게 되면 해당 링크드리스트를 레드블랙 트리로 변환한다.
- 이렇게 하면 상대적으로 해쉬 충돌이 많이 일어나서 한 해쉬버켓에 여러 노드가 들어와도 O(N)에서 O(logN)으로 어느정도 최적화 할 수 있다.
Fail Fast