해시 테이블 HT의 크기는 11이고 0부터 10까지의 인덱스를 가진다.… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
해시 테이블 HT의 크기는 11이고 0부터 10까지의 인덱스를 가진다. 해시 함수 h(x)는 제산 함수로서 h(x) = x mod 11로 표현된다. 충돌 해결책으로는 이차 조사법(quadratic probing)을 사용한다. 해싱을 통해 해시 테이블에 저장할 레코드들의 키 값 순서는 다음과 같다. 마지막 레코드가 저장되는 해시 테이블 위치는? (단, 첫 번째 레코드가 저장되기 전에 해시 테이블은 비어 있고, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)51, 27, 70, 55, 13, 2, 37, 23, 33
1
HT[1]
2
HT[4]
3
HT[6]
4
HT[9]
해설
마지막 키 33은 HT[9]에 저장된다.
이차 조사법은 충돌 시 순서로 빈 자리를 찾는다.
51→7, 27→5, 70→4, 55→0, 13→2
2→2 충돌 → 3
37→4 충돌 → 5 충돌 → 8
23→1
33→0 충돌 → 1 충돌 → 4 충돌 → 9
- HT[1]은 33의 첫 조사 위치(0 + 1)로, 이미 23이 차지하고 있다.
- HT[4]는 그다음 조사 위치(0 + 4)로, 70이 차지하고 있다.
- HT[6]은 비어 있지만 33의 조사 순서(0, 1, 4, 9)에 들어가지 않는다.
오류나 개정된 내용이 보이면 알려주세요