해시테이블

  • O(logN) 시간보다 빠른 연산을 위해, 키와 1차원 리스트의 인덱스의 관계를 이용하여 키(항목)를 저장한다.
  • 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 해싱(Hashing)이라고 함
  • 해싱에 사용되는 함수를 해시함수(Hash Function)라 하고,
  • 해시함수가 계산한 값을 해시값(Hash value) 또는 해시주소라고 하며,
  • 항목이 해시값에 따라 저장되는 배열을 해시테이블(Hash Table)이라고 함
  • 서로 다른 키들이 동일한 해시값을 가질 때 충돌(Collision) 발생

해시함수

  • 가장 이상적인 해시함수는 키들을 균등하게(Uniformly) 해시테이블의 인덱스로 변환하는 함수
  • 일반적으로 키들은 부여된 의미나 특성을 가지므로 키의 가장 앞 부분 또는 뒤의 몇 자리 등을 취하여 해시값으로 사용하는 방식의 해시함수는 많은 충돌을 야기시킴
  • 균등하게 변환한다는 것은 키들을 해시테이블에 랜덤하게 흩어지도록 저장하는 것을 뜻함
  • 해시함수는 키들을 균등하게 해시테이블의 인덱스로 변환하기 위해 의미가 부여되어 있는 키를 간단한 계산을 통해 ‘뒤죽박죽’ 만든 후 해시테이블의 크기에 맞도록 해시값을 계산
  • 아무리 균등한 결과를 보장하는 해시함수라도 함수 계산 자체에 긴 시간이 소요된다면 해싱의 장점인 연산의 신속성을 상실하므로 그 가치를 잃음

대표적인 해시함수

  • 중간제곱(Mid-square) 함수: 키를 제곱한 후, 적절한 크기의 중간부분을 해시값으로 사용
  • 접기(Folding) 함수: 큰 자릿수를 갖는 십진수를 키로 사용하는 경우, 몇 자리씩 일정하게 끊어서 만든 숫자들의 합을 이용해 해시값을 만든다.
  • 곱셈(Multiplicative) 함수: 1보다 작은 실수를 키에 곱하여 얻은 숫자의 소수 부분을 테이블 크기 M과 곱한다. 이렇게 나온 값의 정수 부분을 해시값으로 사용
  • 이러한 해시함수들의 공통점:
    • 키의 모든 자리의 숫자들이 함수 계산에 참여함으로써 계산 결과에서는 원래의 키에 부여된 의미나 특성을 찾아볼 수 없게 된다는 점
    • 계산 결과에서 해시테이블의 크기에 따라 특정부분만을 해시값으로 활용한다는 점
  • 가장 널리 사용되는 해시함수: 나눗셈(Division) 함수
    • 나눗셈 함수는 키를 소수(Prime) M으로 나눈 뒤, 그 나머지를 해시값으로 사용
    • h(key) = key % M이고, 따라서 해시테이블의 인덱스는 0에서 M-1이 됨
    • 여기서 제수로 소수를 사용하는 이유는 나눗셈 연산을 했을 때, 소수가 키들을 균등하게 인덱스로 변환시키는 성질을 갖기 때문

충돌시 해결방법

  • 개방주소방식(Open Addressing) : 해시테이블 전체를 열린 공간으로 가정하고 충돌된 키를 일정한 방식에 따라서 찾아낸 empty 원소에 저장
    • 대표적인 개방주소방식:
      • 선형조사(Linear Probing)
      • 이차조사(Quadratic Probing)
      • 랜덤조사(Random Probing)
      • 이중해싱(Double Hashing)
  • 폐쇄주소방식(Closed Addressing) : 키에 대한 해시값에 대응되는 곳에만 키를 저장
    • 충돌이 발생한 키들은 한 위치에 모여 저장
    • 이를 구현하는 가장 대표적인 방법: 체이닝(Chaining)

선형조사

In [1]:
# 선형조사

