[자료구조] - Hash(해시)

 

 

 

 

 

들어가기에 앞서 해시가 어디에 쓰이는지 알아보도록 하겠습니다.

 

유튜브를 예시로 생각해 보도록 하겠습니다.

 

제가 어떤 사람의 동영상을 그대로 제 채널에 올리려고 한다면, 그 순간 바로 유튜브에서 중복되는 동영상이라는 에러 메세지를 보내줍니다.

 

동영상은 크기도 매우 크고, 그 수도 매우 많습니다.

그렇게 많은 동영상 중에서 어떻게 중복되는 동영상인지를 빠르게 판단할 수 있을까요?

앞으로 살펴볼 자료구조인 해시테이블이 바로 이것을 가능하게 만들어줍니다.

 

 

 

 

 

 

 

 

 

 

Hash Function (해시 함수)

해시 함수 (Hash Function) 또는 해시 알고리즘은 임의의 데이터를 배열의 인덱스로 매핑(변환)하는 함수입니다.

 

해시 테이블은 배열입니다.

따라서 인덱스를 통해 접근할 때에는 O(1)의 시간복잡도로 매우 빠르게 접근할 수 있습니다.

 

 

 

 

 

 

 

정수가 아닌 임의의 데이터를 정수로 만드는 함수

임의의 데이터를 Hash Code(정수값)으로 바꾸는 함수를 의미합니다.

 

어떠한 데이터에 대하여 해당 데이터가 조금이라도 변화할 경우 해당 데이터의 해시코드는 매우 크게 달라집니다.

 

이러한 현상을 눈사태 효과(Avalanche effect)라고 부릅니다.

 

 

 

 

 

 

 

데이터가 가변 길이 혹은 매우 긴 문자열인 경우

이러한 경우 대부분 복잡한 종속관계로 인해 이를 그대로 정수로 변환할 경우 분포가 균일해지지 않습니다.

 

이러한 데이터의 경우 문자열의 모든 문자에 의존하고 각 문자에 다른 방식으로 의존하는 해시 함수를 사용하는 것이 현명합니다

 

대표적인 방법으로는 각 문자열에 오버플로를 무시하고 다음 문자를 추가하기 전에 해시 합계에 상수(일반적으로 상당한 소수)를 곱하는 것입니다.

 

자바에서는 다음과 같이 사용합니다.

31을 사용하는 이유는 소수이면서 홀수이기 때문입니다. 

홀수가 선택되는 이유는 짝수를 곱하는 경우 이진수이므로 비트가 쉬프트되어 기존 해시값의 정보가 사라질 수 있기 때문입니다.
그러나 꼭 소수일 필요는 없습니다.
합성수로 사용하는 사례도 있다고 합니다만, 그저 관행적으로 31을 사용한다 보시면 될 것 같습니다.

 

해당 함수의 최종 과정은 나머지 연산 혹은 이후 배울 middle of square 등의 정수값을 해시테이블 크기의 인덱스로 매핑하는 함수가 될 것입니다

 

 

 

 

 

 

정수값을  배열의 인덱스로 매핑하는 함수

데이터의 Hash Code를 배열의 인덱스 (0 이상의 정수)로 변환해주는 함수입니다.

 

보통 나머지 연산을 사용하며, 이때 나누는 값은 20 이상의 소수의 곱이 권장된다고 알려져 있습니다.

hash = key.hashcode()
index = hash % hashTable.length;

 

 

 

 

 

 

 

위의 두 함수의 조합을 보통 해시 함수라 부릅니다.

즉 다음과 과정을 거쳐 임의의 데이터는 인덱스로 매핑됩니다.

key -> (function 1) -> hashcode(integer) -> (function 2) -> index in hashtable

(일반 정수의 경우 그 자체로 인덱스가 될 수도 있으므로, 해당 경우에는 정수값을 인덱스로 매핑해주는 함수만 사용될수도 있습니다.)

 

 

 

 

 

 

 

 

 

 

 

Hash Table

(자바에 존재하는 Hash Table 클래스가 아닙니다)

 

