이중 해시

**이중 해시법**(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로 만든다.
# h2(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)의 박사 학위 논문url=http://peterd.org/pcd-diss.pdf#page=93은 블룸 필터에서와 같이 해시 함수가 집합으로 취급될 때 이중 해시가 원치 않는 동등한 해시 함수를 생성한다는 점을 지적한다. 만약 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,url=https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf i(i+1)/2 (삼각수) 또는 심지어 i^2 \cdot h_3(x) (**삼중 해시**)딜린저 2004에서와 같이 삼각수로 다르게 정의됨.를 추가하면 해시 함수가 다소 개선된다. 하지만 이 문제를 해결하지는 못한다. 만약 다음과 같다면: : 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 (사면체수)url=https://www.khoury.northeastern.edu/~pete/pub/bloom-filters-verification.pdf를 추가하면 문제를 해결할 수 있는데, 이 기술은 **향상된 이중 해시**로 알려져 있다. 이는 선행 차분을 통해 효율적으로 계산할 수 있다. 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과 유사한 속성을 가진(그러나 여전히 독립적인) 해시 함수를 사용할 수 있게 한다.