이중 해시

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 이중 해싱의 기본 원리
- 2.1. 보조 해시 함수 (h₂(k))의 특징
- 2.2. 해시 위치 계산
3. 이중 해싱의 분석
- 3.1. 삼중 해싱 (Triple Hashing)
- 3.2. 향상된 이중 해싱 (Enhanced Double Hashing)
참조

1. 개요

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

2. 이중 해싱의 기본 원리

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

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

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 반환 금지'와 '테이블 크기와의 서로소' 조건을 만족시키는 경우가 많다. 하지만 이 방식은 사용하지 않는 비트가 발생하여 충돌 가능성을 두 배로 높이는 단점이 있다.^[5]

2. 2. 해시 위치 계산

해시 테이블

T

에 저장된 요소의 수를

n

이라고 할 때,

T

의 적재율은

\alpha = n/|T|

이다. 이중 해싱 테이블

T

를 구축하기 위해, 무작위로 균등하고 독립적인 두 개의 보편 해시 함수

h_1

과

h_2

를 선택한다. 모든 요소는 이 두 함수를 이용한 이중 해싱을 통해

T

에 저장된다.

주어진 키

k

에 대해,

(i+1)

번째 해시 위치는 다음 공식으로 계산된다.

h(i,k) = ( h_1(k) + i \cdot h_2(k) ) \bmod |T|

여기서

|T|

는 해시 테이블의 크기를 나타낸다.

해시 테이블

T

는 고정된 적재율

\alpha

(

1 > \alpha > 0

)를 가진다. Bradford와 케테하키스^[1]는 처음에 선택된 해시 함수들을 계속 사용할 경우,

T

에서 실패한 검색에 대한 예상 프로브(probe) 수가 입력 데이터의 분포와 관계없이

\tfrac{1}{1-\alpha}

임을 증명했다. 이를 위해 해시 함수 쌍의 독립성만으로 충분하다는 것을 보였다.

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

3. 이중 해싱의 분석

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

키 $k$ 가 주어졌을 때, $(i+1)$ 번째 탐사 위치는 다음 수식으로 계산된다:

$h(i,k) = ( h_1(k) + i \cdot h_2(k) ) \bmod |T|.$

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

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

3. 1. 삼중 해싱 (Triple Hashing)

해시 함수에 2차 항

i^2,

^[3]

i(i+1)/2

(삼각수) 또는

i^2 \cdot h_3(x)

형태의 항을 추가하는 것을 고려할 수 있다. 특히

i^2 \cdot h_3(x)

항을 사용하는 방식을 '''삼중 해싱'''(Triple Hashing)이라고 부른다.^[4]

이러한 2차 항을 추가하면 해시 함수의 성능이 일부 개선될 수 있지만,^[3] 서로 다른 키가 충돌했을 때 동일한 순서로 다음 슬롯을 탐사하게 되는 근본적인 문제는 해결되지 않는다. 특정 조건에서는 서로 다른 두 키

x

와

y

가 동일한 탐사 시퀀스를 생성할 수 있다. 이는 다음 수식을 통해 확인할 수 있다.

만약 아래 조건들이 성립한다면:

:

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).

다음과 같이

y

에 대한

(k-i)

번째 탐사 위치와

x

에 대한

i

번째 탐사 위치가 같아지는 관계(

h(k-i, y) = h(i, 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}

따라서 삼중 해싱 역시 해시 테이블의 성능을 저하시킬 수 있는 클러스터링 문제를 완전히 해결하지는 못한다.

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

기존 이중 해싱에서 발생할 수 있는 문제를 해결하기 위해 3차 항

i^3

^[3] 또는

(i^3-i)/6

(사면체수)^[5]를 추가하는 방식을 '''향상된 이중 해싱'''이라고 한다. 이 방식은 서로 다른 키에 대해 해시 함수 집합이 동일하게 생성되는 가능성을 줄여준다.

향상된 이중 해싱은 전방 차분 기법을 활용하여 효율적으로 계산될 수 있다. 초기 해시 값

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)

과 유사한 좋은 분포 특성을 가지면서도 서로 독립적인 함수를 사용하는 것이 더 용이해진다.^[5]

참조

_[1] 논문 A Probabilistic Study on Combinatorial Expanders and Hashing http://phillipbradfo[...] 2007-04
_[2] 학위논문 Adaptive Approximate State Storage http://peterd.org/pc[...] Northeastern University 2010-12
_[3] 학술지 Less Hashing, Same Performance: Building a Better Bloom Filter https://www.eecs.har[...] 2008-09
_[4] 문서 Alternatively defined with the triangular number, as in Dillinger 2004.
_[5] 학회자료 Bloom Filters in Probabilistic Verification https://www.khoury.n[...] 2004-11-15

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com