해시 테이블은 아래 그림과 같이 여러 Bucket(버킷)을 가지고 있으며, 실제 key에 해시함수가 적용되어 반환된 인덱스를 통해 버킷에 저장하고, 조회하는 등의 연산을 수행할 수 있습니다.

 

이러한 버킷들은 배열의 형태로 존재하므로 추가, 삭제, 조회등의 연산이 O(1)의 시간복잡도로 가능해집니다.

 

Hash Table은 사실 다음과 같이 하나의 Bucket속에 여러 Slot이 존재할 수도 있습니다.

그러나 대부분의 경우, Slot의 크기는 1입니다. 즉 Slot이 없다고 봐도 무방합니다.

 

 

 

 

 

 

 

 

 

 

 

Identifier Density & Loading Factor (식별자 밀도 & 부하율)

T와 n을 정의하겠습니다.

T : 어떠한 프로그램에서 가능한 모든 식별자(identifier)의 개수
n : 실제 사용하는 식별자의 개수

 

 

 

Identifier Density

$$\frac{n}{T}$$

대부분의 경우 Identifier Density는 매우 작은 수이므로, 고려하지 않아도 됩니다.

 

 

 

 

Load Factor

(s와 b는 각각 Hash Table의 slot과 bucket의 수로, 대부분의 경우 s = 1 입니다.)

$$\frac{n}{sb}$$

 

 

 

예시

버킷의 수가 26개, slot의 개수가 2개인 Hash Table을 생각해 보겠습니다.(n은 10이라 가정하겠습니다)

 

해당 해시 테이블을 사용하는 프로그램은 식별자를 만들 때 3개의 영어 대문자 혹은 숫자를 사용해서만 만들 수 있으며, 이때 만드시 맨 앞글자는 영어 대문자가 와야 한다고 가정하겠습니다.

 

이때 해당 프로그램에서 가능한 모든 식별자의 개수는 다음과 같습니다.

$$T = 26 + 26 \cdot (26+ 10) + 26 \cdot (26+ 10) \cdot (26+ 10) = 34658$$

 

이 경우 Identifier Density는 다음과 같습니다.

$$\frac{n}{T} = \frac{10}{34658} = 0.00003$$

 

Load Factor는 다음과 같습니다.

$$\frac{n}{sb} = \frac{10}{2\cdot 26} = 0.19$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Collision (충돌)

서로 다른 식별자에 해시 함수를 적용하였을 때, 동일한 값이 나오는 경우, 즉
동일한 버킷에 매핑되는 경우 충돌(Collision)이 발생했다고 합니다.
$$I_1 \neq I_2 \;\; but\;\; f(I_1) = f(I_2)$$

 

프로그램에서 사용 가능한 식별자의 수는 셀 수 없을 정도로 많습니다.

예를 들어 자바의 경우만 해도 변수를 생성할 때, 가능한 가짓수가 굉장히 많다는 것을 아실겁니다.

이러한 모든 식별자들을 해시 테이블의 다른 버킷에 넣기 위해서는 식별자들의 수만큼의 공간이 해시 테이블에 존재해야 합니다.

그러나 이는 너무 많은 메모리를 차지하며, 사실상 할당 자체도 안될 것입니다.

 

 

결국 식별자들의 수보다 해시 테이블의 버킷의 수가 적기 때문에, 서로 다른 어떠한 식별자들은 해시 테이블의  동일한 버킷에 저장될 수밖에 없습니다. (비둘기집 원리)

 

 

 

두개의 식별자 $I_1$ , $I_2$ 에 대하여 각각에 해시함수(hash function) f를 적용한 결과가 동일한 경우, 즉 다음과 같을 때
$$f(I_1) = f(I_2)$$
$I_1$ 과 $I_2$ 는 f에 대한 Sysnonyms(동의어)라고 부릅니다.

 

 

 

 

 

 

 

 

 

 

 

Overflow (오버플로)

어떠한 식별자에 해시함수를 적용하여 매핑된 버킷이 이미 가득 차 있는 경우, Overflow가 발생했다고 합니다.

 

 

 

Overflow와 Collision의 차이

Collision은 해시 함수의 결과가 동일한 값인 경우, 즉 동일한 버킷에 매핑된 상황을 의미하며,

