Hash Collision(해시 충돌)이란?
동일하지 않은 어떤 객체 X와 Y가 있을 때, X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는 해시 함수는 완전한 해시 함수(perfect hash functions)라고 합니다.
Integer, Long, Double 같은 Number 객체는 객체가 나타내는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수를 대상으로 삼을 수 있지만, String이나 POJO(plain old java object)에 대해 완전한 해시 함수를 제작하는 것은 사실상 불가능해 해시 충돌이 일어날 수 있습니다. 또한 Java의 hashcode() 함수는 리턴값을 int로 반환하기 때문에 2^32개의 객체를 다르게 저장할 수 있지만 키 값의 범위, 즉 객체의 수가 이보다 큰 경우에도 해시 충돌이 일어날 수 있습니다.
객체의 hashCode() 값이 다르면 해시 충돌은 무조건 일어나지 않는가?라고 하면 또 그렇지는 않습니다. 아래 HashMap에서 인덱스를 정하는 방법을 보면 이유를 알 수 있습니다.
int index = X.hashCode() % M;이때 M은 배열의 크기로 hashCode의 값이 다르더라도 M 모듈러 연산을 하면서 한번 더 해시 충돌이 일어날 수 있습니다.
해시 충돌 전략
해시 충돌이 일어나도 키값 쌍데이터를 안정적으로 저장하고 조회할 수 있도록 하는 대표적인 방법으로 두 가지가 있습니다.
open addressing(개방주소법)
추가 메모리를 사용하지 않고 비어있는 해시 버킷 공간을 활용합니다. open addressing 방식은 찾은 해시값의 버킷이 이미 사용중인 경우 정해진 규칙에 따라 비어있는 다른 버킷을 결정해 해당 버킷에 데이터를 보관하는 방법으로, 대표적으로 3가지가 있습니다.
- 선형 탐색(Linear Probing): 해시충돌 시 다음 버킷에, 다음 버킷이 비어있지 않다면 몇 개 건너뛰어 데이터를 삽입합니다.
- 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입합니다.
- 이중 해시(Double Hashing): 해시충돌 시 해시를 한번 더 적용해서 나온 버킷에 데이터를 삽입합니다.
Separate Chaining(분리연결법)
동일한 버킷으로 접근시, 추가메모리를 사용해 데이터를 연결해서 관리합니다. 해시값의 버킷이 이미 사용중인 경우 링크드 리스트를 만들어 순차적으로 저장합니다. 탐색할 때는 HashCode 기반이ㅡ 비교를 한 후 Equals()가 false라면 찾거나 리스트가 끝날 때까지 다음 노드를 탐색합니다.
index에 들어가있는 첫 인자는 링크드 리스트의 head 부분이 됩니다.
장단점
open addressing
연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋습니다.데이터가 많아지면 캐시 적중률이 떨어지고 삭제가 어려울 수 있습니다.
Separate Chaining
연결 리스트만 사용하면 되기 때문에 계산식을 사용할 필요가 없습니다.데이터의 수가 많아지면 동일한 버킷에 연결되는 데이터가 많아지며 캐시 효율성이 감소합니다.