HashMap 동작원리 및 충돌해결

도입

이번 포스팅에서는 HashMap의 동작원리와 Hash 충돌해결에 대해 정리할 예정이다.

---

개념

HashMap은 Key-Value가 1:1로 맵핑되는 자료구조이다. 맵핑으로 인해 삽입, 삭제, 검색이 평균적으로 O(1)인 자료구조이다.

---

원리

Key는 Object를 지원하기 때문에 완전한 해시 함수(perfect hash functions)가 아니다.

(hashCode() 결과 자료형은 int ∴32비트 정수 자료형으로 2의 32승까지 표현 가능, 그러나 Object는 더 많은 경우의 수 포함)

아래와 같이 hashing으로 hash값 가공

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l336

∴ HashKey 충돌 가능성 존재

이를 해결하기 위해 내부적으로 Node 2차원 배열 table 존재

transient Node<K,V>[] table;
// http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l395

 

충돌 시, Seperate Chainning 방법으로 현재 Value의 다음 Value를 연결하는 방식으로 해결

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); // 새로운 Node 생성해 연결
			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;
	}
}
// http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l641

그럼에도 불구하고 최악의 경우는 O(n)이 될 수 있다.

do {
	if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
		return e;
} while ((e = e.next) != null);
// http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l580

 

 

#HashMap #면접