Overflow는 Collision이 발생하였을 때, 해당 버킷이 이미 가득 차 저장이 불가능한 상황을 의미합니다.


즉 Overflow가 발생하였다면 Collision 역시 발생한 것이지만,
Collision이 발생하였다고 해서 Overflow가 발생한 것은 아닙니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Perfect Hash Function (완전 해시 함수)

서로 다른 모든 식별자들을
서로 다른 버킷으로 대응시키는 해시 함수를 Perfect Hash Function이라고 합니다.

 

이를 가능하게 하기 위해서는 해쉬함수를 정의하기 전에 정의된 식별자들의 집합을 알고 있어야 합니다.

 

그러나 이는 매우 큰 저장공간을 필요로 하며, 메모리 낭비가 심하기 때문에, 거의 사용하지 않습니다. 

 

앞으로는 완전 해시 함수를 고려하지 않은 체, 설명을 이어가도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

좋은 해시 함수에 대해서

Collision을 최소화하기 위해
해시 테이블에서 식별자들이 균등한 분포(Uniformly distributed) 를 갖도록 하며
계산하기 쉬워야 합니다.

 

위에서 살펴보았듯이 해시 함수는 결국 다대1(Many-to-One) 매핑이며,

따라서 비둘기집 원리에 의해 Collision은 반드시 발생할 수밖에 없습니다.

 

이때 발생하는 Collision의 수를 최대한 줄이는 것이 필요합니다.

 

 

Collision을 최소화하기 위해서는 식별자들을 해시 테이블에서 균등하게 분포(Uniformly distributed)시켜야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Uniform Hash Function (균등 해시 함수)

정수값(혹은 이진수)을 해시테이블의 인덱스에 매핑해 주는 함수이며 다음을 만족시켜야 합니다.

해시 테이블의 버킷의 수 b와, 해시 함수 f에 대하여

만약 x가 임의로 선택된 식별자라면, 해당 식별자에 f를 적용하여 임의의 인덱스 i가 나올 확률은 $\frac{1}{b}$ 여야 합니다.
$$P(f(x) = i) = \frac{1}{b}$$

 

Uniform Hash Function은 여러 종류가 있으며, 그중 3가지 함수에 대해서 알아보도록 하겠습니다.

• Division
• Middle of Square
• Folding

 

 

 

 

 

 

 

Division

버킷의 크기 b를 M이라 정의하겠습니다.

Division 방식의 Hash Function은 다음과 같습니다.
f(X) : X modulo M  

(modulo는 나머지 연산을 의미합니다.)
(X는 음이아닌 정수입니다.)

 

해당 방식에서 M을 선택하는 것이 매우 중요합니다.

결론부터 말하면 다음이 권장됩니다.

20 이상의 소수(prime number)들의 곱을 선택하는 것으로 충분합니다.

 

만약 M을 2의 k제곱으로 정한 경우, 해시함수의 결과는 X의 오른쪽 k비트를 사라지게 만듭니다.

그 결과 해시 함수는 X의 모든 값을 반영하지 못하며, 이는 해시값을 균등하게 분포하지 못합니다.

 

 

대부분의 경우 Division 방식이 가장 쉬우며, 권장되는 방식입니다.

 

 

 

 

 

 

 

 

Middle of Square

버킷의 크기 b를 다음과 같이 정의합니다.
$$b = 2^{r}$$

Middle of Square 방식의 Hash Function은 다음과 같습니다.
f(X) : X(이진수)를 제곱한 값에서 가운데 r비트를 취한 값

 

 

 

 

버킷의 크기를 2의 제곱수로 정해준 이유는 다음과 같습니다.

n비트 이진수로 표현할 수 있는 값의 범위(음수 부호 X)
$$0 \sim 2^{n} - 1$$

 

 

따라서 Middle of Square 방식으로 해시값을 생성하면 그 값의 범위는 다음과 같습니다.

$$0 \leq f(X) \leq 2^{r}-1$$

 

$X^2$ 의 가운데 비트들은 X를 표현하는 모든 이진수를 반영하게 되므로 Middle of Square 방식으로 생성된 인덱스는 균등한 값을 가질 수 있습니다.

 

 

 

 

 

 

 

Folding

