버킷(bucket)이 13개이고 버킷당 슬롯(slot)이 1개인 해시 … | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

버킷(bucket)이 13개이고 버킷당 슬롯(slot)이 1개인 해시 테이블에 키 값 <7, 20, 3, 19, 45>를 차례대로 저장하고자 한다. 다음 <조건>에 따라 아래 <해시 함수>를 이용하여 작동하는 이중 해싱(double hashing)에서, 마지막 키 값 45의 저장 위치는?
<조  건>
○ 버킷의 인덱스는 0부터 시작한다.
○ $h(x)$는 첫 번째 조사 위치를 결정하는 기본 해시 함수이다.
○ $f(x)$는 충돌 발생 시 조사 위치 간격을 결정하는 함수이다.
○ 하나의 키 값에 대한 해시 함수 연산 중 충돌이 1번 이상 발생할 경우 $i$번째 충돌에 대응하여 $h_i(x)$를 적용한다.

<해시 함수>
$h(x) = x \bmod 13$
$f(x) = x \bmod 11$
$h_i(x) = (h(x)+i \times f(x)) \bmod 13$

5

7

8

11

키 45는 버킷 8에 저장된다.
앞의 키들을 먼저 배치한다.
7: h=7 → 버킷 7
20: h=7 충돌, f=9 → (7+9) mod 13 = 3
3: h=3 충돌, f=3 → (3+3) mod 13 = 6
19: h=6 충돌, f=8 → (6+8) mod 13 = 1
45: h=45 mod 13 = 6에서 충돌하고 f=45 mod 11 = 1이다. $h_1 = (6+1) \bmod 13 = 7$도 차 있으므로 $h_2 = (6+2 \times 1) \bmod 13 = 8$에 저장된다.
버킷 7은 첫 재조사 위치지만 이미 키 7이 있다.
버킷 5는 조사 순서 6 → 7 → 8에 나타나지 않는다.
버킷 11도 조사 순서에 나타나지 않는다.