이중 해시

1. 개요

이중 해싱은 충돌을 줄이기 위해 두 개의 해시 함수를 사용하는 개방 주소 지정 방식의 해싱 기술이다. 보조 해시 함수는 0을 반환하지 않고, 전체 테이블을 순환하며, 계산 속도가 빠르고, 첫 번째 해시 함수와 독립적이어야 하며, 해시 테이블 크기와 서로소여야 한다. 이중 해싱은 실패한 검색에 대한 예상 프로브 수가 적재율에 따라 결정되며, 테이블 로딩을 75%로 제한하는 것이 일반적이다. 삼중 해싱과 향상된 이중 해싱은 이중 해싱의 변형으로, 해시 함수의 개선을 위해 3차항 또는 사면체수를 추가한다. 향상된 이중 해싱은 해시 함수 집합의 동일성 문제를 해결하고, h₂의 속성에 대한 제약을 완화한다.

2. 이중 해싱의 기본 원리

이중 해싱은 해시 충돌을 해결하기 위한 개방 주소 지정 방식 중 하나이다. 이 방식의 핵심 원리는 서로 독립적인 두 개의 [[보편 해시]] 함수 $h\_1$과 $h\_2$를 사용하는 것이다.

키 $k$를 해시 테이블 $T$에 삽입하거나 검색할 때, 먼저 첫 번째 해시 함수 $h\_1(k)$를 사용하여 초기 위치를 계산한다. 만약 해당 위치에서 충돌이 발생하면, 두 번째 해시 함수 $h\_2(k)$를 사용하여 다음 탐사 위치를 결정하기 위한 고유한 이동 거리를 계산한다. 이처럼 키마다 다른 이동 거리를 적용함으로써, 선형 탐사법이나 제곱 탐사법 등에서 발생할 수 있는 클러스터링(데이터가 특정 영역에 집중되는 현상) 문제를 효과적으로 완화할 수 있다는 장점이 있다. 이 방식은 해시 테이블의 성능을 유지하는 데 도움을 준다.

2.1. 보조 해시 함수 (h₂(k))의 특징

보조 해시 함수 $h\_2(k)$는 다음과 같은 몇 가지 특징을 가져야 한다.

* 0을 인덱스로 반환해서는 안 된다. 이는 첫 번째 탐사 위치(probe)가 $h\_1(k)$와 동일해지는 것을 방지하기 위함이다.
* 전체 해시 테이블을 순환할 수 있도록 해야 한다. 즉, $h\_2(k)$의 값은 테이블 크기 |T|와 서로소여야 한다.
* 계산 속도가 매우 빨라야 한다.
* 첫 번째 해시 함수 $h\_1(k)$와 쌍별 독립적이어야 한다. 이는 클러스터링을 최소화하는 데 도움이 된다.
* $h\_2$의 분포 특성은 중요하지 않다. 난수 생성기와 유사하게 동작해도 무방하다.

실제 구현 시 고려 사항은 다음과 같다.

* 두 해시 함수($h\_1(k)$, $h\_2(k)$) 모두에 나눗셈 해싱을 사용하는 경우, 제수(나누는 수)를 소수로 선택하는 것이 좋다.
* 해시 테이블 크기 |T|가 2의 거듭제곱인 경우, $h\_2(k)$가 항상 홀수를 반환하도록 설계하여 '0 반환 금지'와 '테이블 크기와의 서로소' 조건을 만족시키는 경우가 많다. 하지만 이 방식은 사용하지 않는 비트가 발생하여 충돌 가능성을 두 배로 높이는 단점이 있다.

2.2. 해시 위치 계산

해시 테이블 $T$에 저장된 요소의 수를 $n$이라고 할 때, $T$의 적재율은 $\backslash alpha\; =\; n/|T|$이다. 이중 해싱 테이블 $T$를 구축하기 위해, 무작위로 균등하고 독립적인 두 개의 보편 해시 함수 $h\_1$과 $h\_2$를 선택한다. 모든 요소는 이 두 함수를 이용한 이중 해싱을 통해 $T$에 저장된다.

주어진 키 $k$에 대해, $(i+1)$번째 해시 위치는 다음 공식으로 계산된다.

$$h(i,k)\; =\; (\; h\_1(k)\; +\; i\; \backslash cdot\; h\_2(k)\; )\; \backslash bmod\; |T|$$

여기서 $|T|$는 해시 테이블의 크기를 나타낸다.

해시 테이블 $T$는 고정된 적재율 $\backslash alpha$ ($1\; >\; \backslash alpha\; >\; 0$)를 가진다. Bradford와 케테하키스는 처음에 선택된 해시 함수들을 계속 사용할 경우, $T$에서 실패한 검색에 대한 예상 프로브(probe) 수가 입력 데이터의 분포와 관계없이 $\backslash tfrac\{1\}\{1-\backslash alpha\}$임을 증명했다. 이를 위해 해시 함수 쌍의 독립성만으로 충분하다는 것을 보였다.

다른 모든 형태의 개방 주소 지정 방식과 마찬가지로, 이중 해싱은 해시 테이블이 거의 가득 찰수록 성능이 선형적으로 저하되는 경향이 있다. 일반적으로 테이블의 적재율을 용량의 75% 이하로 유지하는 것이 권장된다. 결국, 다른 개방 주소 지정 방식들처럼 테이블 크기가 부족해지면 더 큰 크기로 재해싱하는 과정이 필요하다.

3. 이중 해싱의 분석