X를 특정한 길이로 쪼갭니다.
이후 해당 쪼갠 각각의 부분을 모두 더합니다.

 

Folding은 Shift Folding과 Folding at boundary의 두 가지 방법이 있습니다.

 

각각의 예시는 다음과 같습니다.

X = 12320324111220 이라고 하겠습니다.
3자리씩 끊어서 더하겠습니다. 즉
$$X_1 = 123, \;\; X_2 = 203\;\; X_3 = 241\;\; X_4 = 112\;\; X_5 = 20$$

Shift Folding
단순히 더하면 됩니다.
$$f(X) = 123 + 203 + 241 + 112 + 20 = 669$$

Folding at Boundary
종이를 접는 느낌으로 한번은 그대로, 한번은 역으로 더하는 것을 반복합니다.
f(X) = 123 + 302 + 241 + 211 + 20 = 897

 

 

 

 

 

 

 

 

 

 

 

지금까지는 Collision의 발생을 최소하는 방법을 살펴보았습니다.

그러나 결국 완전 해시 함수를 만들지 않는 이상 Collision은 발생할 것이고, 따라서 Overflow도 발생할 것입니다.

 

이제부터는 Overflow가 발생했을 때 이를 어떻게 해결하는지 확인해 보도록 하겠습니다.

 

 

 

 

 

Overflow Handling 

Overflow를 해결하는 방법은 크게 두 종류로 구분됩니다.

• Close Hashing (Internal Hashing) (Open addressing)
• Open Hashing (External Hashing) (Closed addressing)

 

 

 

 

 

 

 

 

 

 

 

 

Close Hashing (Open addressing) (폐쇄 해싱 혹은 개방 주소법)

주어진 해시 테이블 내의 메모리 공간 속에서 Overflow를 해결하는 방법을 의미합니다.

즉 테이블 내 고정된 공간 내에서 해결하는 것이므로 공간이 닫혀있다고 하여 Close Hashing입니다.

 

종류는 다음과 같습니다.

• Linear Probing (Linear Open Addressing) (선형 탐사)
• Quadratic Probing (제곱 탐사)
• Rehashing (재해싱, 이중 해싱)
• Random Probing (임의 탐사)
• ...

 

 

 

 

 

 

 

 

 

 

Linear Probing (선형 탐사)

Overflow가 발생했을 때 이후 존재하는 버킷들 중에 비어있는 버킷을 선형적으로 탐색하여 삽입하는 방법입니다.

매우 간단하게 Overflow를 해결할 수 있으나 여러 단점이 존재합니다.

먼저 비어있는 버킷을 찾기 위한 비교 연산의 횟수가 많아질수록, 오랜 시간이 걸립니다.

또한 데이터의 삭제 연산이 발생한다면, 이후 검색 시 데이터가 존재함에도 이를 찾지 못하는 상황이 발생합니다.

 

 

예시

식별자는 반드시 첫 글자가 영어 대문자로 시작하며, 해시함수는 첫글자에 해당하는 영어의 순서를 반환한다 가정하겠습니다.

즉 Axx -> 0, Bxx -> 1, ... , Zxx -> 25 입니다.

 

다음과 같은 26개의 버킷을 가진 해시테이블을 가정하겠습니다.

 

 

입력열(sequence)은 다음과 같습니다.

GA -> D -> A -> G -> E -> A2 -> A1 -> A3 -> Z -> ZA

 

 

 

위와 같은 상황에서, A2를 제거해 보도록 하겠습니다.

 

이 상황에서 A1을 찾을 수 있을까요???

 

A1을 찾기 위해서는 우선 0번 위치에 가서 A와 비교합니다. 존재하지 않는다면 이후 존재하는 버킷을 탐색해야 하는데, 1번 버킷이 비어있으므로 존재하지 않는다고 판단해 버립니다.

 

 

 

 

 

 

 

선형 조사의 비교 연산을 줄이기 위해, Quadratic Probing, Rehashing, Random Probing 등의 방법을 사용합니다.

 

 

 

 

 

어떠한 종류의 방법을 사용하든 Close Hashing에서는 식별자를 다른 해시값을 가진 식별자와 비교하는 과정을 피할 수 없습니다.