class LinearProbing: 
    def __init__(self, size): # 생성자
        self.M = size
        self.a = [None for x in range(size+1)]  # 해시테이블
        self.d = [None for x in range(size+1)]  # key관련 데이터 저장

    def hash(self, key):
        return key % self.M  # 나눗셈 함수
    
    def put(self, key, data): # 삽입 연산
        initial_position = self.hash(key) # 초기 위치 
        i = initial_position
        j = 0
        while True:  
            if self.a[i] == None or self.a[i] == '$': # 삽입 위치 발견
                self.a[i] = key   # key를 해시테이블에 저장
                self.d[i] = data  # key관련 데이터 저장 
                return           
            if self.a[i] == key:  # 이미 key 존재하면
                self.d[i] = data  # 데이터만 갱신
                return  
            j += 1                      
            i = (initial_position + j) % self.M # i의 다음 위치  
            if i == initial_position: # i가 초기위치와 같으면 루프 종료
                break         
           
    def get(self, key): # 탐색 연산
        initial_position = self.hash(key)
        i = initial_position
        j = 1
        while self.a[i] != None: # a[i]가 empty가 아니면
            if self.a[i] == key:
                return self.d[i] # 탐색 성공
            i = (initial_position + j) % self.M  # i의 다음 위치
            j += 1
            if i == initial_position: # i가 초기위치와 같으면 루프 종료
                return None # 탐색 실패                 
        return None # 탐색 실패

    def delete(self, key): # 삭제 연산
        initial_position = self.hash(key)
        i = initial_position
        j = 1
        while self.a[i] != None: # a[i]가 empty가 아니면
            if self.a[i] == key:
                self.a[i] = '$' 
                self.d[i] = None
            i = (initial_position + j) % self.M  # i의 다음 위치
            j += 1   
            if i == initial_position: # i가 초기위치와 같으면 루프 종료
                return None # 삭제 실패             
        return None # 삭제 실패    

    def print_table(self):
        for i in range(self.M):
            print('{:4}'.format(str(i)), ' ', end='')
        print()
        for i in range(self.M):
            print('{:4}'.format(str(self.a[i])), ' ', end='')
        print()
In [2]:
#from linear_prob import LinearProbing
if __name__ == '__main__':
    t = LinearProbing(13)
    t.put(25, 'grape') 
    t.put(37, 'apple')    
    t.put(18, 'banana')
    t.put(55, 'cherry')
    t.put(22, 'mango')    
    t.put(35, 'lime')       
    t.put(50, 'orange')
    t.put(63, 'watermelon')
    print('탐색 결과:')
    print('50의 data = ', t.get(50))
    print('63의 data = ', t.get(63))
    print('해시테이블:')
    t.print_table() 
    t.delete(50)
    t.print_table() 
    print('63의 data = ', t.get(63))
    t.put(9, 'berry')
    t.print_table()

탐색 결과:
50의 data =  orange
63의 data =  watermelon
해시테이블:
0     1     2     3     4     5     6     7     8     9     10    11    12    
50    63    None  55    None  18    None  None  None  22    35    37    25    
0     1     2     3     4     5     6     7     8     9     10    11    12    
$     63    None  55    None  18    None  None  None  22    35    37    25    
63의 data =  watermelon
0     1     2     3     4     5     6     7     8     9     10    11    12    
9     63    None  55    None  18    None  None  None  22    35    37    25

이차조사

In [3]:
class QuadProbing: 
    def __init__(self, size): # 생성자
        self.M = size 
        self.a = [None for x in range(size+1)] # 해시테이블
        self.d = [None for x in range(size+1)] # key관련 데이터 저장
        self.N = 0  # 항목 수

    def hash(self, key): # 나눗셈 함수
        return key % self.M
    
    def put(self, key, data): # 삽입 연산
        initial_position = self.hash(key) # 초기 위치 
        i = initial_position
        j = 0
        while True:  
            if self.a[i] == None: # 삽입 위치 발견
                self.a[i] = key   # key를 해시테이블에 저장
                self.d[i] = data  # key관련 데이터 저장 
                self.N += 1
                return           
            if self.a[i] == key:  # 이미 key 존재하면
                self.d[i] = data  # 데이터만 갱신
                return  
            j += 1                      
            i = (initial_position + j*j) % self.M # i의 다음 위치  
            if self.N > self.M: # 테이블이 full이면  
                break         
           
    def get(self, key): # 탐색 연산
        initial_position = self.hash(key)
        i = initial_position
        j = 1
        while self.a[i] != None: # a[i]가 비어있지 않으면
            if self.a[i] == key:
                return self.d[i] # 탐색 성공
            i = (initial_position + j*j) % self.M  # i의 다음 위치
            j += 1
        return None # 탐색 실패
    
    def print_table(self): # 해시테이블 출력
        for i in range(self.M):
            print('{:4}'.format(str(i)), ' ', end='')
        print()
        for i in range(self.M):
            print('{:4}'.format(str(self.a[i])), ' ', end='')
        print()
