이중 해시

**이중 해시법**(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<sub>2</sub>(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{align}
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) - 2k h_3(x)) + (k-i)^2 h_3(x) \\
          &= \ldots \\
          &= h_1(x) + k h_2(x) + k^2 h_3(x) + (i - k) h_2(x) + (i^2 - k^2) h_3(x) \\
          &= h_1(x) + i h_2(x) + i^2 h_3(x) \\
          &= h(i, x). \\
\end{align}

### 향상된 이중 해시

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

```c
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 라이브러리.

분류:검색 알고리즘
분류:해싱