[JAVA/Hash] JAVA의 HashMap과 충돌(Collision) 문제

Hashmap이라는 자료구조를 java에서 내부적으로 어떻게 저장되는지, 해시 충돌과 관련된 내용입니다.

 

# HashMap & HashTable

두 구조 모두 Hash를 사용해 Key, value 형태로 저장되는 자료구조입니다.

 - HashMap : JDK 2.0에서 부터 생긴 API로 현재까지 꾸준히 업데이트 되고 있습니다.

 - HashTable : JDK 1.0부터 있던 API로 현재는 자주 사용되지 않습니다.

가장 큰 차이로는 동기화(Synchronization)의 차이입니다. 먼저 HashMap의 경우 동기화를 지원하지 않기 때문에 멀티 쓰레드 환경에서 문제가 발생할 수 있습니다. HashTable의 경우 동기화를 지원해 멀티 쓰레드 환경에서 안전합니다.

하지만 현재 ConcurrentHashMap이라는 API를 제공하기 때문에 동기화 문제로 HashTable을 사용할 필요는 없을 것 같습니다.

또한, HashMap의 경우 HashTable과 달리 보조 해시 함수를 사용하기 때문에, HashTable보다 성능상의 이점을 갖고 있습니다.

 

# HashMap의 작동 방식?

HashMap의 내부는 배열로 이루어져 있습니다. HashMap은 Key-Value 형식이기 때문에, Key는 배열의 인덱스가 되고, 이 배열을 해시 버킷이라고 부릅니다.

먼저 key값을 hashcode()라는 메소드를 통해 int형의 해쉬값으로 바꾸고 이를 버킷의 사이즈인 M으로 나눈 나머지가 해시 버킷의 진짜 인덱스가 됩니다. int index = hashcode() % M;

바로 이 버킷의 사이즈 때문에 저장하는 데이터가 많아진다면 1/M의 확률로 해시 값이 같아질 수 있습니다. 물론 버킷의 사이즈를 크게하면 일부 해결은 되지만, 아무리 크게 한다고 해도 int형의 범위인 2^32를 넘을 수 없기 때문에 String이나 POJO에 대해 완벽히 안전한 해시 값을 생성하는 것은 불가능합니다.

바로 이 때문에 실제는 다른 key값이지만 해시값이 같아지는 해시 충돌 (Hash collision) 문제가 생깁니다.

 

# Hash Collision 해결법

우선 JAVA에서는 Hash 버킷의 크기를 메모리 절약을 위해 정수의 표현 범위보다 작은 M개가 있는 배열을 사용합니다. 또한 같은 hash값을 가질 때 해결을 위한 방법은 크게 두가지가 있습니다.

 - Open Addressing : 데이터를 삽입하려는 해시 버킷이 사용중이면 다른 비어있는 해시 버킷을 찾아 삽입하는 방법
     - Linear Probing : 순차적으로 비어있는 버킷을 찾을 때까지 진행
     - Quadratic Probing : 이차함수를 이용해 버킷의 위치를 찾는 방법

 - Seperate Chaining : 해시 값이 같을 때, Linked List나 Tree (Red-Black Tree)를 사용해 해결하는 방법
     - Linked List : 각각의 버킷을 Linked List의 첫부분(head)로 충돌시 list add하는 방식
     - Red Black Tree : 기본적인 방법은 list와 같지만, 자료구조만 Tree로 하는 방법

자바에서는 Seperate Chaining을 사용하는데, 그 이유는 Open Addressing의 경우 데이터 삭제시 효율적인 처리가 어려워서 입니다. Hashmap의 경우 remove()가 빈번할 수 있는데, OpenAddressing의 경우 버킷을 채운 밀도가 높아질 수록 worst case 발생 확률이 높아질 수 밖에 없습니다. Seperate Chaining의 경우 보조해시함수를 사용해 충돌이 잘 발생하지 않도록 조정할 수 있습니다.

자바 8부터는 Seperate Chaining에서 데이터 개수가 많아지면 LinkedList대신 Tree를 사용해 성능적으로 더 좋아졌습니다.
즉, 처음에는 해시 버킷을 LinkedList로 하고 8개의 Key-Value쌍이 모이면 저장 구조를 Tree로 변경한다. 만약 데이터가 삭제되어 개수가 6개가 되면 다시 LinkedList로 바꾼다. 이렇게 8과 6이라는 2차이의 Threshold를 두면 차이가 1일때의 삽입/삭제에 따라 더욱 빈번하게 자료구조가 변경되는 일이 반복되어 성능저하가 발생할 수 있기 때문입니다.

 

# 해시 버킷 동적 확장과 보조 해시 함수

해시 버킷의 개수가 적으면 메모리를 아낄 수 있지만 해시 충돌로 인해 성능상의 손실이 발생합니다. 그래서 Hashmap은 데이터 개수가 일정 이상이 되면 버킷의 개수를 두배로 늘리고, 버킷의 최대 개수는 2^30개 입니다. 버킷의 크기를 두배로 확장하는 임계점은 밀도가 3/4를 넘어서는 시점입니다. 그런데 이것에는 결정적인 문제가 있는데, 해시 버킷의 개수는 2의 지수승 형태(2^a)로 증가되기 때문에 X.hashCode() % M 을 계산할때 하위 a개의 비트만 사용하게 됩니다. 이 때문에 해시함수가 32비트 영역을 잘 만들었다 하더라도 해시 값이 쉽게 충돌이 발생할 수 있습니다. 이 때문에 보조 해시 함수가 필요합니다.

보조해시함수는 키의 해시 값을 변형해, 충돌 가능성을 줄이는 것으로 이는 JDK 1.4부터 처음 등장했습니다.

자바 8부터는 상위 16비트 값을 XOR연산하는 더욱 단순해진 보조 해시 함수를 사용하는데, 그 이유는 트리를 함께 사용하므로 충돌 발생 가능성이 완화되었고, 최근 해시 함수는 균등하게 분포되도록 잘 만들어지는 경향이 높기 때문입니다.

 

# String 객체에 대한 해시 함수

Java내에서 String객체에 대한 해시 함수는 별도로 있으며, 이 내용은 생략하도록 하겠습니다.

 

 

출처 : d2.naver.com/helloworld/831311