충돌 해결 방법은 해시 테이블의 중요한 부분이며, 성능과 저장 공간 효율성에 영향을 미칩니다.
아래에서 자주 사용되는 충돌 해결 방법과 그 차이를 설명하겠습니다.
1. 선형 조사법 (Linear Probing)
- 방법: 충돌이 발생하면 해시 테이블의 다음 빈 슬롯을 순차적으로 탐색하여 데이터를 저장.
- 예시: 만약 h(k)=kmod 11h(k) = k \mod 11에서 충돌이 발생하면, 그 다음 슬롯을 확인하는 방식으로 충돌을 해결합니다.
장점:
- 간단한 구현.
- 데이터가 해시 테이블 내에 하나의 연속된 메모리 공간에 저장되므로 메모리 캐시 효율이 좋음.
단점:
- 클러스터링(한 곳에 연속적인 데이터가 몰리는 현상)이 발생할 수 있어, 테이블의 로딩이 높아질수록 성능이 급격히 저하됨.
- 데이터가 연속된 공간에 저장되므로, 클러스터의 끝까지 확인해야 할 수 있음.
2. 이차 조사법 (Quadratic Probing)
- 방법: 충돌이 발생하면 1, 4, 9, 16 등 제곱수만큼의 간격으로 슬롯을 조사.
- 예시: 충돌이 발생할 경우, h(k)h(k)에서 1, 4, 9, 16 등의 간격으로 빈 슬롯을 찾습니다.
장점:
- 클러스터링을 어느 정도 방지할 수 있어 선형 조사법보다 나은 성능을 보임.
- 메모리 내에서 데이터를 근처에 저장할 확률이 높아 캐시 효율이 상대적으로 좋음.
단점:
- 여전히 클러스터링의 문제가 완전히 해결되지는 않음.
- 탐색 범위가 넓어질 경우 복잡도가 증가함.
3. 이중 해싱 (Double Hashing)
- 방법: 두 개의 다른 해시 함수를 사용하여 충돌이 발생했을 때 두 번째 해시 함수의 결과로 이동할 위치를 결정.
- 예시: h1(k)=kmod 11h_1(k) = k \mod 11, h2(k)=1+(kmod 10)h_2(k) = 1 + (k \mod 10)와 같이 두 해시 함수를 사용하는 방식.
장점:
- 클러스터링 문제를 크게 감소시키며, 데이터가 더 고르게 분포됨.
- 충돌이 발생할 때 이동하는 거리가 다양해 효율성이 높아짐.
단점:
- 두 개의 해시 함수가 필요하여 계산이 상대적으로 복잡.
- 해시 함수의 선택이 중요하며, 적절하지 않으면 성능 저하가 발생할 수 있음.
4. 체이닝 (Chaining)
- 방법: 각 버킷에 연결 리스트를 두어 동일한 해시 값을 가진 데이터를 모두 저장.
- 예시: h(k)=kmod 11h(k) = k \mod 11에서 충돌이 발생하면, 해당 버킷에 연결 리스트를 사용하여 데이터를 추가.
장점:
- 충돌이 많이 발생해도 쉽게 해결 가능하며, 해시 테이블이 꽉 차더라도 성능 저하가 상대적으로 적음.
- 해시 함수 설계에 덜 민감하며, 확장이 쉽고 유연함.
단점:
- 연결 리스트를 사용하므로, 추가적인 메모리 공간이 필요.
- 최악의 경우 시간 복잡도가 O(n)O(n)으로 증가할 수 있음.
5. Robin Hood 해싱
- 방법: 충돌이 발생하면 '먼' 키와 '가까운' 키를 비교하여 더 멀리 떨어져 있어야 하는 키를 우선적으로 저장.
- 예시: 충돌 시 테이블 내에서 더 멀리 있는 데이터가 더 가까운 곳으로 교체될 수 있음.
장점:
- 해시 테이블이 고르게 분포될 가능성이 높으며, 특정한 조건 하에서 선형 조사법보다 나은 성능을 보일 수 있음.
- 데이터의 분포가 매우 고르게 되어, 평균 탐색 시간이 줄어듦.
단점:
- 구현이 복잡하며, 충돌 시 데이터의 이동이 많이 발생할 수 있음.
- 충돌 발생 시, 키가 많은 곳에서 상대적으로 많은 자원이 소모될 수 있음.
비교 요약
충돌 해결 방법시간 복잡도 (탐색)메모리 효율성클러스터링 문제구현 난이도
| 충돌 해겳 방법 | 시간 복잡도 (탐색) | 메모리 효율성 | 클러스터링 문제 | 구현 난이도 |
| 선형 조사법 | 평균 O(1)O(1), 최악 O(n)O(n) | 높음 | 심각 | 낮음 |
| 이차 조사법 | 평균 O(1)O(1), 최악 O(n)O(n) | 높음 | 중간 | 중간 |
| 이중 해싱 | 평균 O(1)O(1), 최악 O(n)O(n) | 높음 | 낮음 | 중간 |
| 체이닝 | 평균 O(1)O(1), 최악 O(n)O(n) | 낮음 (추가 메모리 필요) | 없음 | 낮음 |
| Robin Hood | 평균 O(1)O(1), 최악 O(n)O(n) | 높음 | 낮음 | 높음 |
결론
- 선형 조사법은 간단하지만 클러스터링 문제로 인해 성능 저하가 있을 수 있습니다.
- 이차 조사법은 클러스터링을 줄이지만 완전히 해결하지는 못합니다.
- 이중 해싱은 가장 강력한 방법 중 하나로, 충돌을 효율적으로 해결할 수 있습니다.
- 체이닝은 메모리를 추가로 사용하지만, 충돌이 자주 발생하는 환경에서 매우 효율적입니다.
- Robin Hood 해싱은 성능이 뛰어나지만 구현 복잡도가 높습니다.
따라서, 상황에 따라 가장 적합한 방법을 선택하는 것이 중요합니다. 예를 들어, 충돌이 많을 것으로 예상되는 경우에는 체이닝이나 이중 해싱을 고려하는 것이 좋습니다.
예제
이제 앞에서 주어진 예시의 키들 12,33,13,55,23,83,1112, 33, 13, 55, 23, 83, 11을 다양한 충돌 해결 방법으로 저장해보겠습니다. 해시 함수는 동일하게 h(k)=kmod 11h(k) = k \mod 11을 사용합니다.
1. 선형 조사법 (Linear Probing)
- 키 12:
h(12)=12mod 11=1h(12) = 12 \mod 11 = 1
-> 1번 버킷에 저장. - 키 33:
h(33)=33mod 11=0h(33) = 33 \mod 11 = 0
-> 0번 버킷에 저장. - 키 13:
h(13)=13mod 11=2h(13) = 13 \mod 11 = 2
-> 2번 버킷에 저장. - 키 55:
h(55)=55mod 11=0h(55) = 55 \mod 11 = 0
-> 0번 버킷 충돌 -> 1번 버킷 충돌 -> 2번 버킷 충돌 -> 3번 버킷에 저장. - 키 23:
h(23)=23mod 11=1h(23) = 23 \mod 11 = 1
-> 1번 버킷 충돌 -> 2번 버킷 충돌 -> 3번 버킷 충돌 -> 4번 버킷에 저장. - 키 83:
h(83)=83mod 11=6h(83) = 83 \mod 11 = 6
-> 6번 버킷에 저장. - 키 11:
h(11)=11mod 11=0h(11) = 11 \mod 11 = 0
-> 0번 버킷 충돌 -> 1번 충돌 -> 2번 충돌 -> 3번 충돌 -> 4번 충돌 -> 5번 버킷에 저장.
결과:
버킷 번호저장된 값
| 0 | 33 |
| 1 | 12 |
| 2 | 13 |
| 3 | 55 |
| 4 | 23 |
| 5 | 11 |
| 6 | 83 |
2. 이차 조사법 (Quadratic Probing)
이차 조사법은 충돌이 발생할 경우 12,22,32,…1^2, 2^2, 3^2, \dots로 이동하여 빈 슬롯을 찾습니다.
- 키 12:
h(12)=12mod 11=1h(12) = 12 \mod 11 = 1
-> 1번 버킷에 저장. - 키 33:
h(33)=33mod 11=0h(33) = 33 \mod 11 = 0
-> 0번 버킷에 저장. - 키 13:
h(13)=13mod 11=2h(13) = 13 \mod 11 = 2
-> 2번 버킷에 저장. - 키 55:
h(55)=55mod 11=0h(55) = 55 \mod 11 = 0
-> 0번 버킷 충돌 -> 0+12=10 + 1^2 = 1번 버킷 충돌 -> 0+22=40 + 2^2 = 4번 버킷에 저장. - 키 23:
h(23)=23mod 11=1h(23) = 23 \mod 11 = 1
-> 1번 버킷 충돌 -> 1+12=21 + 1^2 = 2번 버킷 충돌 -> 1+22=51 + 2^2 = 5번 버킷에 저장. - 키 83:
h(83)=83mod 11=6h(83) = 83 \mod 11 = 6
-> 6번 버킷에 저장. - 키 11:
h(11)=11mod 11=0h(11) = 11 \mod 11 = 0
-> 0번 충돌 -> 0+12=10 + 1^2 = 1 충돌 -> 0+22=40 + 2^2 = 4 충돌 -> 0+32=90 + 3^2 = 9번 버킷에 저장.
결과:
버킷 번호저장된 값
| 0 | 33 |
| 1 | 12 |
| 2 | 13 |
| 4 | 55 |
| 5 | 23 |
| 6 | 83 |
| 9 | 11 |
3. 이중 해싱 (Double Hashing)
두 번째 해시 함수는 h2(k)=1+(kmod 10)h_2(k) = 1 + (k \mod 10)을 사용합니다.
- 키 12:
h1(12)=12mod 11=1h_1(12) = 12 \mod 11 = 1
-> 1번 버킷에 저장. - 키 33:
h1(33)=33mod 11=0h_1(33) = 33 \mod 11 = 0
-> 0번 버킷에 저장. - 키 13:
h1(13)=13mod 11=2h_1(13) = 13 \mod 11 = 2
-> 2번 버킷에 저장. - 키 55:
h1(55)=55mod 11=0h_1(55) = 55 \mod 11 = 0, 충돌 ->
h2(55)=1+(55mod 10)=1+5=6h_2(55) = 1 + (55 \mod 10) = 1 + 5 = 6
-> 6번 버킷에 저장. - 키 23:
h1(23)=23mod 11=1h_1(23) = 23 \mod 11 = 1, 충돌 ->
h2(23)=1+(23mod 10)=1+3=4h_2(23) = 1 + (23 \mod 10) = 1 + 3 = 4
-> 4번 버킷에 저장. - 키 83:
h1(83)=83mod 11=6h_1(83) = 83 \mod 11 = 6, 충돌 ->
h2(83)=1+(83mod 10)=1+3=4h_2(83) = 1 + (83 \mod 10) = 1 + 3 = 4, 충돌 ->
다음 조사 위치: 6+4=106 + 4 = 10번 버킷에 저장. - 키 11:
h1(11)=11mod 11=0h_1(11) = 11 \mod 11 = 0, 충돌 ->
h2(11)=1+(11mod 10)=1+1=2h_2(11) = 1 + (11 \mod 10) = 1 + 1 = 2, 충돌 ->
다음 조사 위치: 0+2=20 + 2 = 2 충돌 -> 0+4=40 + 4 = 4 충돌 ->
다음 조사 위치: 0+6=60 + 6 = 6 충돌 -> 0+8=80 + 8 = 8번 버킷에 저장.
결과:
버킷 번호저장된 값
| 0 | 33 |
| 1 | 12 |
| 2 | 13 |
| 4 | 23 |
| 6 | 55 |
| 8 | 11 |
| 10 | 83 |
4. 체이닝 (Chaining)
체이닝은 각 버킷에 연결 리스트를 둬 충돌이 발생하면 해당 버킷에 여러 값을 저장합니다.
- 키 12:
h(12)=12mod 11=1h(12) = 12 \mod 11 = 1
-> 1번 버킷에 저장. - 키 33:
h(33)=33mod 11=0h(33) = 33 \mod 11 = 0
-> 0번 버킷에 저장. - 키 13:
h(13)=13mod 11=2h(13) = 13 \mod 11 = 2
-> 2번 버킷에 저장. - 키 55:
h(55)=55mod 11=0h(55) = 55 \mod 11 = 0
-> 0번 버킷의 연결 리스트에 추가. - 키 23:
h(23)=23mod 11=1h(23) = 23 \mod 11 = 1
-> 1번 버킷의 연결 리스트에 추가. - 키 83:
h(83)=83mod 11=6h(83) = 83 \mod 11 = 6
-> 6번 버킷에 저장. - 키 11:
h(11)=11mod 11=0h(11) = 11 \mod 11 = 0
-> 0번 버킷의 연결 리스트에 추가.
결과:
버킷 번호저장된 값 (연결 리스트)
| 0 | 33 → 55 → 11 |
| 1 | 12 → 23 |
| 2 | 13 |
| 6 | 83 |
비교 요약:
- 선형 조사법: 충돌이 발생할 때마다 순차적으로 빈 슬롯을 찾음.
- 이차 조사법: 충돌 시 제곱 간격으로 이동.
- 이중 해싱: 두 번째 해시 함수를 이용해 충돌을 해결.
- 체이닝: 충돌 시 해당 버킷의 연결 리스트에 추가.
5. Robin Hood
Robin Hood 해싱은 충돌 발생 시 데이터가 얼마나 멀리 떨어져 있는지를 기준으로, 더 '불리한' 데이터(즉, 더 멀리 떨어져 있어야 하는 데이터)를 우선적으로 처리하는 방식입니다. 즉, 키를 저장할 때 자신보다 더 멀리 떨어진 키가 있으면 그 키와 자리를 바꾸고, 그 자리를 찾습니다. 이를 통해 해시 테이블의 편향된 데이터 분포를 방지하는 것을 목표로 합니다.
단계별 과정:
- 키 12:
h(12)=12mod 11=1h(12) = 12 \mod 11 = 1
-> 1번 버킷에 저장. (현재 버킷 거리 = 0) - 키 33:
h(33)=33mod 11=0h(33) = 33 \mod 11 = 0
-> 0번 버킷에 저장. (현재 버킷 거리 = 0) - 키 13:
h(13)=13mod 11=2h(13) = 13 \mod 11 = 2
-> 2번 버킷에 저장. (현재 버킷 거리 = 0) - 키 55:
h(55)=55mod 11=0h(55) = 55 \mod 11 = 0
-> 0번 버킷 충돌 발생!
현재 33이 0번 버킷에 있는데, 버킷 거리가 0입니다.
55의 원래 위치는 0번이지만, 충돌이 발생했으므로 다음 버킷으로 이동합니다.-> 2번 버킷에서도 충돌 발생 (13이 저장되어 있음).
13의 버킷 거리는 0, 55의 버킷 거리는 2이므로, 55가 더 멀리 떨어진 값입니다.
따라서, 55와 13의 자리를 바꿉니다.
-> 55가 2번 버킷에 저장되고, 13은 다음 슬롯으로 이동. - -> 3번 버킷에 13 저장. (버킷 거리 = 1)
- -> 1번 버킷에서도 충돌 발생 (12가 저장되어 있음).
55의 버킷 거리는 1, 12의 버킷 거리도 1이므로 그대로 두고 다음 슬롯으로 이동. - 키 23:
h(23)=23mod 11=1h(23) = 23 \mod 11 = 1
-> 1번 버킷에서 충돌 발생 (12가 저장되어 있음).
23의 원래 위치는 1번이고, 12의 버킷 거리는 0이므로 그대로 두고 다음 슬롯으로 이동.-> 3번 버킷에서 충돌 발생 (13이 저장되어 있음).
13의 버킷 거리는 1, 55의 버킷 거리는 2이므로, 55가 더 멀리 떨어진 값입니다.
따라서, 55와 13의 자리를 바꿉니다.
-> 55가 3번 버킷에 저장되고, 13은 다음 슬롯으로 이동. - -> 4번 버킷에 13 저장. (버킷 거리 = 3)
- -> 2번 버킷에서 충돌 발생 (55가 저장되어 있음).
55의 버킷 거리는 2, 23의 버킷 거리는 1이므로, 55가 더 멀리 떨어진 값입니다.
따라서, 55와 23의 자리를 바꿉니다.
-> 23이 2번 버킷에 저장되고, 55는 다음 슬롯으로 이동. - 키 83:
h(83)=83mod 11=6h(83) = 83 \mod 11 = 6
-> 6번 버킷에 저장. (현재 버킷 거리 = 0) - 키 11:
h(11)=11mod 11=0h(11) = 11 \mod 11 = 0
-> 0번 버킷에서 충돌 발생 (33이 저장되어 있음).
11의 원래 위치는 0번이고, 33의 버킷 거리는 0이므로 그대로 두고 다음 슬롯으로 이동.-> 2번 버킷에서 충돌 발생 (23이 저장되어 있음).
23의 버킷 거리는 1, 11의 버킷 거리는 2이므로 그대로 두고 다음 슬롯으로 이동.-> 4번 버킷에서 충돌 발생 (13이 저장되어 있음).
13의 버킷 거리는 3, 11의 버킷 거리는 4이므로 그대로 두고 다음 슬롯으로 이동. - -> 5번 버킷에 11 저장. (버킷 거리 = 5)
- -> 3번 버킷에서 충돌 발생 (55가 저장되어 있음).
55의 버킷 거리는 2, 11의 버킷 거리는 3이므로 그대로 두고 다음 슬롯으로 이동. - -> 1번 버킷에서 충돌 발생 (12가 저장되어 있음).
12의 버킷 거리는 0, 11의 버킷 거리는 1이므로 그대로 두고 다음 슬롯으로 이동.
최종 결과:
버킷 번호저장된 값| 0 | 33 |
| 1 | 12 |
| 2 | 23 |
| 3 | 55 |
| 4 | 13 |
| 5 | 11 |
| 6 | 83 |
요약:
- Robin Hood 해싱은 충돌이 발생할 때, 현재 키가 저장되어 있는 슬롯에서 얼마나 멀리 떨어져 있는지를 고려하여 충돌을 해결합니다.
- 멀리 떨어진 키가 더 가까운 슬롯에 있는 키보다 우선하여 저장됩니다.
- 이를 통해 해시 테이블 내에서 데이터가 좀 더 고르게 분포되고, 긴 클러스터를 방지하는 효과를 가져옵니다.
+ Java에서는 해시 충돌을 어떻게 해결했을까?
- jdk7까지는 linked list를 사용한 separate chaning을 활용.
- jdk8에서 linked list와 red black tree를 혼용한 separate chaining을 활용.
- 충돌을 한 key-value쌍이 적을때는 linked list로 작동을 한다.
- 충돌을 한 key-value쌍이 특정 임계치에 도달하면 red black tree로 작동을 한다.
'정보처리기사' 카테고리의 다른 글
| OSI 7계층의 네트워킹 장비 및 주요 프로토콜 (0) | 2024.09.26 |
|---|---|
| 보안 공격 기법 (3) | 2024.09.24 |
| 병행 수행 및 병행 제어 (0) | 2024.09.24 |
| SDLC 와 Secure SDLC 비교하기 (0) | 2024.04.25 |