해시 테이블

1. 해시 테이블?

검색트리는 원소가 저장될 자리를 이미 트리에 존재하는 값들과 비교하면서 리프까지 내려가서 자리가 결정된다. 이방법은 평균적으로 Θ(logn)의 시간이 걸리게 된다. 하지만 우리가 아는 배열에 값을 넣는 것은 Θ(n)의 시간이 걸린다. 이 배열을 이용하는 것이 해시 테이블이다. 

우선 해시 테이블에 값을 저장하려면 해당 원소의 해시 값을 계산해야 한다. 해시값은 함수로 계산하게 되는데 해시 테이블이 m개의 원소를 저장할 수 있다면 함수는 m-1까지의 값을 return한다. 예를들어 17개의 원소를 저장할 수 있는 해시 테이블이 있고 해시를 계산하는 함수가 x mod 18이라고 하자. 우리가 25를 저장하려고 하면 25 mod 18 = 7임으로 hash[7]에 값이 저장되는 것이다. 

해시 테이블에 원소가 차 있는 비율을 적재율이라고 한다. 이 적재율은 저장된 원소의 총수/해시테이블의 크기로 나타내고 보통 α로 표시한다.

또한 만일 해시 값을 계산해서 테이블에 넣으려고 하는데 이미 그곳에 값이 존재하면 이를 충돌이라고 한다. 

 

2. 해시 함수

해시함수는 아래의 두가지 성질을 만족해야 한다. 

 

1) 입력 원소가 해시 테이블 전체에 고루 저장

2) 계산이 간단해야한다.

 

이를 만족시키는 것중 대표적인것이 두개가 있다.

 

1) 나누기 방법

나누기 방법은 h(x) = x mod m 으로 나타낸다. 

 

2) 곱하기 방법

이 방법은 h(x) = |m(xA mod 1)|로 나타낸다. 우선 xA mod 1을 계산해서 소수 부분을 구한다. 그다음 m을 곱해서 (이때 해시 테이블의 크기를 m이라고 한다.) 정수부분을 해시값으로 사용한다. 이때 A의 값이 해시 값 분포에 영향을 많이 미치는데 0.6180339887을 많이 사용한다. 

 

3. 충돌 해결

1) 체이닝

체이닝은 충돌이 일어나면 그 자리를 링크드 리스트로 연결을 시켜버린다.

링크드 리스트로 연결을 할때 새로운 원소를 맨뒤에 두는 것이 아닌 맨 앞에 두는데 맨뒤에 두면 그 자리에 원소 n개가 연결되있다고 하면 맨 끝 자리를 찾는데 O(n)의 시간이 더 소요되기 때문이다. 아래는 체이닝 해시 테이블의 삽입, 삭제, 검색을 직접 구현한 코드이다. 

class node():
    def __init__(self, value):
        self.hash = None
        self.value = value
        self.next = None

class hashtable():
    def __init__(self, m):
        self.capacity = m
        self.table = [None]*m
        
    def find_hash(self, x):
        hash_ = x % self.capacity
        return hash_
        
    def insert(self, x):
        hash_ = self.find_hash(x)
        a = node(x)
        a.hash = hash_
        if self.table[hash_] is None:
            self.table[hash_] = a
        else:
            a.next = self.table[hash_]
            self.table[hash_] = a
    
    def search(self, x):
        hash_ = self.find_hash(x)
        
        if self.table[hash_] is None:
            return False, False
        else:
            p = None
            a = self.table[hash_]
            while a.next is not None and a.value != x:
                p = a
                a = a.next
            
            return a, p
        
    def delete(self, x):
        a, p = self.search(x)
        if a == False:
            return False
        else:
            #if a is last
            if a.next is None:
                p.next = None
            #if a is first
            if p is None:
                self.table[self.find_hash(x)] = a.next
            else:
                p.next = a.next
        
        return True           
    
    def dump(self):
        for i in range(self.capacity):
            print('{} :'.format(i), end = ' ')
            a = self.table[i]            
            while a is not None:
                print('{} ->'.format(a.value), end = ' ')
                a = a.next
            print('\n')

아래 처럼 잘 구현된 것을 확인할 수 있다.

 

2) 개방 주소 방법 

개방 주소 방법(open addressing)은 추가 공간을 허용하지 않고 테이블 안에서 해결한다. 예를들어 3번째 자리에 이미 차있다면 체이닝은 링크드 리스트로 공간을 만들어 3번째 자리에 어떻게든 넣는데 개방 주소는 그와 관련된 다른 자리에 넣는다.

 

(1) 선형조사

충돌이 일어난다면 바로 뒷자리에 값을 넣는다. 만약 그 뒷자리도 차있다면 그 뒷자리에 넣는 식이다.

예를들어 마지막에 55를 넣을때 6번째에 넣어야 하지만 6번째가 차서 0번째로 돌아와 확인하니 그곳도 차있고 그래서 1번째 자리에 넣는다. 이를 수식으로 나타내면 h_j(x) = (h(x)+i) mod m으로 나타낼 수 있다. i는 충돌이 일어난 횟수이다. 

하지만 선형 조사의 경우 특정 영역에 원소가 몰린다면 성능이 치명적으로 떨어진다. 이를 1차 군집(Primary Clustering)이라고 한다. 

