크기가 7(M=7)인 해시 테이블(hash table)에 이중 해싱(d… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
크기가 7()인 해시 테이블(hash table)에 이중 해싱(double hashing) 기법을 사용하여 데이터를 삽입한다고 하자. 첫 번째 해시 함수(hash function)는 이고, 충돌이 발생할 경우 사용하는 두 번째 해시 함수는 이다. 이러한 해시 함수를 사용하여 다음과 같은 탐색 키들을 차례대로 삽입한다고 할 때, 삽입이 완료된 후 해시 테이블의 상태는?1, 15, 3, 6, 10
1
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 15 | 3 | 10 | 6 |
2
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 10 | 15 |
3
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 15 | 3 | 10 | 6 |
4
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 10 | 15 |
해설
삽입 완료 후 테이블은 [0]=6, [1]=1, [3]=3, [4]=10, [6]=15이다.
이중 해싱은 충돌 시 위치를 차례로 탐사한다.
1 → [1], 3 → [3]은 충돌 없이 들어간다.
15: 충돌, →
6: 충돌, → 충돌 →
10: 충돌, → [1], [6] 충돌 →
- [2]에 15, [4]에 10, [6]에 6인 상태: 충돌 시 한 칸씩 옮기는 선형 탐사의 결과다.
- [0]에 6, [5]에 10, [6]에 15인 상태: 10은 [1], [6]을 거쳐 [4]에 들어가야 한다.
- [2]에 15, [5]에 10, [6]에 6인 상태: 15부터 두 번째 해시 함수를 올바로 적용하지 않은 결과다.
오류나 개정된 내용이 보이면 알려주세요