이 문제를 해결하기 위해 Close Hashing보다는 Open Hashing을 사용합니다.

 

 

 

 

 

 

 

 

 

 

 

Open Hashing (Closed addressing) (개방 해싱 혹은 폐쇄 주소법)

별도의 메모리를 할당하여 필요한 만큼 사용하는 방법입니다.

LinkedList와 비슷하게 연결 체인을 사용하여 Overflow를 해결합니다.

이를 Chaining 기법 이라고 합니다.

자바의 HashMap은 기본 최대 적재율이 0.75인 폐쇄주소법을 사용합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

Static Hash

위에서 살펴보았던 방법들이 모두 Static Hash 입니다.

고정 크기의 배열을 이용한 방법으로, 해시 테이블의 버킷의 수를 고정시켜 사용하는 방법입니다.

그러나 이는 데이터의 수가 증가함에 따라 효율이 떨어지게 됩니다.

 

위의 예시에서 Close Addressing 방법을 사용하여 Overflow를 해결하는 경우, 결국 데이터의 수가 많아지면 Overflow Chain도 길어질 것이며, 이는 데이터의 탐색에서 많은 시간이 소요될 것입니다. 

 

이를 해결하기 위해 해시테이블의 부하율 (Load Factor)를 70~80% 정도로 유지하며,
이를 초과할 경우 새로운 크기의 해시테이블을 생성하여
기존 해시테이블에 존재하던 모든 원소들에 대해서 재해싱을 거쳐 해시테이블을 재구성해주는 작업이 필요합니다.

 

해시 테이블을 제구성하는 과정에서 모든 원소들에 대하여 rehash하는 과정은 매우 비효율적입니다.

 

Dynamic Hash에서는 모든 원소가 아닌 단일 버킷에 대해서만 재해싱을 해주는 방식으로 작동하여,

Static Hash에 비해 효율적으로 동작합니다.

 

 

 

 

 

 

 

 

 

 

 

 

Dynamic Hash

데이터의 증감에 따라 배열의 크기를 동적으로 변화시키는 방법입니다.

즉 버킷의 수를 고정하지 않고, 필요한 경우 늘리거나 줄일 수 있습니다.

Static Hash와 달리 데이터가 증가하였을 때 해시테이블을 재조정 하는 과정에서,
모든 원소들에 대해 재해싱을 하는것이 아닌
한번의 Overflow에 하나의 Bucket의 원소들에 대해서만 재조정하여 Static Hash에 비해 효율적으로 작동합니다.

 

Dynamic Hash는 크게 Directory를 사용하는 해시 방법과

Directory를 사용하지 않는(Directoryless) 해시 방법으로 나눌 수 있습니다.

 

 

대표적으로는 다음과 같습니다.

Directory 사용      : Extendible Hashing (확장 해싱)
Directory 사용 X  : Linear Hashing (선형 해싱)

 

 

 

 

Dynamic Hashing은 데이터베이스에서 주로 사용됩니다.

 

 

 

 

 

 

Dynamic Hash에서의 Hash Funtion

Hash Function인 $h(k, p)$ 를 정의합니다.

 

$h(k)$  : hash function

$h(k, p)$  : $h(k)$ 의 값에서 최우측 p비트만을 사용하는 hash function

예시

h(k)가 다음과 같을 때

$h(A0, 2) : 00 = 0$
$h(A1, 2) : 01 = 1$
$h(B0, 2) : 00 = 0$
$h(C1, 4) : 0001 = 1$
$h(C1, 5) : 10001 = 17$
$h(C1, 6) : 110001 = 49$
...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Extendible Hashing (확장 해싱)

Directory를 사용하며, Directory에는 Bucket에 대한 주소(Pointer)가 들어있습니다.

 

Directory는 메모리에 존재하며, Bucket은 대부분의 경우 Disk에 존재합니다. 

 

(메모리 용도로 사용할 수도 있으나 Dynamic Hash는 대부분의 경우 데이터의 개수가 매우 많은 경우에 사용하므로, memory 용도로는 잘 사용하지 않습니다.)

 

$h(k, p)$를 사용할 경우,
Directory Size : $2^p$
Directory Depth : p

 

 

 

 

 

