[스터디] HashMap에서 key가 충돌나면 어떻게 해야 하는가?

key는 무한함에 비해 bucket의 사이즈는 유한하다. 또한 key가 서로 다르더라도 확률상 해시 함수가 동일한 값을 반환할 수도 있다. 동일한 해시값을 반환하게 되면 value를 저장할 bucket의 인덱스가 동일할 것이고 이는 문제가 된다.

 

이처럼 다른 key 값으로 동일한 해시값이 나오는 걸 해시 충돌(Hash collision)이라고 한다. 이는 해시맵의 성능을 떨어뜨리는 주범이며 해시 함수가 해결해야 하는 문제이다.

 

하지만 해시 충돌은 불가피하며 단지 확률을 낮춤으로써 충돌을 최대한 피하는 것이 최선의 방법이다. 충돌을 피하는 방법은 잠시 후 알아보고 먼저 충돌 시의 대안을 먼저 알아보자. 일단 충돌이 난다고 어느 한 value를 버릴 순 없다.

 

 

[체이닝(chanining)]

첫 번째로, 해시 충돌이 발생해 동일한 인덱스가 나오면 해당 인덱스에 추가로 이어서 저장하는 방법이 있다. 25번 인덱스에 이미 값이 존재한다고 가정해 보자. 그리고 나는 "Bird"-"parrot" 쌍을 해시맵에 저장하고 싶다. 그래서 "Bird"라는 key를 해시 함수에 넣었더니 인덱스로 25가 나와 충돌이 일어난 상황이다.

 

이 때  value가 저장되는 공간을 정적 배열 또는 가변 배열로 구현하여, 충돌 시 기존 value에 이어서 다음 요소에 추가하도록 하면 충돌을 해결할 수 있다. 즉 버켓의 각 요소가 배열이다. 이러한 방법을 연쇄적으로 연결한다 해서 체이닝(chaining)이라 한다.

 

이 경우 Bird의 value인 "parrot"에 접근하기 위해선 해싱을 통해 인덱스를 얻고 "parrot"이 나올 때까지 순차적으로 탐색해야 할 것이다. 이는 bucket의 인덱스엔 상수 시간으로 접근하지만, 해시 충돌로 인해 요소가 여러개일 경우 일치하는 value를 찾기 위해선 요소를 하나씩 확인해야 한다. 따라서 최악의 경우 선형 시간이 걸릴 것이다.

 

정말 최악의 경우를 생각해보면 이해하기 쉽다. bucket의 사이즈가 1이라면 모든 value가 하나의 인덱스에 연쇄적으로 저장될 것이고, 이는 pair의 개수인 n번 만큼 돌기에 시간복잡도는 O(n)이 될 것이다. 그러나 bucket을 이렇게 설계하는 경우는 없고 충분한 크기로 설계하고 다른 방법으로도 해시 충돌을 피하기 때문에 보통 해시맵 및 해시테이블의 key로 부터 value로의 접근 시간 복잡도는 O(1)으로 말한다.

 

 

[개방 번지화(open addressing)]

다른 방법으로는 개방 번지화(open addressing) 또는 개방 주소법이라고도 한다. 용어만 들어보면 어려울 수 있는데 사실 개념은 간단하다. 해시 충돌이 발생하면 그 결과(인덱스)를 버리고 다른 인덱스(비어있는)에 value를 할당하는 방법이다. 즉 다음과 같이 25번 인덱스에 이미 요소가 존재할 경우 비어있는 다른 인덱스를 찾아 그 곳에 저장하는 방식을 말한다. 이는 당연히 규칙이 있어야 할 것이다. 그래야 매번 동일한 결과를 기대할 수 있으니까.

 

개방 주소법에서 비어있는 인덱스를 탐색하는 방법으로는 여러가지가 있으며 몇가지만 소개하면 다음과 같다.

 

선형 탐사(Linear probing): 고정된 폭(인덱스)으로 탐사한다. 위의 bucket에서 25번에서 충돌이 났을 경우 바로 다음 인덱스를 확인한다. 이 방법은 value가 특정 부분에 밀집되는 클러스터(cluster) 현상이 발생하기 쉽다. 따라서 많은 데이터가 밀집되어 있을 경우 탐색 시간이 길어진다는 단점이 있다.

 

