[7급 국가직 자료구조론 2024년 22번]

버킷(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\mathrm{mod}13$ $f(x)=x\mathrm{mod}11$ $h_i(x)=(h(x)+i\times f(x))\mathrm{mod}13$