이중 해시

이중 해시법(double hashing)은 해시 테이블에서 해시 충돌을 해결하기 위해 개방 주소 지정 방식과 함께 사용되는 컴퓨터 프로그래밍 기술로, 충돌 발생 시 보조 해시를 키의 오프셋으로 사용한다. 개방 주소 지정 방식과 함께 이중 해시를 사용하는 것은 $T$ 테이블의 고전적인 자료 구조이다.

이중 해시 기술은 하나의 해시 값을 테이블의 인덱스로 사용하고, 원하는 값이 발견되거나, 빈 위치에 도달하거나, 전체 테이블을 검색할 때까지 특정 간격으로 반복하여 앞으로 이동한다. 하지만 이 간격은 두 번째의 독립적인 해시 함수에 의해 설정된다. 선형 탐사 및 제곱 탐사와 같은 다른 충돌 해결 방법과는 달리, 이 간격은 데이터에 따라 달라지므로 동일한 위치로 매핑되는 값들은 서로 다른 버킷 시퀀스를 갖게 된다. 이는 반복적인 충돌과 군집화의 영향을 최소화한다.

두 개의 무작위적이고 균일하며 독립적인 해시 함수 $h_{1}$과 $h_{2}$가 주어졌을 때, $|T|$ 버킷으로 구성된 해시 테이블에서 값 $k$에 대한 버킷 시퀀스의 $i$번째 위치는 $h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|$이다. 일반적으로 $h_{1}$과 $h_{2}$는 범용 해시 함수의 집합에서 선택된다. $h_{1}$은 $\{0,|T|-1\}$ 범위의 값을 갖도록 선택되고, $h_{2}$는 $\{1,|T|-1\}$ 범위의 값을 갖도록 선택된다. 이중 해시는 무작위 분포를 근사화한다. 더 정확히 말하면, 쌍별 독립적인 해시 함수는 어떤 키 쌍이 동일한 버킷 시퀀스를 따를 확률을 $(n/|T|)^{2}$로 만든다.

h₂(k) 선택

보조 해시 함수 $h_{2}(k)$는 다음과 같은 특징을 가져야 한다.

• 절대 0 인덱스를 반환하지 않아야 한다.
• 전체 테이블을 순환해야 한다.
• 계산이 매우 빨라야 한다.
• $h_{1}(k)$와 쌍별 독립적이어야 한다.
• $h_{2}$의 분포 특성은 중요하지 않다. 이는 난수 생성기와 유사하다.
• 모든 $h_{2}(k)$는 $|T|$와 서로소여야 한다.

실제로는 다음과 같다.

• 두 함수 모두 나눗셈 해시를 사용하는 경우, 제수는 소수로 선택된다.
• $|T|$가 2의 거듭제곱인 경우, $h_{2}(k)$가 항상 홀수를 반환하도록 하면 첫 번째 및 마지막 요구 사항이 일반적으로 충족된다. 이는 한 비트가 낭비되어 충돌 가능성이 두 배가 되는 부작용이 있다.

분석

$T$에 저장된 요소의 수를 $n$이라고 하면, $T$의 적재율은 $\alpha =n/|T|$이다. 즉, 이중 해시 테이블 $T$를 만들기 위해 무작위적이고 균일하며 독립적인 두 개의 범용 해시 함수 $h_{1}$과 $h_{2}$를 선택하는 것으로 시작한다. 모든 요소는 $h_{1}$과 $h_{2}$를 사용하는 이중 해시를 통해 $T$에 삽입된다. 주어진 키 $k$에 대해 $(i+1)$번째 해시 위치는 다음으로 계산된다.

$$h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.$$

$T$가 고정된 적재율 $\alpha :1>\alpha >0$을 갖는다고 가정하자. 브래드포드와 케이테하키스는 입력 분포와 관계없이 처음 선택된 해시 함수를 사용하여 $T$에서 성공하지 못한 검색에 대한 예상 탐사 횟수가 ${\tfrac {1}{1-\alpha }}$임을 보였다. 해시 함수의 쌍별 독립성으로 충분하다.

