해시법

Preface

 

이번 장은 공부하는 데 생각보다 오랜 시간이 걸렸다.

 

개인적인 사정이 생겨 시간이 없었던 탓도 있지만, 내용 자체가 어렵고 길어 코드를 한 줄 한 줄 읽어가며 이해하는 것이 어려웠다.

 

무엇보다 이전엔 사용하지 않던 어노테이션을 사용하려 하니 손에 익지 않아서인지 꽤나 불편했다.

 

또, 다양한 클래스와 함수, 변수를 한 프로그램 내에서 모두 사용하자 정신이 없었다.

 

앞으로는 이보다 훨씬 길고 복잡한 코드를 자주 접하게 될텐데, 벌써부터 코드를 이해하는 데 어려움을 겪으니 걱정이 앞선다.

 

이번에 공부한 코드를 자주 읽어보며 구현력과 가독성을 높이자.

---

 

- 해시법 : '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것

 

 

- 해시값 : 원소의 값 % 원소의 개수

 

 

- 해시 테이블 : 해시값을 인덱스로 하여 원소를 새로 저장한 배열

 

 

- 해시 함수 : 키를 해시값으로 변환하는 과정

 

 

- 버킷 : 해시 테이블에서 만들어진 원소

 

 

- 충돌 : 저장할 버킷이 중복되는 현상

→ 해시 테이블을 충분히 크게 만들면 충돌 발생을 억제할 수 있지만, 시간과 공간의 트레이드-오프(상충 관계) 문제가 발생한다.

 

 

- 해시법 구현 방법

---

1. 체인법 : 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법

→ 오픈 해시법

 

 

- 체인법 코드

from __future__ import annotations
from typing import Any, Type
import hashlib


class Node:
    def __init__(self, key: Any, value: Any, next: Node) -> None:
        self.key = key
        self.value = value
        self.next = next


class ChainedHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.table = [None] * self.capacity

    def hash_value(self, key: Any) -> int:
        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) -> 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) -> bool:
        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, self.table[hash])
        self.table[hash] = temp
        return True

    def remove(self, key: Any) -> bool:
        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()

 

 

- 해시법의 key가 int 형이 아닌 경우

1) sha256 알고리즘 : 주어진 바이트 문자열의 해시값을 구하는 해시 알고리즘의 생성자

2) encode( ) 함수 : 바이트 문자열을 생성하는 함수

3) hexdigest( ) 함수 : sha256 알고리즘에서 해시값을 16진수 문자열로 꺼내는 함수

4) int( ) 함수 : hexdigest( ) 함수로 꺼낸 문자열을 16진수 문자열로 하는 int 형으로 변환

 

 

- 체인법 사용 코드

from enum import Enum
from chained 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)

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

 

 

2. 오픈 주소법 : 충돌이 발생했을 때 재해시를 수행하여 빈 버킷을 찾는 방법

→ 닫힌 해시법, 선형 탐사법

 

 

- 오픈 주소법 코드

from __future__ import annotations
from typing import Any, Sequence
from enum import Enum
import hashlib


class Status(Enum):
    OCCUPIED = 0
    EMPTY = 1
    DELETED = 2


class Bucket:
    def __init__(self, key: Any = None, value: Any = None,
                 stat: Status = Status.EMPTY) -> None:
        self.key = key
        self.value = value
        self.stat = stat

    def set(self, key: Any, value: Any, stat: Status) -> None:
        self.key = key
        self.value = value
        self.stat = stat

    def set_status(self, stat: Status) -> None:
        self.stat = stat


class OpenHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.table = [Bucket()] * self.capacity

    def hash_value(self, key: Any) -> int:
        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) -> int:
        return (self.hash_value(key) + 1) % self.capacity

    def search_node(self, key: Any) -> Any:
        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 add(self, key: Any, value: Any) -> bool:
        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.DELETED:
                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: Any) -> int:
        p = self.search_node(key)
        if p is None:
            return False
        p.set_status(Status.DELETED)
        return True

    def dump(self) -> None:
        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.DELETED:
                print('-- 삭제 완료 --')

 

 

- 오픈 주소법 사용 코드

from enum import Enum
from open_hash import OpenHash

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 = 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