아래는 직접 구현한 선형조사 해시 테이블 코드이다. 

class hashtable():
    def __init__(self, m):
        self.capacity = m
        self.table = [None]*m
        
    def find_hash(self, x):
        hash_ = x % self.capacity
        i = 0
        while self.table[hash_] is not None:
            i += 1
            hash_ = (x+i) % self.capacity
            
        return hash_
        
    def insert(self, x):
        hash_ = x % self.capacity
        i = 0
        while self.table[hash_] is not None and self.table[hash_] != 'DELETED':
            i += 1
            hash_ = (x+i) % self.capacity
        self.table[hash_] = x
        
        return
    
    def search_loc(self, x):
        hash_ = x % self.capacity
        i = 0
        if self.table[hash_] == x:
            return hash_
        
        while self.table[hash_] is not None:
            i += 1
            hash_ = (x+i) % self.capacity
            if self.table[hash_] == x:
                return hash_
            
        return False
        
        
    def delete(self, x):
        hash_ = self.search_loc(x)
        if hash_ != False:
            self.table[hash_] = 'DELETED'
        else:
            
            return False
    
    def dump(self):
        for i in range(self.capacity):
            print('{} :'.format(i), end = ' ')
            print('{}'.format(self.table[i]))
            print('\n')

또한 아래는 위의 코드를 실험해본 결과이다.

 

(2) 이차원 조사

선형조사처럼 바로 뒷자리를 보는 것이 아닌 이차함수로 보폭을 늘린다. 따라서 i번째 해시 함수는 다음과 같게 된다. 이런식으로 하면 선형함수보다 더 빨리 군집 지역에서 탈출할 수 있다. 그만큼 보폭이 커지기 때문이다. 아래는 이에 관한 코드이다. find_hash만 바꾸었다.

def find_hash(self, x):
        hash_ = x % self.capacity
        i = 0
        while self.table[hash_] is not None:
            i += 1
            hash_ = (x+i**2) % self.capacity
            
        return hash_

위의 선형 조사의 예시를 그대로 사용하면 아래의 결과가 나온다.

위는 c1을 1, c2는 0으로 잡았지만 이를 키우면 더 빨리 군집에서 벗어날 수 있다. 하지만 이것은 군집에서는 빨리 벗어날지언정 같은 초기 해시값을 가지는 경우에는 이득이 없다. 예를들어 3개의 수의 초기 해시값이 2라면 3개 모두 0, 1, 4칸을 확인해봐야하기 때문이다. 이같이 같은 순서로 조사를 하는 것일 2차 군집이라고 한다. 

 

(3) 더블 해싱

더블해싱은 위의 선형, 이차원 조사와 비슷한 방식이지만 그 자리에 또다른 함수를 넣는다. i번째 해시 함수는 다음과 같다.

또한 또다른 함수인 f(x)는 보통 위처럼 잡는다. 더블 해싱에서 조심해야 할 것이 f(x)의 값과 테이블 크기 값이 서로소여야 한다는 것이다. 만일 둘의 최소 공약수가 1보다 크다면 m크기의 테이블의 일부분 밖에 못쓰게 된다. 예를들어 f(x)의 값이 24이고 m의 값이 16이면 24 mod 16 = 8이 되어서 전체 16칸의 테이블중 일부분 밖에 사용하지 못하게 된다. 그래서 서로소로 맞추기 위하여 m을 소수로 잡고 f(x)의 값이 항상 m보다 작게 하기 위하여 m'를 m보다 작은수로 둔다. 아래는 직접 구현한 코드이다. 

   def insert(self, x):
        hash_orgin = x % self.capacity
        hash_ = hash_orgin
        i = 0
        while self.table[hash_] is not None and self.table[hash_] != 'DELETED':
            i += 1
            hash_ = hash_orgin + (i * (1 + (x % 11)) % self.capacity)
            if hash_ > self.capacity-1:
                return False
        self.table[hash_] = x
        
        return
 

아래는 15, 28, 41, 67을 차례로 넣었을때 각각 선형, 이차원, 더블 해싱의 결과이다.

군집이 더블 해싱에서는 사라진 것을 볼 수 있다. 

 

위에서의 개방 주소 방법은 주어진 테이블의 공간만 사용 가능하여 적재율이 1을 넘을 수 없다. 하지만 적재율이 높아지면 효율이 급격하게 떨어짐으로 적당한 임계점을 설정하여 그것을 넘으면 해시 테이블의 크기를 대략 두 배로 키우고 모든 원소를 다시 해싱하는 것이 일반 적이다. 

 

또한 삭제할 때는 그냥 삭제를 하면 안된다. 그냥 삭제를 하게되면 아래와 같은 문제점이 발생한다.

선형 조사에서 1을 지우고 15를 찾는다면 13, 1, 15.. 모두 같은 초기 해시값을 가지기 때문에 13을 찾고 차있어서 그 다음을 가야하는데 그다음이 비어있기 때문에 이것이 삭제되어서 비어있는지 아니면 원래 비워져있는지 분간이 안가 15로 나아갈 수 없게 된다. 따라서

이렇게 DELETE를 넣음으로서 삭제된 자리라고 알리고 15가있는 곳으로 갈 수 있다. 물론 삽입과정에서 DELETE부분을 채워넣으면 된다.