Dynamic Hasing

동적해싱의 구체적인 구현방법에 대해서 설명.

동적해싱은 인덱스를 2진수료표현한다. 따라서 들어오는 키값을 hash함수에 넣고 돌린값을 2진수로 convert해야하며 2진수를 토대로 들어갈 인덱스를 결정하며 실제 인덱스에 mapping할때는 다시10진수로 convert하는 작업이 필요하다.

단, 그냥 변환하는것이 아니다. 현재 depth를 기준으로 변환해야한다.

예를들어, 11이라는 값이 들어왔을때, 11은 2진수로 1011로 표현되며 현재 depth가 2라고 가정했을경우에 가장끝자리서부터 2개만 파싱해야한다.

따라서 11로 변환되야하며, depth가 4라면 1011로 변환된다.

Operation : 

       transformToBinary(decimal) ::= 10진수를 2진수로 변환한다

extract(binary) ::= 변환된 2진수를 depth를 참고하여 비트를추출한다.

이제 데이터를 삽입할떄 인덱스는 hash함수의 결과를 토대로 2진수로 변환하여 적당한 자릿수를 추출하여 mapping될 것이다.

overflow가 발생할경우 무작정 디렉토리 사이즈를 늘려서 해결하는것이 아니다. 

디렉토리 사이즈는 들어갈 곳을 못찾았을떄 최후의 방법이다. 따라서 디렉토리 사이즈를 늘리지않고 들어갈수있는곳이 있다면 그곳에 들어가야하며 이것을 발견하는 알고리즘이 중요하다.

오버플로가 발생했을 경우 다음과 같은 방법을 설계하였다.

1. 오버플로된 버켓의 모든 데이터와 새로 삽입된 데이터를 모두 재분류 시킨다

2. 만약 1번에서 분류된 데이터중에서 현재 머물고 있는 인덱스와 재분류된 인덱스가 다르다면 디렉토리사이즈를 늘리지 앟고 대채공간을 찾았다는 것이다.

3. 2번에서 대채공간을 찾았다면 분류결과를 토대로 데이터를 다시 넣고 빼는 작업을 한다. 단, 데이터를 넣을때, 그 인덱스가 자신만의 버켓을 소유하고있지 않다면 새로 만들어준다.

1->2->3의 방법을 따라가되, 다음의 내용을 이해하는것이 중요하다.

**** 3번에서 재분류시키고, 기존버켓에 있던 데이터를 꺼내고 새로운 버켓에 넣을때 새로운 버켓에 대해서 버켓이 꽉 찾나 안찾나 볼 필요가 없다. 왜냐하면 이미 그전에 디렉토리를 확장했을때 오버플로가 되서 옮겨져야할 데이터는 다 옮겨졌기때문이다.

처음에 말했듯이 디렉토리의 확장은 최후의 방법이다. 즉, 데이터가 들어갈곳이없다면 디렉토리를 확장하여 해결해야한다.

여기서 부가적인 내용으로 중복되는 값에대한 처리도 함께 다루겠음.

이것에 대한 방법은 다음의 방법을 설계하고 해결하였다.

1. 디렉토리 사이즈를 2배로 늘린다.  
2. depth를 늘리고 삽입된 값에 대해서 비트수를 1개 늘려서 다시검사해서 들어갈공간을 찾는다.
3. 확장(새로할당된)된 디렉토리공간은 확장되기 이전의 디렉토리공간을 참조시킨다.
4. 들어갈 슬롯이 오버플로가 되는지 한번더 체크해준다.
5. 오버 플로우가되서 대채슬롯을 찾았다면 그곳에 넣는다. 여기서는 반드시 대채슬롯을 찾게 되있음. (위의 ****내용을 참조) 
6. depth를 늘리기전에 인덱스안에 중복된 데이터가 있으면 그 중복된 데이터도 같이 이동시켜준다. (이것이 중복된데이터대한 처리방법임)
7. 들어갈 공간이 오버플로가 아니면서 데이터가 중복이아니라면 hash함수의 결과값으로나온 인덱스로 그대로 들어간다.

위의 대한 전체적인 내용의 그림은 집필로 대채함.

              

마지막으로  체이닝기법과 동적해싱기법의 성능비교를 다룬다. 

먼저 다음의 이미지들은 동적해싱에 대한 결과화면이다.

첫번쨰사진은 삽입된 데이터는 0~30이며 depth는 2^4가 되었다.

두번째은 삽입된 데이터는 0~20이며 depth는 2^4가 되었다.

슬롯의 사이즈는 2로 잡았다.

이제 체이닝기법과 동적해싱기법의 성능비교화면이다.

먼저, 동적해싱에 대한 결과이다.

삽입된데이터는 0~8999이며, 디렉토리 사이즈는 2^13이 되었으며,  슬롯사이즈는 이전과 동일하게 2로잡았  다. 

탐색하는데 있어서 평균비교횟수는 1번이며, 디렉토리를 구축하는데 걸린시간은 0.057551초이다.

다음은 체이닝기법에대한 결과이다.  삽입된데이터는 0~8999이다.

사진이 커서 잘안보이기때문에 요약화면을 따로 캡쳐했다. 

평균비교횟수는 150번이며, 구축하는데 걸린시간은 0.013847초이다.

결론 :

체이닝기법과 동적해싱에대한 성능비교를 봤을때 결과내용은 명확하다.

동적해싱은 체이닝기법보다 탐색하는데있어서 훨씬 빠른속도를 보장한다. 

하지만 구축하는데있어서 시간비용은 체이닝기법이 더 우세하다.

왜냐하면 동적해싱은 메모리카피를 요구하기때문이다. 메모리카피는 되게 비싼연산이고, 또한 메모리를 재대로 복사하려면 인스턴스 혹은 구조체에 대해서 깊은복사(deep copy)를 수반해야하기때문에 시간을 많이잡아먹는다.