선형 탐사법.

해시 테이블의 크기 M이 레코드의 개수 N보다 클때 사용하는 것으로 동일 주소로 해시되는 원소가 있으면 해시 테이블상의 오른쪽으로 이동하면서 비어있는 공간을 찾아서 첫번째로 만나는 빈 공간에 원소를 저장시킨다.

특징.

해시 테이블에서 할당된 공간이 연속해서 나타나는 뭉치가 있으면 이게 더 커지는 현상이 발생할수 있는데 이것을 집적화(클러스터링)라고 부른다. 이러한 집적화가 발생하게 되면 평균 탐색 시간을 증가시켜 성능을 저하시키게 된다.

ex.

레코드의 갯수 N=17일때 해시 함수를 h(k) = k mod 19라고 하자.

키값이 (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은 [2]에 들어간다.(1%19==1 인데 1자리에 이미 채웠으므로 그 바로 오른쪽인 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)
         while self.a[x] != -1:
             if v==self.a[x]:
                 return self.a[x]
             else:
                 x = (x+1) % M
         return -1
     def insert(self,v):
         x = hash(v,M)
         while self.a[x] != -1:
             x = (x+1) % 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 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()