이 섹션에서는 개방형 주소 지정 방식에서 Double Hashing 기술이 무엇인지 살펴보겠습니다. 일반적인 해시 함수 h'(x)가 있습니다. U → {0, 1, . . ., m – 1}. 개방형 주소 지정 방식에서 실제 해시 함수 h(x)는 공간이 비어 있지 않을 때 일반 해시 함수 h'(x)를 취한 다음 삽입할 공간을 확보하기 위해 다른 해시 함수를 수행합니다.
$$h_{1}(x)=x\:mod\:m$$
$$h_{2}(x)=x\:mod\:m^{\prime}$$
$$h(x,i)=(h^{1}(x)+ih^{2})\:mod\:m$$
i의 값 =0, 1, . . ., m – 1. 그래서 우리는 i =0에서 시작하여 하나의 여유 공간이 생길 때까지 이것을 늘립니다. 따라서 처음에 i =0일 때 h(x, i)는 h'(x)와 같습니다.
예
크기가 20(m =20)인 목록이 있다고 가정합니다. 일부 요소를 선형 탐색 방식으로 지정하려고 합니다. 요소는 {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}입니다.
$$h_{1}(x)=x\:mod\:20$$
$$h_{2}(x)=x\:mod\:13$$
x h(x, i) =(h1(x) + ih2(x)) 모드 20
해시 테이블