데이터를 검색하는 방법

$h(k, p)$ 를 적용하여 값을 찾습니다.

(앞으로의 모든 예제에서 Bucket의 slot의 수는 2개입니다.)

B1을 찾아보도록 하겠습니다.

$h(B1, 2) = 01 = 1$ 
즉 d[1]이 가리키는 Bucket의 주소로 이동하여 B1을 탐색합니다.
이 경우 존재하므로 찾을 수 있습니다.

 

 

 

 

 

 

 

Overflow를 해결하는 방법

이 상황에서 C5를 추가해 보도록 하겠습니다.

$h(C5, p)$ 를 구합니다. 

위의 경우 $h(C5, 2) = 01 = 1$ 이므로 d[1]에 추가해야 합니다.

추가하려고 d[1]의 Bucket으로 이동하였는데, 이미 Bucket이 가득 차 있는 상황입니다.
즉 Overflow가 발생하였습니다.

이 경우 directory의 크기를 확장해야 합니다.

확장할 directory의 크기를 결정해야 합니다.
Overflow가 발생한 Bucket에 존재하는 원소들만 대상으로 이들을 구별 가능하게 하는 최소 비트 u를 결정합니다.

h(A1) = 100001
h(B1) = 101001
h(C5) = 110101

이 경우 u는 3입니다.

이제 p를 u로 바꾸어줍니다.
위의 경우 p가 3으로 바뀌므로, Directory Size는 $2^3 =$  8이 됩니다.
추가된 크기만큼 Directory를 복사합니다. 

복사된 후

Directory를 복사한 것이므로 Disk에 존재하는 Bucket은 그대로 유지됩니다.

 

 

복사 이후 Overflow가 발생한 버킷을 재조정합니다.
Overflow가 발생한 버킷에 대해서 증가된 p를 적용한 $h(k, p)$ 를 통해 재해싱을 진행하여 재배치합니다.

위의 경우에
$h(A1, 3) = 001 = 1$
$h(B1, 3) = 001 = 1$
$h(C5, 3) = 101 = 5$
입니다.

재조정 후의 모습입니다.

위의 예시에서는 우연히 A1과 B1의 위치가 바뀌지 않았지만, 만약 B1이 101101 이었다면 B1도 d[5]의 위치로 이동했을 것입니다.

 

 

 

 

 

 

Extendible Hashing 요약

Overflow가 발생하였을 때는 발생한 Bucket에 대해서만 rehash를 진행합니다.

검색의 경우 Disk 접근이 1회만 발생합니다.

데이터를 추가하는 경우 Overflow가 발생하였을 때
1번의 Disk 읽기와, 2번의 Disk 쓰기 접근이 발생합니다.

Directory를 복사하는 과정을 Disk Access가 발생하지 않습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Linear Hashing (선형 해싱)

Directory를 사용하지 않는 Hashing입니다.

즉 Disk에 존재하는 Bucket의 주소를 가진 Directory를 사용하는 대신 해싱의 결과로 나오는 값을 가지고 운영체제의 도움을 받아 Disk에 직접 접근합니다.

 

Linear Hashing에서는 더이상 확장될 가능성이 없는 가능한 가장 거대한 배열 ht[]를 가정합니다.

Active Buckets과 Overflow Buckets이라는 두가지 개념을 사용합니다.
그리고 이를 위해 두 변수 q, r을 정의합니다.
이 두 변수 사이에는 다음 관계식이 성립합니다.
$$0 \leq q < 2^{r}$$

 

 

 

Active Bucket(활성 버킷)

배열 ht에서 다음 인덱스에 해당하는 부분을 Active Buckets으로 사용합니다.
$$ht[0] \;\sim\; ht[2^{r}+q-1]$$

각각의 Active Bucket에는 bucket chain의 시작이 들어있습니다.

예를 들어 r=3, q=5인 경우

Active Buckets은 ht[0]~ht[12]입니다.

 

 

 

 

 

 

Overflow Bucket

Active Bucket에서  bucket chain의 시작을 제외한 나머지를 Overflow Bucket이라 부릅니다.

Overflow가 발생한 경우, 이미 해당 버킷이 가득 찬 상태하면 overflow된 데이터를 chaining합니다. 