In [4]:
#from quad_prob import QuadProbing
if __name__ == '__main__':
    t = QuadProbing(13)
    t.put(25, 'grape') 
    t.put(37, 'apple')    
    t.put(18, 'banana')
    t.put(55, 'cherry')
    t.put(22, 'mango')    
    t.put(35, 'lime')       
    t.put(50, 'orange')
    t.put(63, 'watermelon')
    print('탐색 결과:')
    print('50의 data = ', t.get(50))
    print('63의 data = ', t.get(63))
    print('해시테이블:')
    t.print_table()

탐색 결과:
50의 data =  orange
63의 data =  watermelon
해시테이블:
0     1     2     3     4     5     6     7     8     9     10    11    12    
None  None  50    55    None  18    None  63    None  22    35    37    25

랜덤조사

In [5]:
import random
class RandProbing: 
    def __init__(self, size):
        self.M = size           
        self.a = [None for x in range(size+1)]  # 해시테이블
        self.d = [None for x in range(size+1)]  # key관련 데이터 저장
        self.N = 0  # 항목 수
        
    def hash(self, key): # 나눗셈 함수
        return key % self.M
    
    def put(self, key, data): # 삽입 연산
        initial_position = self.hash(key) # 초기 위치 
        i = initial_position
        random.seed(1000)
        while True:  
            if self.a[i] == None: # 삽입 위치 발견
                self.a[i] = key   # key를 해시테이블에 저장
                self.d[i] = data  # key관련 데이터 저장 
                self.N += 1
                return           
            if self.a[i] == key:  # 이미 key 존재하면
                self.d[i] = data  # 데이터만 갱신
                return  
            j = random.randint(1, 99)                    
            i = (initial_position + j) % self.M  # i의 다음 위치  
            if self.N > self.M: # 테이블이 full이면 
                break         
           
    def get(self, key): # 탐색 연산
        initial_position = self.hash(key)
        i = initial_position
        random.seed(1000)
        while self.a[i] != None: # a[i]가 비어있지 않으면
            if self.a[i] == key:
                return self.d[i] # 탐색 성공
            i = (initial_position + random.randint(1, 99)) % self.M  # i의 다음 위치                
        return None # 탐색 실패
    
    def print_table(self):
        for i in range(self.M):
            print('{:4}'.format(str(i)), ' ', end='')
        print()
        for i in range(self.M):
            print('{:4}'.format(str(self.a[i])), ' ', end='')
        print()

if __name__ == '__main__':
    t = RandProbing(13)
    t.put(25, 'grape') 
    t.put(37, 'apple')    
    t.put(18, 'banana')
    t.put(55, 'cherry')
    t.put(22, 'mango')    
    t.put(35, 'lime')       
    t.put(50, 'orange')
    t.put(63, 'watermelon')
    print('탐색 결과:')
    print('50의 data = ', t.get(50))
    print('63의 data = ', t.get(63))
    print('해시테이블:')
    t.print_table()

탐색 결과:
50의 data =  orange
63의 data =  watermelon
해시테이블:
0     1     2     3     4     5     6     7     8     9     10    11    12    
None  50    None  55    35    18    63    None  None  22    None  37    25

체이닝

