Data Structure - Hashing ( Dynamic Hashing )

Dynamic Hasing

여지것 우리는 배열(bucket)의 사이즈를 바꾸지 않는 Static Hashing에 대해 알아보았습니다.

 

우리는 좋은 성능을 내기 위해서, hash table의 사이즈를 늘려주어야 할 필요가 있게 됩니다. loading density가 이미 정해진 경곗값 이상으로 올라가게 되면 말이죠.

 

• 예를 들어서 b개의 bucket과 divisor D = b -> 2b + 1가 되어야 합니다. D = 2b + 1로 array doubling을 해주어야 합니다.
• 우리는 해시 함수도 다시 구축해야 합니다. 모든 쌍들을 다시 만든 해시 함수에 다시 매핑시켜주어야 합니다.

이 Dynamic Hashing에는 2가지 방법이 있습니다.

• Dynamic hashing using directories
• Directoryless dynamic hashing

이제 이것들이 어떻게 구성되는지에 대해 알아보도록 하겠습니다.

들어가기 전에 ( 간단한 예시 )

기본적으로 정적 해싱은 충돌에 대비한 여러가지 해시 함수를 제시했습니다. 이차 조사법이나, 재해싱, 체인법,... 충돌을 허용하지만, 이를 최소화하기 위해 이와 같은 방법을 사용했습니다.

 

하지만 정적 해싱의 가장 큰 문제점은 데이터를 입력하기 전에 메모리를 미리 할당받아야 하며, 추가 적인 데이터 삽입으로 인해 해시 테이블의 크기가 할당된 메모리 크기를 넘어갈 수 있습니다. 이럴 경우 해시 테이블의 크기를 증가하고, 기존의 값들을 새로 만든 큰 해시 테이블에 재조정하여 삽입하는 문제점이 생깁니다. 이럴 경우 굉장한 시간적, 시간적 낭비가 일어나게 됩니다.

 

이러한 문제점을 해결하기 위해 동적해싱이 등장합니다. 동적 해싱 확장성 해싱이라고도 하며 재조정을 한 번 할때마다 오직 충돌(오버플로)이 일어난 버킷 안의 엔트리들만 재조정하고, 동적으로 해시 테이블의 크기를 변화시키면서 전체적으로 성능을 높여줍니다.

 

주로 디렉토리를 사용하여 동적 해싱을 구현합니다.

 

기본적으로 디렉토리는 깊이라는 변수를 가집니다. 이 깊이에 따라 디렉토리의 크기가 결정됩니다.

각 버킷에 데이터를 2개까지 삽입 가능하다고 설정하겠습니다. (s = 2)

 

우선 삽입하여야 할 데이터를 순서대로 8, 12, 7, 6, 5, 11, 3이라고 합시다. 

각각을 이진수로 바꾸면 1000, 1100, 0111, 011,0, 0101, 1011, 0011이 됩니다.

보통 디렉토리 깊이 비트만큼 최우측 비트(LSB)가 인덱스가 됩니다.

 

초기에 디렉토리 깊이를 1로 잡습니다. 1비트에서는 0과 1만 쓸 수 있습니다.

이 상태에서 8(1000)을 삽입하면 인덱스가 0이므로 0번 디렉토리가 가리키는 위치에 삽입됩니다.

다음에 12(1100)을 삽입해도 1100에서 최우측 1비트가 0이므로 0번 디렉토리에 삽입됩니다.

이제 7(0111)을 삽입하면 1번 디렉토리에 들어가게 됩니다.

다음 순서는 6(0111)입니다. 6은 인덱스가 0이므로 다음과 같이 삽입됩니다.

오버플로가 발생하게 됩니다. 디렉토리의 크기를 2배로 하고 버킷의 내용을 재조정해야 합니다.

이 때 중요한 것은 오버플로가 발생한 버킷에 대해서만 재조정한다는 것입니다!!

 

1. 디렉토리를 2배로 늘립니다.
2. 포인터가 가리키는 테이블 값을 그대로 복사합니다.
3. 데이터의 해시값을 통해 데이터를 재조정합니다. 필요할 경우 새 버킷을 생성합니다.
4. 새로 생성된 버킷이 있으면 해당 버킷에 대한 포인터로 변경합니다.
5. 오버플로가 해결되면 끝. 또 오버플로가 발생한다면 이 과정을 반복해 주면 됩니다.

이제 5를 삽입해봅시다. 5는 이진수로 0101이니까 01디렉토리가 가리키는 곳에 들어갈 겁니다.



