[알고리즘] 해시함수, 뻐꾸기 해싱 Cuckoo Hashing (재해시)

해시 함수 (Hashing Function)?

임의의 길이를 갖는 메세지를 입력받아 일정한 길이의 해시 값을 출력하는 함수이다.

 

특징

• 입력 값의 길이가 달라도 출력 값은 언제나 고정된 길이로 반환
• 눈사태 효과 : 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력
• 출력된 결과 값을 토대로 입력 값을 유추할 수 없음 < 단방향성, 일방향성 One-way >
• 동일한 값이 입력되면 언제나 동일한 출력 값을 보장

 

사용하는 목적

• 메세지의 오류나 변조를 탐지할 수 있는 무결성을 제고하기 위함
• 디지털 서명의 생성
• 메세지 인증코드의 생성 (메세지 내용의 무경성 확인)
• 일회용 패스워드(OTP)의 생성
• 세션 키 도출
• 소프트웨어 배포시 변경 검출

 

Cuckoo Hashing?

뻐꾸기는 다른 새의 둥지에서 알을 낳는다. 이후에 부화된 뻐꾸기 새끼가 다른 새의 알이나 새끼들을 둥지에서 밀어내어 깨버린다. 다른 새의 어미는 그런 줄도 모르고 뻐꾸기 새끼를 품고 자기 새끼처럼 키운다. 이러한 조류의 습성을 탁란이라고 하는데 이를 모방한 해싱 방법이다.

 

뻐꾸기 해싱은 2개의 해시 함수와 해시 테이블이 필요하다. 두 개의 해시 테이블을 htable과 dtable이라고 정의하겠다. 키가 처음 삽입되는 테이블을 htable로 정의한다. 키의 위치가 htable에 중복되었을 경우, 있던 값을 밀어내기 위한 또 다른 테이블을 dtable이라 정의한다. 각각의 테이블에 값이 입력될 때 사용되는 해시 함수는 다른 해시 함수이다. 

 

 

재해시 (Rehash)?

모든 해싱 방식은 해시테이블에 비어있는 원소가 적을수록 삽입에 실패하거나 해시 성능이 급격히 저하되는 현상이 발생한다. 이런 상황에서 재해시를 통해 해시테이블을 확장시키고 새로운 해시함수를 사용하여 모든 키들을 새로운 해시테이블에 다시 저장하여 성능을 향상 시킬 수 있다. 재해시는 오프라인에서 이루어지며 모든 키를 다시 저장해야하므로 O(N) 의 시간이 소요된다. 재해시가 수행되는 조건은 적재율로 따진다. 적재율 a가 0.75를 초과할 경우 해시테이블의 크기를 2배로 늘린다. 만약 a가 0.25보다 작을 경우 해시테이블의 크기를 반으로 줄인다.

 

 

 

장점

최대 2회의 해시함수 계산으로 각각의 테이블 원소를 찾아 각 연산을 처리한다. 탐색과 삭제를 O(1) 시간에 보장할 수 있는 해시함수는 아직 존재하지 않지만 삽입의 경우 뻐꾸기 해싱은 높은 확률로 O(1) 시간에 수행이 가능하다.

 

 

 

알고리즘 설명>

 

1. 처음에는 일반 해시함수들과 똑같이 동작을 한다. 들어온 키를 정해진 해시함수를 거쳐 해시 테이블에 위치시킨다.

   계속해서 hash함수를 통해 H_table을 채워나간다.

2. 키를 채우던 중, 내가 위치해야할 자리에 이미 h_table이 차 있으면, 원래 있던 키인 5는 d hash 함수를 이용해 다시 한 번 위치를 정하여 d_table에 위치시키고, 방금 들어온 3은 h_table에 위치시킨다. 원래 h_table에 있던 키를 d_table로 밀어내는 과정이다. (뻐꾸기 해싱)

3. 내가(8) 위치해야 할 자리에 이미 table이 차 있어 원래 있던 키(1)를 밀어내어 dhash을 통해 d_table로 보냈다. 그러나 d_table의 자리마저 다른 키(6)가 위치해 있는 상황이라면? 그 다른 키(6)마저 밀어내고 원래 있던 키는 d_table을 차지하고, 다른 키(6)는 다시 hash 함수를 통해 h_table에 위치하게 된다. (재해싱)

