Hash Map과 Hash Collision 문제

Hash Map & Hash Table

 두 구조 모두 Key, Value로 데이터를 저장하는 자료구조입니다.

• Hash Map : JDK 2.0부터 생긴 API로 꾸준히 업데이트 되고 있습니다.
• Hash Table : JDK 1.0부터 있던 API로 현재는 사용되고 있지 않습니다.

두 자료구조의 가장 큰 차이로는 동기화의 차이가 있습니다.

HashMap의 경우 동기화를 지원하지 않기 때문에 멀티 쓰레드 환경에서 문제가 될수 있습니다. 반면에 HashTable의 경우 동기화를 지원하여 멀티 쓰레드 환경에서 안전합니다.

 

물론, 현재 동기화를 지원하는 ConcurrentHashMap이라는 API를 지원하기 때문에 동기화 때문에 HashTable을 사용할 필요는 없습니다.

Hash Map 작동방식

Hash Map은 key-value구조로 이루어져 있습니다. 내부적으로 Node<K,V>[] 형태 즉, 배열로 이루어져 있습니다.

이 배열을 Hash Bucket이라고 부릅니다.

또한 배열의 Index는 key값에 의해서 결정되고, Index는 key값에서 hashCode()함수를 적용하고, M으로 나눈 나머지로 선정합니다.

즉, Index = key.hashcode() % M으로 표현될수 있습니다.

그리고 이 버킷의 사이즈 때문에, 데이터가 많아진다면 1/M확률로 해시값이 같아질수 있습니다. 물론 Hash Bucket의 사이즈를 증가시키면 Collision에 대해서 일정부분 자유롭지만 완벽한 자유롭지는 못합니다.

Hash Colision 해결법

Hash Collision은 같은 Hash값을 가진 경우에 같은 장소에 저장하려고 하기때문에 발생하는 현상입니다.

이러한 같은 Hash값을 가질경우 해결하기 위한 두가지 방법이 존재합니다.

 

1. Open Addressing 방법

해당 방법은 데이터를 삽입하려는 Hash Bucket이 사용중이라면, 다른 비어있는 HashBucket을 찾아 삽입하는 방식을 의미합니다.

해당 방법은 크게 두가지 방법으로 나뉠수 있습니다.

1.1) Linear Probing

순차적으로 탐색을 진행하여 비어 있는 HashBucket을 만나게 될시 해당 Bucket에 삽입하는 방식을 의미합니다.

1.1) Quadratic Probing

이차 함수를 이용하여 버킷의 위치를 찾는 방식을 의미합니다.

 

2. Seperate Chaning 방법

Hash값이 같은 경우, Linked List나 Tree(Red-Black Tree)를 사용하여 해결하는 방식입니다.

1.1) Linked List 

각각의 Bucket을 LinkedList의 첫부분으로 하고 충돌시 List add 하는 방식

1.1) Tree

기본적인 방법은 LinkedList와 동일하지만, 자료구조를 Tree로 하는 방식

 

그렇다면 Java의 HashMap은 어떠한 방식을 선택하고 있을까?

자바8에서는 Seperate Chaning방식을 선택하고 있다. 그 이유는 HashMap의 경우, 삭제가 빈번할수밖에 없는데 그럴 경우, Open Addressing방식은 HashMap의 Bucket의 밀도가 높아질수록 지속적으로 Key에 맞는 Bucket의 위치를 찾아야 하므로 Worst Case 발생확률이 높기 때문입니다.

반면에, Seperate Channing의 경우, 보조 해시 함수를 사용해서 충돌이 잘 발생하지 않게끔 조절이 가능하기 때문입니다.

또한, Seperate Channing 방식은 8개 이상의 Key - Value가 존재시 자료구조를 Linked List에서 Tree구조로 변화시켜서 성능이 더 좋아졌기 때문입니다.

Hash Bucket 동적 확장과 보조 Hash 함수

Hash 버킷의 개수가 적으면 메모리를 아낄수 있지만, 충돌로 인해서 성능상의 손실이 발생합니다.

그래서 HashMap은 일정 수준 이상의 데이터가 차게 되면 Bucket의 개수를 2배로 늘립니다.(여기서 버킷의 최대갯수는 2^30 입니다).

버킷을 2개로 확장하는 임계점은 밀도가 3/4를 넘어서는 시점입니다. 또한 Bucket의 개수가 2지수승으로 증가하기 때문에, x.HashCode() % M을 시전할 경우 하위 a(2^a의 Bucket 가정)개의 비트만 사용될 경우가 존재합니다.

이때문에 Hash함수가 32비트 영역을 잘 만들었다고 하더라도 충돌의 발생 가능성이 존재하고 이를 보완하기 위해서 Hash 보조함수가 필요합니다.

 

보조함수는 Hash값을 변경하여 충돌을 줄이는 것이 목적으로, 자바에서는 XOR을 이용한 연산을 사용합니다.

상위 16비트를 XOR하는 더욱 단순해진 보조함수를 사용하는데, 이는 트리를 사용해 충돌 가능성이 완화되었고, 최근에는 더욱 정교한 Hash함수를 사용하기 때문입니다.