해쉬충돌을 해결하는 몇 가지 방법

해쉬충돌은 해쉬알고리즘을 사용하는 자료구조에겐 성능상 치명적이다.

 

해쉬알고리즘을 사용하는 것의 목적은 자료를 정수로 표현해 인덱스를 구하기 위함인데, 해쉬충돌이 발생하면 인덱스가 충돌되기 때문에 O(1)의 시간복잡도를 유지할 수 없다.

 

정말 최최최악의 경우엔 O(N)의 시간복잡도를 갖게 된다.

 

해쉬 충돌을 해결하는 여러가지 방법을 알아보려한다.

 

Open Addressing

개방주소법이라고 불리는 이 방식은 해쉬 충돌이 발생하면 비어있는 공간을 찾아가는 알고리즘이다.

 

Open Addressing는 크게 세 가지로 나뉜다.

 

1. Linear Probing

 

Linear Probing 방식은 해쉬 충돌이 발생하면 비어있는 버킷을 발견할 때 까지 선형적으로 버킷을 검색한다.

 

이는 H(key,i) = (H_qp(key) + i) % Bucket Size 라는 수식으로 표현할 수 있다.

 

- Function H() : 해쉬 인덱스를 구하는 함수

 

- Function H_qp(key) : 키 값의 해쉬값을 구하는 함수

 

- i : 충돌 횟수

 

이 함수는 충돌이 발생하면 i를 선형적으로 증가시키면서 빈 버킷을 찾는다.

 

버킷은 10개로 설정하고 11과 24가 인덱스 1과 4에 저장돼있는 상황이다.

 

	11			24
0	1	2	3	4	5	6	7	8	9

 

 

여기서 44라는 숫자가 들어오면 해쉬 충돌이 발생한다.

 

Linear Probing은 인덱스 4에서 비어있는 버킷이 i값을 선형적으로 증가시킨다.

 

즉 44는 5번 인덱스에 저장된다.

 

	11			24	44
0	1	2	3	4	5	6	7	8	9

 

하지만 이 방식은 해쉬충돌이 발생한 인덱스 4 주변으로 지속적인 충돌이 발생하게되고, 특정 구간에 데이터가 모여들게되는 군집화가 발생하기 쉽다.

 

군집화가 발생하면 검색이나 삽입시간이 늘어나 성능이 떨어지기 쉽다.

 

2. Qudratic Probing

 

Qudratic Probing은 이름에서 드러나듯 해쉬 함수를 단순 선형증가 형식이 아닌, 충돌횟수를 제곱시켜 빈 버킷을 찾는다.

 

H(key,i) = (H_qp(key) + i^2) % Bucket Size

 

실제로는 i^2보다 더 복잡한 함수를 적용한다.

 

아래와 같은 상황에서 다시 44를 삽입해보면

 

	11			24	55
0	1	2	3	4	5	6	7	8	9

 

1. 44 % 10 = 4 [해쉬충돌]

 

2. (44 + 1) % 10  = 5 [해쉬충돌]

 

3. (44+2^2) % 10 = 8 [빈 버킷 발견]

 

	11			24	55			44
0	1	2	3	4	5	6	7	8	9

 

 

이렇게 충돌 횟수를 제곱시키면 해쉬인덱스를 흩어지게 만들어 군집화를 발생시키지 않는다.

 

하지만 94를 삽입하는 연산을 진행하면 4에서 해쉬 충돌, 5에서 해쉬 충돌, 8에서 해쉬 충돌이 발생하게되고

 

해쉬충돌이 연쇄적으로 발생하는 문제점이 있다.

 

3. Double Hasing

 

H(key,i) = H_1st(key) + i * H_2st(key) 

 

Double Hasing은 위와 같이 2가지 해쉬 함수를 적용해 해쉬인덱스를 찾는 방식이다.

 

해쉬인덱스를 더 넓게 퍼트릴 수 있는 방식이지만 주의해야할 점이 있다.

 

