다음의 해시 함수들을 사용하는 이중 해싱(double hashing)에… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
다음의 해시 함수들을 사용하는 이중 해싱(double hashing)에서 해시 테이블의 크기는 7이며 0부터 6까지의 인덱스를 가진다. 는 첫 번째 조사 위치를 결정하는 기본적인 해시 함수이고 는 충돌 발생 시 조사 위치 간격을 결정하는 추가 해시 함수로서, 번째 충돌 발생 시 다음 조사 위치를 결정하는 해시 함수는 가 된다. 공백 해시 테이블에 일련의 키(key) 값 9, 10, 2, 3, 16, 13, 11을 가지는 레코드들을 순서대로 삽입한 후, 해시 테이블의 위치별 키 값을 보여주는 것은? (단, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|
1
| 13 | 16 | 9 | 10 | 11 | 2 | 3 |
2
| 16 | 13 | 9 | 10 | 11 | 2 | 3 |
3
| 3 | 13 | 9 | 10 | 11 | 2 | 16 |
4
| 13 | 11 | 9 | 10 | 2 | 3 | 16 |
해설
삽입 후 해시 테이블은 [0]부터 3, 13, 9, 10, 11, 2, 16이다.
충돌이 없으면 위치에 넣고, 충돌하면 간격으로 다음 위치를 조사한다.
9: h=2 → [2]
10: h=3 → [3]
2: h=2 충돌, f=3 → (2+3) mod 7 = 5 → [5]
3: h=3 충돌, f=2 → [5] 충돌 → (3+4) mod 7 = 0 → [0]
16: h=2 충돌, f=4 → (2+4) mod 7 = 6 → [6]
13: h=6 충돌, f=2 → (6+2) mod 7 = 1 → [1]
11: h=4 → [4]
- [0]에 13, [6]에 3을 둔 배치: 13은 [1], 3은 [0]에 들어가므로 틀리다.
- [0]에 16, [1]에 13을 둔 배치: 16은 첫 충돌 후 [6]에 들어가므로 틀리다.
- [1]에 11, [4]에 2, [5]에 3을 둔 배치: 11은 충돌 없이 [4], 2는 [5]에 들어가므로 틀리다.
오류나 개정된 내용이 보이면 알려주세요