[Python 자료구조] 해시 법 + (체인 법)

💡 해시법 

'데이터를 저장할 위치 (인덱스)' 를 간단한 연산으로 구하는 것이다. 

해시법을 사용하게 되면 원소의 검색뿐 아니라 추가 및 삭제도 효율적으로 수행할 수 있다.

 

💡 해시 값 

배열의 키를 원소 개수로 나눈 나머지를 해시 값 ( hash value ) 라고 하며, 데이터에 접근할 때 기준으로 사용된다.

 

💡 설명

8개의 원소가 작성되어 있는 표에서 17을 찾고자한다.

17을 찾는 과정에서 해시 함수 ( hash function ) 을 사용하여 변환한다.

해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용된다.

해시 함수를 사용하게 되면 17을 8로 나눈 나머지는 1 이므로 x[1]에 17을 저장한다.  

이렇게 변환하는 과정을 해시 함수라고 한다.

파란색 글씨로 작성된 것은 키 ( Key ) 이며, 표에 작성되어 있는 원소들은 8로 나누었을 때 나머지 ( 해시 값 ) 이다. 

위 설명처럼 인덱스로하여 원소를 새로 저장한 배열을 해시 테이블 ( Hash Table ) 이라고 한다.

 

 

💡 해시 충돌

위에서 만든 해시 테이블에서 18을 8로 나눈 나머지는 2 이다. 

저장할 곳은 버킷 x[2] 이지만, 이곳에는 이미 값이 들어있는 경우가 발생할 수 있다. 

이처럼 저장할 버킷이 중복되는 현상을 해시 충돌 ( hash collistion ) 이라고 한다.

버킷 ( bucket ) 이란 해시 테이블에서 만들어진 원소이다.

 

이렇게 해시법에서 충돌이 발생하는 경우 체인법 과 오픈 주소법을 이용하여 대처할 수 있다.

체인 법은 체인 모양의 연결 리스트로 관리하는 방법이고, 오픈 주소법은 빈 버킷을 찾을 때 까지 해시를 반복하는 것이다.

 

💡 해시 충돌 - 체인 법 (코드)

 

import hashlib

class Node:
    # 해시 구성 노드
    
    def __init__(self, key, value, next):
        self.key = key # 키
        self.value = value # 값
        self.next = next  # 뒤쪽 노드를 참조

Node Class 는 key 와 value 의 값이 짝을 이루는 구조이며, key 에 해시 함수를 적용하여 해시 값을 구하게 된다.

 

import hashlib

class Node:
    
    def __init__(self, key, value, next):
        self.key = key # 키
        self.value = value # 값
        self.next = next  # 뒤쪽 노드를 참조

class ChainedHash:
    
    def __init__(self, capacity):
        self.capacity = capacity # 해시 테이블의 크기 지정
        self.table = [None] * self.capacity # 해시 테이블(list)를 선언
        
    def hash_value(self, key):
        
        """나머지로 해시 값 구하는 조건문"""
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)

해시 테이블의 각 버킷은 맨 앞부터 table[0], table[1], table[2] ... table[capacity -1] 순으로 접근할 수 있다.

init 함수가 호출된 직후 배열 table 의 모든 원소는 None 이며, 전체 버킷이 빈 상태이다.

 

 

import hashlib

class Node:
    
    def __init__(self, key, value, next):
        self.key = key # 키
        self.value = value # 값
        self.next = next  # 뒤쪽 노드를 참조

class ChainedHash:
    
    def __init__(self, capacity):
        self.capacity = capacity # 해시 테이블의 크기 지정
        self.table = [None] * self.capacity # 해시 테이블(list)를 선언
        
    def hash_value(self, key):
        
        """나머지로 해시 값 구하는 조건문"""
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)
    
    
    def search(self, key):
        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, value):
        hash = self.hash_value(key)
        p = self.table[hash]
        
        while p is not None:
            if p.key == key:
                return False
            p = p.next
            
        temp = Node(key, value, p)
        p = temp
        return True
    
    def remove(self, key):
        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
    
    def dump(self) -> None:
        for i in range(self.capacity):
            p = self.table[i]
            print (i, end = '')
            
            while p is not None:
                print(f'  → {p.key} ({p.value})', end='')  # 해시 테이블에 있는 키와 값을 출력
                p = p.next
            print()

 

main

from enum import Enum
from chained_hash import ChainedHash

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

def select_menu() -> 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)     # 크기가 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