이와 같은 과정을 모두가 자리에 위치할 때까지 반복해주는 것이다.  

 

 

이를 파이썬을 이용하여 간단하게 2차원 리스트로 구현해보았다.

class CuckooHashing: 
    def __init__(self, size): 
        self.M = size
        self.h = [[None, None] for x in range(size+1)]  # h-table
        self.d = [[None, None] for x in range(size+1)]  # d-table

    def hash(self, key):        # h-hash function, h(key)
        return key % self.M      
    
    def hash2(self, key):       # d-hash function, d(key)
        return (key*key % 17) *11 % self.M  
    
    def put(self, key, data): # item (key,data) 삽입위한 method 
        #### 구현
        while(True):
            hash_list = [key,data]      
            hash_value = self.hash(key)
            
            if self.h[hash_value][0] is None:
                self.h[hash_value] = hash_list
                break
            elif self.h[hash_value][0] == hash_list[0]:
                self.h[hash_vallue][1] = hash_list[1]
                break
                
            else:
                #충돌 case이므로 기존 htable에 있던 키 (old_key)를 쫓아냄
                old_hash_list = [self.h[hash_value][0],self.h[hash_value][1]]
                dhash_v = self.hash2(old_hash_list[0])
                
                self.h[hash_value] = hash_list
            
                
                if self.d[dhash_v][0] is None:
                    self.d[dhash_v] = old_hash_list
                    break
                elif self.d[dhash_v][0] == old_hash_list[0]:
                    self.d[dhash_v][1] = old_hash_list[1]
                    break

                else:
                    #old키가 있던 테이블이 dtable일 경우
                    #hash(old_key) htable에 old key를 저장
                    key = self.d[dhash_v][0]
                    data = self.d[dhash_v][1]
                    
                    self.d[dhash_v] = old_hash_list
                    
                              
            
                                 
    def get(self, key): # key 값에 해당하는 value 값을 return 
        #### 구현
        if self.h[self.hash(key)][0] == key:
            return self.h[self.hash(key)][1]
        elif self.d[self.hash2(key)][0] == key:
            return self.d[self.hash2(key)][1]
            

    def delete(self, key): # key를 가지는 item 삭제 
        #### 구현
        if self.h[self.hash(key)][0] == key:
            self.h[self.hash(key)][0] = None
        elif self.d[self.hash2(key)][0] == key:
            self.d[self.hash2(key)][0] = None

    def print_table(self):
        prt= list(range(self.M))
       
        print('********* Print Tables ************')
        print('h-table:')
        #### h-table 출력 : 구현
        for i in range(len(prt)):
            print(prt[i], end="\t")
        print()
        for i in range(len(self.h)-1):
            print(self.h[i][0],end='\t')

            
        print('\nd-table:')
        #### d-table 출력 : 구현
        for i in range(len(prt)):
            print(prt[i], end="\t")
        print()
        for i in range(len(self.h)-1):
            print(self.d[i][0],end='\t')

if __name__ == '__main__':
    t = CuckooHashing(13)
    t.put(25, 'grape')      # 25:  12,   0
    t.put(43, 'apple')      # 43:   4,   0
    t.put(13, 'banana')     # 13:   0,   7
    t.put(26, 'cherry')     # 26:   0,   0
    t.put(39, 'mango')      # 39:   0,  10
    t.put(71, 'lime')       # 71:   9,   8
    t.put(50, 'orange')     # 50:  11,  11
    t.put(64, 'watermelon') # 64:  12,   7
    
    print()
    print('--- Get data using keys:')
    print('key 50 data = ', t.get(50))
    print('key 64 data = ', t.get(64))
    print()
    t.print_table()
    
    print()
    print('-----  after deleting key 50 : ---------------')
    t.delete(50)
    t.print_table() 
    print()
    print('key 64 data = ', t.get(64))
    print('-----  after adding key 91 with data berry:---------------')
    t.put(91, 'berry')
    t.print_table()
    print()
    print('-----  after changing data with key 91 from berry to kiwi:---------------')
    t.put(91, 'kiwi')       # 91:  0,   9
    print('key 91 data = ', t.get(91))    
    t.print_table()