검색 알고리즘 - 해시법

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다.

배열 검색의 종류로는 

 

• 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다.
• 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다.
• 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 
  • 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다.
  • 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다.

---

해시법 hashing

 

검색과 더불어 데이터의 추가와 삭제도 효율적이다. 해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다.  

 

 

배열의 키들은 해시함수를 거쳐서 해시값(Hash Table)을 만들어 낸다. Hash Table은 Index(key)와 value로 이루어져 있으며, 

해시 테이블에서 만들어진 Key값(원소)을 bucket이라고 하고 Value값을 entry라고 한다.

일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 자주 사용한다.

 

만약 유저가 원소 345의 위치를 알고 싶다면 해쉬함수로 나눈 값이 인덱스 넘버이기 때문에 쉽게 위치를 찾을 수 있다.  

 

 

해시 충돌

 

앞에서 만든 해시 테이블에 135를 추가한다면 100으로 나눈 값은 1이다. 그러나 인덱스 1엔 이미 값(123)이 들어 있다. 키와 해시값의 대응 관계가 꼭 1:1일 필요는 없다. 키와 해시값은 일반적으로 n:1이다. 이처럼 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다.  해시법에서 충돌이 발생하는 경우 두 가지 방법으로 대처할 수 있다.

 

• 체인법 : 해시값이 같은 원소를 연결 리스트로 관리
• 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복

만약 충돌이 발생하지 않는다면 해시 함수로 인덱스를 찾는 것만으로 검색-추가-삭제가 가능하기 때문에 시간 복잡도는 O(1)이다. 해시 테이블을 충분히 크게 만들면 충돌을 억제할 수 있지만 메모리를 낭비하게 된다. 즉, 시간과 공간의 trade-off(상충관계)가 발생한다. 충돌을 피하려면 해시 함수가 해시 테이블 크기보다 작거나 같은 정수를 고르게 생성해야 한다. 따라서 해시 테이블의 크기는 소수를 선호한다.

---

 

 

체인법 chaining

 

체인법이란 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며 오픈 해시법이라고도 한다.

배열의 각 버킷(해시 테이블)에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드(head node)를 참조하는 것이다. 

체이닝 예시

위의 그림을 보면 44와 70의 해시값은 둘 다 5이며, 이들을 연결하는 연결 리스트의 앞쪽 노드를  참조하여 table[5]에 저장한다. 참고로 table[2] 처럼 데이터가 하나도 없는 버킷의 값은 None이라고 한다.

 

<open code>

## -- chained_hash.py
from __future__ import annotations
from typing import Any, Type
import hashlib

class Node:
    '''해시를 구성하는 노드
    Node 클래스는 키와 값이 짝을 이루는 구조이다. 키에 해시 함수를 적용하여 해시값을 구한다.'''
    
    def __init__(self, key: Any, value: Any, next: Node):
        '''초기화'''    
        self.key = key  # 키
        self.value = value  # 값
        self.next = next    # 뒤쪽 노드를 참조
        
class ChainedHash:
    '''체인법으로 해시 클래스 구현 
    해시 테이블의 각 버킷은 맨 앞부터 table[0], table[1] 순으로 접근 가능하다
    __init__() 함수가 호출된 직후 배열 table의 모든 원소는 None으로 모두 빈 상태이다.'''    
    
    def __init__(self, capacity: int):
        self.capacity = capacity    # 해시 테이블의 크기 지정
        self.table = [None] * self.capacity     # 해시 테이블(리스트)을 선언
        
    def hash_value(self, key: Any):
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity) # key가 int형이 아닌 경우 형 변환
    
    def search(self, key: Any):
        hash = self.hash_value(key)     # 검색하는 키의 해시값
        p = self.table[hash]            # 노드를 주목
        
        while p is not None:
            if p.key == key:
                return p.value          # 검색 성공
            p = p.next                  # 뒤쪽 노드를 주목
        
        return None                     # 검색 실패
    
    def add(self, key: Any, value: Any):
        hash = self.hash_value(key)     # 추가하는 key의 해시값
        p = self.table[hash]            # 노드를 주목
        
        while p is not None:
            if p.key == key:
                return False            # 추가 실패
            p = p.next                  # 뒤쪽 노드를 주목
            
        temp = Node(key, value, self.table[hash])
        self.table[hash] = temp         # 노드 추가
        return True                     # 추가 성공
    
    def remove(self, key: Any):
        hash = self.hash_value(key)
        p = self.table[hash]
        pp = None
        
        while p is not None:
            if p.key == key:            # 키를 발견하면 아래의 코드 실행
                if pp is None:
                    self.table[hash] = p.next
                else:
                    pp.next = p.next         
                return True             # 키 삭제 성공
            pp = p
            p = p.next                  # 뒤쪽 노드를 주목
        return False                    # 삭제 실패(key가 존재하지 않음)
    
    def dump(self):    # -- 원소를 출력하는 함수
        for i in range(self.capacity):
            p = self.table[i]
            print(i, end='')
            while p in not None:
                print(f'  -> {p.key} ({p.value})', end='')
                p = p.next
            print()

from enum import Enum
from os import sep
from chained_hash import ChainedHash

Menu = Enum('Menu', ['추가', '삭제', '검색', '덤프', '종료']) # 메뉴 선언

def select_menu():
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
hash = ChainedHash(13)