이미 chaing된 Overflow Bucket이 존재하는 경우, 이어서 연결합니다.

 

그런데 이러면 static hash에서의 closed addressing 방법과 다를 바 없어보입니다.

이에 대한 의문은 조금 뒤어 풀어보도록 하겠습니다.

 

 

 

 

 

 

 

인덱싱(Indexing)

$h(k, r+1)$  : q가 0이 아닌 경우, 다음 범위의 인덱싱에 사용합니다. 
$$ht[0] \;\sim\; ht[ q-1 ],\;\;  ht[ 2^r ] \;\sim\; ht[ 2^r + q-1 ]$$

$h(k, r) $ :
$$ht[q]  \;\sim\;  ht[2^r -1 ]$$

r=3, q=5인 경우

 

 

 

 

 

검색

우선 $h(k, r)$ 을 적용합니다.

$h(k, r)$ 의 결과가 q보다 작다면 , $h(k, r+1)$을 적용한 결과로 나오는 값을 통해 ht에서 탐색합니다. 
$$ht[\;h(k,\;r+1\;)\;]$$

$h(k, r)$의 결과가 q이상이라면 ,해당 결과를 통해 ht에서 탐색합니다.
$$ht[\;h(k,\;r\;)\;]$$

 

 

 

 

 

 

 

 

 

 

Overflow 대처

Overflow가 발생한 경우 Active Bucket을 1개 증가시켜 해결합니다.

Active Bucket이 증가하였을 때, 증가된 위치에서 $2^r$  전에 존재하는 Active Bucket과
이에 Chaining된 Overflow Buckets의 원소들에 대해서만 rehash하여 Hash Table을 재구성합니다.

Active Bucket을 1개 늘렸음에도 Overflow가 해결되지 않았다면 Overflow chain으로 연결합니다.

 

 

Actvie Bucket을 1개 증가시킨다는 것은 q를 1 증가시키는 것과 동일하며,
만약 증가시킨 q의 값이 $2^r$ 과 동일한 경우 r을 1 증가시키고 q는 0으로 바꿉니다.

 

 

 

 

다음 Hash Table을 예시로 살펴보겠습니다.

r=2, q=0

 

 

 

이 경우 C5를 삽입해 보도록 하겠습니다.

$h(C5, 2) = 01 = 1$ 

이는 q 이상이기에 해당 값을 그대로 인덱스로 사용합니다. 즉 h[1]을 사용합니다.

그러나 해당 위치로 이동해보니 이미 Bucket이 가득 찬 상태이므로 Overflow가 발생했습니다.
Overflow가 발생했기에 Active Bucket을 1개 늘립니다.

 

 

Active Bucket이 증가하였으므로, 해당 위치에서 $2^r$  이전에 존재하는 Bucket에 대해서 rehash를 진행합니다.

 

위의 예시에서는 증가된 Active Bucket이 ht[4]이므로, $2^2$ 를 뺀 ht[0]에 대하여 rehash를 진행합니다.

 

 

rehash 진행 완료

중요한 점은 Overflow는 h[1]에서 발생하였는데, rehash는 h[0]의 버킷에서 진행되었다는 것입니다.

즉 이를 통해 다음 중요한 사실을 알 수 있습니다.

Linear Hashing에서는 Overflow가 발생한 Bucket과 rehash되는 Bucket이 동일하지 않을 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference

https://en.wikipedia.org/wiki/Hash_function

Hash function - Wikipedia

https://www.cpp.edu/~ftang/courses/CS240/lectures/hashing.htm

CS240: Data Structures & Algorithms I

 

https://stackoverflow.com/questions/24555783/hashmap-hashcode-to-internal-table-index-conversion#

Hashmap hashcode to internal table index conversion

http://faculty.tamuc.edu/dcreider/csci520/Note520/Note%207.htm

Note 7: Hash Algorithms in Data Structure for Application

https://searchall.tistory.com/74

[박혜웅] 최소 완전 해쉬 함수 (Minimal Perfect Hash Function)

https://programming.guide/hash-tables-open-vs-closed-addressing.html

Hash Tables: Open vs Closed Addressing | Programming.Guide