제곱 탐사(Quadratic probing): 선형 탐사와 비슷한데 폭을 단순히 선형으로 증가시키는 것이 아닌 이차식을 통해 인덱스를 구해 한 곳에 데이터가 집중되지 않도록 한다. 하지만 이 또한 같은 해시값이 나온다면 동일한 과정을 거치기 때문에 2차 클러스터가 발생할 수 있다. 

 

이중 해싱(Double hashing): 해시 충돌이 발생할 경우 또 다른 해시 함수를 사용하여 증가 폭을 구한다. 증가폭만큼 인덱스를 증가시키며 비어있는 곳을 탐색하는 것이 이중 해싱이다.

 

다음은 bucket에 요소가 차지한 비율(LF)에 따른 탐사 방법별 성공 및 실패의 평균을 나타낸 표이다. 요소가 bucket을 차지하는 비율이 80% 부터는 fail이 눈에 띄게 많아지는 것을 볼 수 있다. 특히 선형 탐사가 제일 많은 실패율을 보여주고 제곱 탐사와 이중 해싱은 비슷한 비율을 보여준다. 

 

 

[chaining vs open addressing]

그럼 체이닝과 오픈 어드레싱 중 어떤 방법이 더 좋을까?

 

체이닝을 제외한 오픈 어드레싱 방법은 70% 정도까진 적당한 효율성을 보여준다. 즉 오픈 어드레싱을 사용할 경우 이상적인 data의 개수는 bucket의 70% 이하로 유지해야 한다는 의미이다. 그 이후로부턴 resizing을 통해 bucket의 크기를 늘리고 모든 요소를 갱신해야할 것이다.

 

체이닝은 90% 까진 괜찮은 효율을 보여주고 그 뒤부턴 동일하게 효율이 좋지 않다. 하지만 체이닝은 연결리스트 또는 벡터와 같은 또 다른 자료구조를 추가로 사용하기 때문에 일차적으로 메모리를 많이 차지할 수 있으며, 메모리 할당에 대한 오버헤드가 발생할 수 있고, 추가로 저장되는 데이터들은 bucket의 인덱스와는 또 다른 메모리이기 때문에 locality(지역성)가 좋지 않아 cpu cache에 의해 빠르게 참조되지 않을 수 있다.

 

정리해보면 bucket 사이즈와 비교했을 때 들어오는 데이터가 적을수록 오픈 어드레싱이 유리하고, 데이터가 bucket을 많이 차지한다면 체이닝이 더 좋은 방법이라고 할 수 있다.

 

 

[해시 충돌 최소화 방법]

다음으론 해시 충돌을 최소화 시키는 방법에 대해 알아보자. 사실 제일 중요한 것이 해시 충돌을 최소화시키는 것이다. 해시 충돌을 최소화시키는 방법엔 여러가지가 있는데 첫 번째로 해시함수를 잘 설계하던지 잘 만들어진 해시함수를 사용하는 것이다. 해시 함수가 제일 중요하다. 잘 설계되지 못한 해시함수는 동일한 해시값을 반환할 확률이 높다.

 

두 번째로 bucket의 size가 충분히 커야한다. 이상적인 bucket 사이즈는 들어오는 key의 개수가 bucket size의 ~40% 정도일 때라고 한다. bucket의 size가 10인데 들어오는 key의 개수가 20개라면 당연히 충돌이 많이 일어날 수 밖에 없다.

 

세 번째론 bucket의 크기를 소수(prime number)로 설계하는 것이다. 여기서 소수는 2, 3, 5, .. 등과 같은 1을 제외하고 1과 자신으로만 나누어 떨어지는 수를 말한다. 그 이유는 수학적으로 분석해보면 이진수로 볼 때 소수가 어떤 계산으로부터 나올 확률이 훨씬 적기 때문이라고 한다.  

 

결론적으로 잘 만들어진 해시 함수를 사용하고, bucket 사이즈가 데이터를 담기에 충분히 크고 bucket의 크기가 소수라면 웬만해선 O(1)의 성능을 얻을 수 있다.

 

성능이 좋은 해시 함수로 djb2라는 해시 함수가 있는데 구글에서 쉽게 코드를 얻을 수 있다. 다시 한번 강조하지만 잘 만들어진 해시 함수를 사용하는 것이 중요하다.