다음 순서는 11입니다. 11은 1011이니까 11디렉토리가 가리키는 곳에 들어가야 합니다.

오버플로가 발생했습니다. 당연히 디렉토리의 크기를 늘려야 겠다고 생각합니다. 하지만 아닙니다.

 

디렉토리의 크기를 늘리기 전에 점검해야 할 사항이 하나 있습니다.

현재 같은 곳을 가리키는 디렉토리의 비트로 데이터를 분류할 수 있다면 굳이 늘릴 필요가 없게 됩니다.

7은 0111, 5는 0101, 11은 1011이므로 7과 11은 이진수 11로 분류할 수 있고, 5는 01로 분류할 수 있게 됩니다.

따라서, 아래와 같이 버킷이 하나 더 생성됩니다. 당연, 포인터도 변경됩니다.

마지막으로 3을 삽입해 보겠습니다. 3은 이진수로 0011이니다. 

이제 굳이 그림을 그리지 않아도 알 수 있듯이 11이 가리키는 버킷에 오버플로가 발생합니다.

그리고 디렉토리 깊이가 2인 상황에서는 포인터를 아무리 조정해도 오버플로를 해결할 수 없습니다.

이럴때는 당연히 디렉토리 크기를 2배로 늘려주고, 오버플로된 버킷만 재조정 해줍니다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=skyjjw79&logNo=220875535595 

Dynamic Hashing Using Directories

우리는 일단 key를 음수가 아닌 정수로 mapping시켜 주는 h(k)을 정의할 필요가 있게 됩니다. 

• 일단 h의 범위는 충분히 크다고 해 봅시다.
• 또한 h(k, p)를 h(k)로 나오는 값의 least significant bit라고 해 봅시다.

h(k)는 2개의 문자로 이루어진 키들을 6비트의 음수가 아닌 정수들로 바꾸어 줍니다.

 

또한 directory d는 bucket을 가리키게 됩니다. 이러한 디렉토리는 h(k)가 사용하는, p에 의존하게 됩니다.

eg) h(k, 2) -> size of 2^2 = 4, h(k, 5) -> size of 2^5 = 32

 

여기서 사용되는 directory depth는 h(k)가 directory에서 사용하는 인덱스와 같은것이라고 보시면 됩니다.

t가 directory depth라고 하면 2^t개가 directory의 size가 됩니다.

그리고 bucket size b는 2^t보다 작거나 같아야 합니다.

dynamic hash table of s = 2, t = 2

이제 위 상황에서 예시를 한번 들어봅시다.

C5을 Insert

이 과정에서 C5( 01 )인데 overflow가 발생하게 됩니다. 그러면 나머지 중에 11로 갈 수 있는 것을 찾아보지만, 없습니다. 무조건 Array doubling을 해야 하는 상황입니다.

그래서 doubling을 하고 새 bucket을 하나 만들고 C5을 101과 매칭시켜 줍니다. 그리고 나머지는 포인터가 가리키는 테이블은 그대로 복사 합니다.

 

C1을 Insert

여기서는 조금 상황이 다릅니다 C1을 추가하는데 C1은 01입니다. 그래서 Array doubling을 해서 t=  3으로 depth를 3으로 증가 시켰는데 도, A1, B1, C1모두 001입니다. 아직도 overflow가 일어나는 상황인 것입니다. 따라서 doubling을 한번 더 진행해 줍니다. 그러면 t = 4인 상황이 될 것이고, A1, B1, C1은 각각 0001, 1001, 0001이 됩니다. 그래서 1001만 B1과 매칭되고 나머지는 포인터가 가리키는 테이블 그대로를 가리키면 됩니다.

또한 다음과 같은 상황에서 C4와 C1이 각각 추가된다면 어떻게 hash table이 구성될지 한번 풀어보았습니다.

C4는 100이니까 그냥 home bucket하나 만들어 준다음에 포인터를 테이블과 연결해 주기만 하면 됩니다. 하지만 C1을 추가하는 상황에서는 C1은 001인데 overflow가 일어납니다. 하지만 들어갈 수 없고 이를 가리키는 포인터가 001하나뿐이므로 무조건 array doubling이 일어나야 합니다. 따라서, t = 4가 되고 이 때 A1은 0001, B1은 1001, C1은 0001입니다. 따라서 C1을 0001로 꼬라박고, B1을 1001로 재구성 해주면 됩니다.