다음 비어 있는 크기가 11인 해시 테이블(hash table)에 입력… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 비어 있는 크기가 11인 해시 테이블(hash table)에 입력키가 4, 6, 15, 26, 17 순서로 저장되었다. 입력키 26이 저장된 해시 테이블의 주소는? (단, 해시 함수는 h(k) = k mod 11이고, 충돌 해결은 선형 조사법(linear probing)을 사용한다)
| 해시 테이블 주소 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 해시 테이블 |
1
1
2
4
3
6
4
7
해설
입력키 26은 해시 테이블 주소 7에 저장된다.
k mod 11로 홈 주소를 구하고, 충돌하면 다음 주소로 한 칸씩 이동한다(선형 조사).
- 4: 4 mod 11 = 4 → 주소 4
- 6: 6 mod 11 = 6 → 주소 6
- 15: 15 mod 11 = 4 → 4 충돌 → 주소 5
- 26: 26 mod 11 = 4 → 4·5·6이 모두 차 있음 → 주소 7
주소 4는 26의 홈 주소일 뿐 이미 키 4가 차지했고, 주소 6도 키 6이 먼저 들어가 있다.
오류나 개정된 내용이 보이면 알려주세요