while True:
    menu = select_menu()
    
    if menu == Menu.추가:
        key = int(input('추가할 키를 입력하세요 : '))
        val = input('추가할 값을 입력하세요 : ')
        if not hash.add(key, val):
            print('추가를 실패했스니다.')
            
    elif menu == Menu.삭제:
        key = int(input('삭제할 키를 입력하세요 : '))
        if not hash.remove(key):
            print('삭제를 실패했습니다.')
    
    elif menu == Menu.검색:
        key = int(input('검색할 키를 입력하세요 : '))
        t = hash.search(key)
        if t is not None:
            print(f'검색한 키를 갖는 값은 {t}입니다.')
        else:
            print('검색할 데이터가 없습니다.')
    elif menu == Menu.덤프:
        hash.dump()
        
    else:
        break

 

 

오픈 주소법 open addressing

 

 

오픈 주소법은 충돌이 발생했을 때 재해시를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법이라고도 한다.

오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사법(linear probing)이라고도 한다.

 

 

원소 삭제하기

 

위 그림의 배열에서 5를 삭제하고 싶다면 인덱스가 5인 버킷을 비우기만 하면 될 것 같지만, 해시값이 같은 18을 검색할 때 해시값이 5인 데이터는 존재하지 않는다고 착각하여 검색에 실패한다. 그렇기 때문에 버킷의 상태를 비어 있는 상태(-)와 삭제 완료된 상태(*)로 나타낸다.

 

 

원소 검색하기

 

 

17을 검색한다고 가정하면 해시값이 4인 버킷은 비어 있는 상태 이므로 검색에 실패한다. 18을 검색한다면 해시값인 5인 버킷은 삭제 완료 상태이다. 그래서 재해시를 반복하여 5 -> 6 -> 7 순으로 버킷 값을 옮겨서 검색하는 값을 찾아낼 수 있다.

<open code>

# -- open_hash.py
from  __future__ import annotations
from telnetlib import STATUS
from typing import Any, Type
from enum import Enum
import hashlib

class Status(Enum):
    OCCUPIED = 0   # 데이터를 저장
    EMPTY = 1      # 비어 있음
    DELETE = 2     # 삭제 완료
    
class Bucket:
    '''해시를 구성하는 버킷'''
    def __init__(self, key: Any = None, value: Any = None, stat: Status = Status.EMPTY):
        self.key = key
        self.value = value
        self.stat = stat
        
    def set_satus(self, stat: Status):
        '''속성을 설정'''
        self.stat = stat
        
class OpenHash:
    '''오픈 주소법으로 구현하는 해시 클래스'''
    def __init__(self, capacity: int):
        '''초기화'''
        self.capacity = capacity                  # 해시 테이블의 크기를 지정
        self.table = [Bucket()] * self.capacity   # 해시 테이블
        
    def hash_value(self, key: Any):
        '''해시값을 구함'''
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.md5(str(key).encode()).hexdigest(), 16) % self.capacity)
    
    def rehash_value(self, key: Any):
        '''재해시값을 구함'''
        return(self.hash_value(key) + 1) % self.capacity
    
    def search_node(self, key):
        '''키가 key인 버킷을 검색'''
        hash = self.hash_value(key) # 검색하는 키의 해시값
        p = self.table[hash]        # 버킷을 주목
        
        for i in range(self.capacity):
            if p.stat == Status.EMPTY:
                break
            elif p.stat == Status.OCCUPIED and p.key == key:
                return p
            hash = self.rehash_value(hash)    # 재해시
            p = self.table[hash]
        return None
    
    def search(self, key):
        p = self.search_node(key)
        if p is not None:
            return p.value
        else:
            return None
        
    def add(self, key, value):
        '''키가 key이고 값이 value인 원소를 추가'''
        if self.search(key) is not None:
            return False    # 이미 등록된 키
        
        hash = self.hash_value(key)  # 추가하는 키의 해시값 
        p = self.table[hash]         # 버킷을 주목
        for i in range(self.capacity):
            if p.stat == Status.EMPTY or p.stat == Status.DELETE:
                self.table[hash] = Bucket(key, value, Status.OCCUPIED)
                return True
            hash = self.rehash_value(hash)    # 재해시
            p = self.table[hash]
        return False
    
    def remove(self, key):
        p = self.search_node(key)
        if p is None:
            return False
        p.set_satus(Status.DELETE) # -- ? 다른 클래스 아닌가?
        return True
    
    def dump(self):
        for i in range(self.capacity):
            print(f'{i:2}', end='')
            if self.table[i].stat == Status.OCCUPIED:
                print(f'{self.table[i].key} ({self.table[i].value})')
            elif self.table[i].stat == Status.EMPTY:
                print('-- 미등록 --')
            elif self.table[i].stat == Status.DELETE:
                print('-- 삭제 완료 --')

from enum import Enum
from os import sep
from open_hash import OpenHash

Menu = Enum('Menu', ['추가', '삭제', '검색', '덤프', '종료']) #메뉴를 선언

def select_menu():
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep= ' ', end='')
        n = int(input(": "))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
hash = OpenHash(13)

while True:
    menu = select_menu()
    
    if menu == Menu.추가:
        key = int(input('추가할 키를 입력하세요 : '))
        val = input('추가할 값을 입력하세요 : ')
        if not hash.add(key, val):
            print('추가를 실패했습니다.')
            
    elif menu == Menu.삭제:
        key = int(input('삭제할 키를 입력하세요 : '))
        if not hash.remove(key):
            print('삭제를 실패했습니다.')
    
    elif menu == Menu.검색:
        key = int(input('검색할 키를 입력하세요 : '))
        t = hash.search(key)
        if t is not None:
            print(f'검색한 키를 갖는 값은 {t}입니다.')
        else:
            print('검색할 데이터가 없습니다.')
            
    elif menu == Menu.덤프:
        hash.dump()
        
    else:
        break