In [6]:
class Chaining:
    class Node:    
        def __init__(self, key, data, link): # Node 생성자
            self.key   = key
            self.data  = data
            self.next  = link
            
    def __init__(self, size):
        self.M = size           
        self.a = [None for x in range(size+1)]  # 해시테이블
        
    def hash(self, key): # 나눗셈 함수
        return key % self.M

    def put(self, key, data): # 삽입 연산
        i = self.hash(key)
        p = self.a[i]
        while p != None:
            if key == p.key:   # 이미 key 존재하면
                p.data = data  # 데이터만 갱신
                return
            p = p.next 
        self.a[i] = self.Node(key, data, self.a[i])
    
    def get(self, key): # 탐색 연산
        i = self.hash(key)
        p = self.a[i]
        while p != None:
            if key == p.key:  
                return p.data # 탐색 성공
            p = p.next 
        return None  # 탐색 실패
    
    def print_table(self): # 테이블 출력
        for i in range(self.M):
            print('%2d' % (i), end='')
            p = self.a[i]
            while p != None:
                print('-->[', p.key,',', p.data, ']', end='')
                p = p.next;
            print()

if __name__ == '__main__':
    t = Chaining(13)
    t.put(25, 'grape') 
    t.put(37, 'apple')    
    t.put(18, 'banana')
    t.put(55, 'cherry')
    t.put(22, 'mango')    
    t.put(35, 'lime')       
    t.put(50, 'orange')
    t.put(63, 'watermelon')
    print('탐색 결과:')
    print('50의 data = ', t.get(50))
    print('63의 data = ', t.get(63))
    print('해시테이블:')
    t.print_table()

탐색 결과:
50의 data =  orange
63의 data =  watermelon
해시테이블:
 0
 1
 2
 3-->[ 55 , cherry ]
 4
 5-->[ 18 , banana ]
 6
 7
 8
 9-->[ 35 , lime ]-->[ 22 , mango ]
10
11-->[ 63 , watermelon ]-->[ 50 , orange ]-->[ 37 , apple ]
12-->[ 25 , grape ]

더블해싱

In [7]:
class DoubleHashing:   
    def __init__(self, size):
        self.M = size           
        self.a = [None for x in range(size+1)]  # 해시테이블
        self.d = [None for x in range(size+1)]  # key관련 데이터 저장
        self.N = 0  # 항목 수
        
    def hash(self, key): # 나눗셈 함수
        return key % self.M
    
    def put(self, key, data): # 삽입 연산
        initial_position = self.hash(key) # 초기 위치 
        i = initial_position
        d = 7 - (key % 7) # 2번? 해시 함수
        j = 0
        while True:  
            if self.a[i] == None: # 삽입 위치 발견
                self.a[i] = key   # key를 해시테이블에 저장
                self.d[i] = data  # key관련 데이터를 동일한 인덱스하에 저장 
                self.N += 1
                return           
            if self.a[i] == key:  # 이미 key 존재하면
                self.d[i] = data  # 데이터만 갱신
                return  
            j += 1                      
            i = (initial_position + j*d) % self.M   # i의 다음 위치  
            if self.N > self.M:   # 테이블이 full이면 
                break         
           
    def get(self, key): # 탐색 연산
        initial_position = self.hash(key)
        i = initial_position
        d = 7 - (key % 7) # 2번? 해시 함수
        j = 0
        while self.a[i] != None: # a[i]가 비어있지 않으면
            if self.a[i] == key:
                return self.d[i] # 탐색 성공
            j += 1
            i = (initial_position + j*d) % self.M  # i의 다음 위치                
        return None # 탐색 실패
    
    def print_table(self):
        for i in range(self.M):
            print('{:4}'.format(str(i)), ' ', end='')
        print()
        for i in range(self.M):
            print('{:4}'.format(str(self.a[i])), ' ', end='')
        print()

if __name__ == '__main__':
    t = DoubleHashing(13)
    t.put(25, 'grape') 
    t.put(37, 'apple')    
    t.put(18, 'banana')
    t.put(55, 'cherry')
    t.put(22, 'mango')    
    t.put(35, 'lime')       
    t.put(50, 'orange')
    t.put(63, 'watermelon')
    print('탐색 결과:')
    print('50의 data = ', t.get(50))
    print('63의 data = ', t.get(63))
    print('해시테이블:')
    t.print_table()

탐색 결과:
50의 data =  orange
63의 data =  watermelon
해시테이블:
0     1     2     3     4     5     6     7     8     9     10    11    12    
None  None  None  55    50    18    63    None  None  22    35    37    25