버킷의 크기와 두번째 해쉬함수가 뱉어내는 값이 서로소여야 한다는 것인데 예시를 들어보자.

 

44라는 데이터를 첫 번째 해쉬함수에 넣고 0이라는 값을 뱉어냈고, 두 번째 해쉬 함수는 4라는 값을 뱉어 냈을 때

 

해쉬 충돌이 발생하면 0, 4, 8, 12, 16 ,,, 으로 특정 값들만 해쉬 인덱스가 된다.

 

즉 0 4 2 6 으로만 버킷에 접근하게 돼 모든 버킷에 접근할 수가 없게 된다.

 

Open Addressing의 또 다른 문제

Open Addressing은 삭제연산이 일어났을 때 삭제한 자리에 마킹을 해주지 않으면 중복된 값이 들어갈 수 있다.

 

	11			24	55			44
0	1	2	3	4	5	6	7	8	9

 

예시는 Qudratic Probing 방식으로 해쉬값을 구한다고 전제한다.

 

위 자료구조에서 55를 삭제해보자.

 

	11			24				44
0	1	2	3	4	5	6	7	8	9

 

여기서 중복된 값인 44를 새롭게 삽입해보면 첫 번째 해쉬 충돌이 인덱스 4에서 발생하고 다시 해쉬 함수를 적용하면 5번인덱스에 값이 들어가게 된다. 8번 인덱스에 44라는 값이 있는데도 말이다.

 

	11			24	DELETE			44
0	1	2	3	4	5	6	7	8	9

 

DELETE라는 마킹을 해주게되면 5번인덱스가 비어있다는 것을 확인하더라도 다시 해쉬함수를 적용해서 다음 인덱스에

 

같은 값이 없는 지를 확인하는 절차를 거쳐야한다. 무시할 수 없는 오버헤드가 발생하게 되는 것이다.

 

Java가 해결한 방법

자바는 Open Addressing 방식을 사용하지 않고 단계별로 문제를 해결한다.

 

1. 버킷에 들어온 데이터의 비율이 75%를 넘으면 버킷 사이즈를 두 배 증가시킨다.

 

버킷 크기를 늘린다는 의미는 해쉬인덱스를 더 많이 갖겠다는 의미다. 충돌을 해결하는 가장 단순한 방법이지만 모든 자료를 재해싱(Rehasing)해야한다. 데이터베이스 샤딩에서 샤드를 하나 늘릴 때 마다 리샤딩하는 것과 똑같은 의미다.

 

2. Separte Chaining [Linked List]

 

지난 포스팅에서 알아봤듯 해쉬충돌이 발생하면 기존 버킷에 빈 공간을 찾지 않고 같은 해쉬인덱스에 링크드 리스트 방식으로 단순 연결한다.

 

하지만 지속적으로 해쉬충돌이 발생하면 시간 복잡도가 O(N)이 될 수 있는데 자바는 일정 임계치 이상 노드가 연결되면 레드-블랙 트리로 자료구조를 변환한다.

 

레드-블랙 트리는 시간 복잡도가 O(logN)으로 O(N)보다 훨씬 빠르다.

 

레드-블랙 트리로 변환되기 위해서는

 

 

한 버킷의 연결된 노드 수가 TREEIFTY_THRESHOLD(8) 보다 같거나 커야 트리로 변경된다.(첫 번째 노드를 제외했기 때문에 -1이 붙는다)

 

하지만 treeifBin 함수에 들어가보면 또 다른 조건이 하나 더 존재한다.

 

 

전체 버킷 사이즈가 MIN_TREEIFY_CAPACITY(64) 보다 작으면 트리구조로 변경하지 않고 버킷 사이즈를 단순히 증가 시킨다.

 

정리하자면

 

버킷 전체 사이즈가 64보다 크고 한 버킷에 연결된 노드가 8개 이상이라면 레드-블랙 트리로 변경된다.

 

레드-블랙 트리는 다음 포스팅에서 알아보려한다.