이중 해시

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

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

두 개의 무작위적이고 균일하며 독립적인 해시 함수 과 가 주어졌을 때,  버킷으로 구성된 해시 테이블에서 값 에 대한 버킷 시퀀스의 번째 위치는 이다. 일반적으로 과 는 범용 해시 함수의 집합에서 선택된다. 은  범위의 값을 갖도록 선택되고, 는  범위의 값을 갖도록 선택된다. 이중 해시는 무작위 분포를 근사화한다. 더 정확히 말하면, 쌍별 독립적인 해시 함수는 어떤 키 쌍이 동일한 버킷 시퀀스를 따를 확률을 로 만든다.

 h2(k) 선택 
보조 해시 함수 는 다음과 같은 특징을 가져야 한다.
 절대 0 인덱스를 반환하지 않아야 한다.
 전체 테이블을 순환해야 한다.
 계산이 매우 빨라야 한다.
 와 쌍별 독립적이어야 한다.
 의 분포 특성은 중요하지 않다. 이는 난수 생성기와 유사하다.
 모든 는 와 서로소여야 한다.

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

 분석 

에 저장된 요소의 수를 이라고 하면, 의 적재율은 이다. 즉, 이중 해시 테이블 를 만들기 위해 무작위적이고 균일하며 독립적인 두 개의 범용 해시 함수 과 를 선택하는 것으로 시작한다. 모든 요소는 과 를 사용하는 이중 해시를 통해 에 삽입된다.
주어진 키 에 대해 번째 해시 위치는 다음으로 계산된다.

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

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

 변형 

피터 딜린저(Peter Dillinger)의 박사 학위 논문은 블룸 필터에서와 같이 해시 함수가 집합으로 취급될 때 이중 해시가 원치 않는 동등한 해시 함수를 생성한다는 점을 지적한다. 만약 이고 라면, 이며 해시 집합 는 동일하다. 이는 충돌 가능성을 이 될 것으로 기대했던 것보다 두 배로 만든다.

또한 상당히 많은 부분이 겹치는 해시 집합이 존재한다. 만약 이고 라면, 이며, 추가 해시 값을 비교하는 것(의 범위를 확장하는 것)은 도움이 되지 않는다.

 삼중 해시 
해시 함수에 이차항   (삼각수) 또는 심지어  (삼중 해시)딜린저 2004에서와 같이 삼각수로 다르게 정의됨.를 추가하면 해시 함수가 다소 개선된다. 하지만 이 문제를 해결하지는 못한다. 만약 다음과 같다면:

  이고

그러면


 향상된 이중 해시 

삼차항  또는  (사면체수)를 추가하면 문제를 해결할 수 있는데, 이 기술은 향상된 이중 해시로 알려져 있다. 이는 선행 차분을 통해 효율적으로 계산할 수 있다.
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;
	}
}

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

 같이 보기 
 쿠쿠 해시
 2-선택 해시

 각주 

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

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