해시 테이블 $T$에 저장된 요소의 수를 $n$이라고 할 때, $T$의 적재율(load factor)은 $\backslash alpha\; =\; n/|T|$로 정의된다. 이중 해싱에서는 무작위로 균등하고 독립적으로 선택된 두 개의 보편 해시 함수 $h\_1$과 $h\_2$를 사용하여 해시 테이블 $T$를 구축한다. 모든 요소는 이 두 함수를 이용한 이중 해싱을 통해 $T$에 저장된다.

키 $k$가 주어졌을 때, $(i+1)$번째 탐사 위치는 다음 수식으로 계산된다:
$$h(i,k)\; =\; (\; h\_1(k)\; +\; i\; \backslash cdot\; h\_2(k)\; )\; \backslash bmod\; |T|.$$

해시 테이블 $T$가 고정된 적재율 $\backslash alpha$ ($1\; >\; \backslash alpha\; >\; 0$)를 가질 때, Bradford와 케테하키스는 초기 선택된 해시 함수 $h\_1$과 $h\_2$를 사용하는 경우, $T$에서 실패한 검색(unsuccessful search)에 대한 예상 프로브(probe) 횟수가 입력 데이터의 분포와 관계없이 $\backslash tfrac\{1\}\{1-\backslash alpha\}$임을 증명했다. 이 분석에서는 해시 함수들이 쌍별 독립성(pairwise independence)만 만족해도 충분하다.

다른 모든 개방 주소법과 마찬가지로, 이중 해싱은 해시 테이블이 거의 가득 찰수록(즉, 적재율 $\backslash alpha$가 1에 가까워질수록) 성능이 선형적으로 저하되는 경향이 있다. 따라서 실제 구현에서는 일반적으로 해시 테이블의 적재율을 최대 용량의 75% 정도로 제한하는 방법을 사용한다. 결국 테이블이 일정 수준 이상으로 채워지면, 더 큰 크기의 테이블로 재해싱(rehashing)하는 과정이 필요하다.

3.1. 삼중 해싱 (Triple Hashing)

해시 함수에 2차 항 $i^2,$ $i(i+1)/2$(삼각수) 또는 $i^2\; \backslash cdot\; h\_3(x)$ 형태의 항을 추가하는 것을 고려할 수 있다. 특히 $i^2\; \backslash cdot\; h\_3(x)$ 항을 사용하는 방식을 삼중 해싱(Triple Hashing)이라고 부른다.

이러한 2차 항을 추가하면 해시 함수의 성능이 일부 개선될 수 있지만, 서로 다른 키가 충돌했을 때 동일한 순서로 다음 슬롯을 탐사하게 되는 근본적인 문제는 해결되지 않는다. 특정 조건에서는 서로 다른 두 키 $x$와 $y$가 동일한 탐사 시퀀스를 생성할 수 있다. 이는 다음 수식을 통해 확인할 수 있다.

만약 아래 조건들이 성립한다면:
: $h\_1(y)\; =\; h\_1(x)\; +\; k\; \backslash cdot\; h\_2(x)\; +\; k^2\; \backslash cdot\; h\_3(x),$
: $h\_2(y)\; =\; -h\_2(x)\; -\; 2k\; \backslash cdot\; h\_3(x),$ 그리고
: $h\_3(y)\; =\; h\_3(x).$
다음과 같이 $y$에 대한 $(k-i)$번째 탐사 위치와 $x$에 대한 $i$번째 탐사 위치가 같아지는 관계($h(k-i,\; y)\; =\; h(i,\; x)$)가 성립한다.
: $\backslash 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}
따라서 삼중 해싱 역시 해시 테이블의 성능을 저하시킬 수 있는 클러스터링 문제를 완전히 해결하지는 못한다.

3.2. 향상된 이중 해싱 (Enhanced Double Hashing)

기존 이중 해싱에서 발생할 수 있는 문제를 해결하기 위해 3차 항 $i^3$ 또는 $(i^3-i)/6$(사면체수)를 추가하는 방식을 향상된 이중 해싱이라고 한다. 이 방식은 서로 다른 키에 대해 해시 함수 집합이 동일하게 생성되는 가능성을 줄여준다.

향상된 이중 해싱은 전방 차분 기법을 활용하여 효율적으로 계산될 수 있다. 초기 해시 값 $h\_1(x)$와 $h\_2(x)$를 계산한 후, 반복 과정에서 이전 단계의 값들에 특정 차분 값들을 더해가는 방식으로 다음 해시 위치를 결정한다. 이는 각 단계마다 3차항을 직접 계산하는 것보다 연산 효율성을 높인다. 아래는 C 코드로 구현된 예시이다.
```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;

hashes[0] = a; // 첫 번째 해시 값은 h1(x)
for (i = 1; i < n; i++) {
a += b; // 다음 a 값 계산: a = a + b (3차항 계산을 위한 2차 차분 누적)
b += i; // 다음 b 값 계산: b = b + i (2차항 계산을 위한 선형 차분 누적)
// i++는 다음 반복에서 선형항 계산을 위한 상수 차분을 자동으로 반영
hashes[i] = a; // 계산된 해시 값 저장
}
}
```
이러한 계산 방식은 C 언어에서 부호 없는 정수형(unsigned integer)의 자동 래핑(모듈러 연산) 특성을 활용하여 구현될 수 있다.

충돌 문제를 해결하는 것 외에도, 향상된 이중 해싱은 기존 이중 해싱에서 $h\_2(x)$ 함수가 가져야 했던 특정 수치적 제약(예: 테이블 크기와 서로소여야 하는 조건 등)을 완화시키는 장점이 있다. 이로 인해 $h\_2(x)$ 함수를 선택할 때 $h\_1(x)$과 유사한 좋은 분포 특성을 가지면서도 서로 독립적인 함수를 사용하는 것이 더 용이해진다.