해시함수(hash function)로 h(k)=k mod 7을 사용하고… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
해시함수(hash function)로 h(k)=k mod 7을 사용하고, 선형탐색(linear probing) 기법을 이용하여 충돌을 해결하고자 한다. 키가 3, 10, 5, 9, 12 순서대로 입력되었을 때, 생성된 해시테이블은?
1
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 12 | 9 | 3 | 10 | 5 |
2
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 12 | 3 | 10 | 5 | 9 |
3
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 9 | 10 | 3 | 12 | 5 |
4
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 9 | 3 | 10 | 5 | 12 |
해설
선형탐색으로 충돌을 해결하면 해시테이블은 [2]=9, [3]=3, [4]=10, [5]=5, [6]=12가 된다.
3 → 3 mod 7 = 3, [3]에 저장
10 → 10 mod 7 = 3, 충돌 → 다음 빈 칸 [4]에 저장
5 → 5 mod 7 = 5, [5]에 저장
9 → 9 mod 7 = 2, [2]에 저장
12 → 12 mod 7 = 5, 충돌 → [6]에 저장
- 12를 [0], 9를 [1]에 둔 테이블은 9의 해시값 2와 12의 다음 빈 칸 [6]을 무시했다.
- 12를 [0], 9를 [6]에 둔 테이블은 9가 비어 있는 [2]에 바로 들어가야 함을 무시했다.
- 10을 [2], 12를 [4]에 둔 테이블은 충돌 시 다음 칸으로 이동하는 선형탐색 규칙에 어긋난다.
오류나 개정된 내용이 보이면 알려주세요