다른 모든 개방 주소 지정 방식과 마찬가지로, 해시 테이블이 최대 용량에 가까워지면 이중 해시는 선형적으로 변한다. 일반적인 휴리스틱 이론은 테이블 적재율을 용량의 75%로 제한하는 것이다. 결국 다른 모든 개방 주소 지정 방식과 마찬가지로 더 큰 크기로 재해싱하는 것이 필요할 것이다.

변형

피터 딜린저(Peter Dillinger)의 박사 학위 논문은 블룸 필터에서와 같이 해시 함수가 집합으로 취급될 때 이중 해시가 원치 않는 동등한 해시 함수를 생성한다는 점을 지적한다. 만약 $h_{2}(y)=-h_{2}(x)$이고 $h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)$라면, $h(i,y)=h(k-i,x)$이며 해시 집합 $\left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}$는 동일하다. 이는 충돌 가능성을 $1/|T|^{2}$이 될 것으로 기대했던 것보다 두 배로 만든다.

또한 상당히 많은 부분이 겹치는 해시 집합이 존재한다. 만약 $h_{2}(y)=h_{2}(x)$이고 $h_{1}(y)=h_{1}(x)\pm h_{2}(x)$라면, $h(i,y)=h(i\pm 1,x)$이며, 추가 해시 값을 비교하는 것($i$의 범위를 확장하는 것)은 도움이 되지 않는다.

삼중 해시

해시 함수에 이차항 $i^{2},$ $i(i+1)/2$ (삼각수) 또는 심지어 $i^{2}\cdot h_{3}(x)$ (삼중 해시)를 추가하면 해시 함수가 다소 개선된다. 하지만 이 문제를 해결하지는 못한다. 만약 다음과 같다면:

$h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),$

$h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),$ 이고

$h_{3}(y)=h_{3}(x).$

그러면

${\begin{aligned}h(k-i,y)&=h_{1}(y)+(k-i)\cdot h_{2}(y)+(k-i)^{2}\cdot h_{3}(y)\\&=h_{1}(y)+(k-i)(-h_{2}(x)-2kh_{3}(x))+(k-i)^{2}h_{3}(x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3}(x)\\&=h(i,x).\\\end{aligned}}$

향상된 이중 해시

삼차항 $i^{3}$ 또는 $(i^{3}-i)/6$ (사면체수)를 추가하면 문제를 해결할 수 있는데, 이 기술은 향상된 이중 해시로 알려져 있다. 이는 선행 차분을 통해 효율적으로 계산할 수 있다.

struct key;	/// 불투명
/// 필요할 때 다른 데이터 유형을 사용한다. (래핑을 보장하기 위해 부호 없는 정수여야 함.)
extern unsigned int h1(struct key const *), h2(struct key const *);

/// 향상된 이중 해시를 사용하여 두 기본 해시 함수 h1()과 h2()로부터 k개의 해시 값을 계산한다.
/// 반환 시 hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6.
/// C에서 부호 없는 유형의 자동 래핑(모듈러 감소)을 활용한다.
void ext_dbl_hash(struct key const *x, unsigned int hashes[], unsigned int n)
{
	unsigned int a = h1(x), b = h2(x), i = 0;

    hashes[i] = a;
	for (i = 1; i < n; i++) {
		a += b;	// 3차항을 얻기 위해 2차 차분을 더한다.
		b += i;	// 2차항을 얻기 위해 1차 차분을 더한다.
		       	// i++는 1차항을 얻기 위해 상수 차분을 더한다.
		hashes[i] = a;
	}
}

충돌 문제를 해결하는 것 외에도, 향상된 이중 해시는 $h_{2}(x)$의 속성에 대한 이중 해시의 수치적 제한을 제거하여 $h_{1}$과 유사한 속성을 가진(그러나 여전히 독립적인) 해시 함수를 사용할 수 있게 한다.

같이 보기

• 쿠쿠 해시
• 2-선택 해시

외부 링크

• 캐싱이 해싱에 미치는 영향 by 그레고리 L. 하일맨 and 웬빈 뤄 2005.
• 해시 테이블 애니메이션
• klib 이중 해시 기능을 포함하는 C 라이브러리.