이중 해싱

바로 앞의 선형 탐색법의 문제점은 집적화였다. 선형 탐사법에서 두 번째 이후에 탐사되는 위치가 첫 번째 탐사와 무관하다면 집적화 문제를 완화시킬 수 있다.

특징.

이중 해싱에서는 두 번째 탐사를 첫 번째 탐사와 무관하게 하기 위해 두 개의 해쉬 함수를 사용한다. 

ex.

레코드의 갯수 N=17일때 해시 함수를 h1(k) = k mod 19, h2(k) = 8 - (k mod 8) 이라고 하자.

키값이 (1, 19, 5, 1, 18, 3, 8, 9, 14, 7, 5, 24, 1, 16, 12, 5) 라고 하면....

1은 [1]에 들어간다.(1%19==1)

19는 [0]에 들어간다.(19%19==0)

5는 [5]에 들어간다.(5%19==5) (여기까진 선형 탐색법과 같다.)

그다음 1은 [8]에 들어간다.(1%19==1 인데 1자리에 이미 채웠으므로 그 다음을 찾기 위해 두번째 해쉬값을 더한다. 1+두번째 해쉬값인 7을 더하면 8이 되서 8에 들어간다.)

이런식으로 하나하나 채우는 방법이다.

아래 코드를 실행시켰을때 #가 나오는건 데이터가 찬 부분이고, 공백은 데이터가 없는 부분이다. 집적화가 조금 줄어들었으며 그로인해 수행 시간도 선형 탐색법(0.2초였다)에 비해 줄어들었다.

# -*- encoding: cp949 -*-
from __future__ import print_function
import random
import time
N = 10000
M = 10391

class Dict:
     def __init__(self):
         self.a = [-1 for i in range(M)]
     def search(self,v):
         x = hash(v,M)
         u = hash2(v)
         while self.a[x] != -1:
             if v==self.a[x]:
                 return self.a[x]
             else:
                 x = (x+u) % M
         return -1
     def insert(self,v):
         x = hash(v,M)
         u = hash2(v)
         while self.a[x] != -1:
             x = (x+u) % M
         self.a[x] = v
     def prints(self):
         for i in range(M):
             if self.a[i] != -1: print('#',end='')
             else: print(' ',end='')
             if (i+1)%70 == 0: print()
         print()
def hash(v,M):
    return v%M
def hash2(v):
    return (64 - (v%64))

def main():
    d = Dict()
    key = [-1 for i in range(N)]
    search_key = [-1 for i in range(N)]
    for i in range(N):
        key[i] = search_key[i] = random.randint(1,65536)
    for i in range(N):
        d.insert(key[i])
    d.prints()
    s = time.time()
    for i in range(N):
        result = d.search(search_key[i])
        if result == -1 or result != search_key[i]:
            print (result,i)
            print(u'탐색 오류. {} {}'.format(result,i))
    print(u'선형 탐사법의 실행 시간 (N = {} ) : {}\n탐색 완료.'.format(N,time.time()-s))

if __name__=='__main__':
    main()