하나의 주소에 하나의 원소가 저장되는 해시 테이블에서의 충돌 문제를 해… | [국회직 9급 컴퓨터일반] 25년 1회차 기출문제 상세 페이지

하나의 주소에 하나의 원소가 저장되는 해시 테이블에서의 충돌 문제를 해결하기 위해 더블 해싱을 사용한다. 다음과 같이 해시 함수가 주어져 있고 현재 테이블에 5개의 원소만 저장되어 있는 경우, 원소 19가 저장될 주소는?
$h_{i} ( x ) = ( h ( x ) + i \bullet f ( x ) ) \,\, \bmod \,\, 17 \quad i = 0 , 1 , 2 , . . .$
$h ( x ) = x \,\, \bmod \,\, 17$
$f ( x ) = 1 + ( x \,\, \bmod \, 13 )$
$h_{0} ( 17 ) = 0 , \, h_{0} ( 36 ) = 2 , \, h_{0} ( 20 ) = 3 , \, h_{0} ( 5 ) = 5 , \, h_{0} ( 26 ) = 9$

2

7

9

15

16

원소 19는 주소 16에 저장된다.
먼저 두 해시값을 구한다.
$h(19) = 19 \bmod 17 = 2$
$f(19) = 1 + (19 \bmod 13) = 1 + 6 = 7$
i를 늘리며 빈 주소를 찾는다.
$h_{0}(19) = 2$ : 36이 차지함
$h_{1}(19) = (2 + 1 \cdot 7) \bmod 17 = 9$ : 26이 차지함
$h_{2}(19) = (2 + 2 \cdot 7) \bmod 17 = 16$ : 비어 있음
주소 2는 첫 탐사 위치이지만 이미 36이 저장되어 있다.
주소 7은 증가폭 f(19)의 값일 뿐 탐사 주소가 아니다.
주소 9는 두 번째 탐사 위치이지만 이미 26이 저장되어 있다.
주소 15는 탐사 순서 2, 9, 16에 나타나지 않는다.