[5.17] 03-4 해시법 복습 (재도전)

03-4 해시법

정렬된 배열에서 원소 추가하기

해시법

hashing - 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 수행

hash table, hash function, bucket

해시 충돌

-> 체인법 : 해시값이 같은 원소를 연결 리스트로 관리

-> 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복

체인법

chaining = open hashing

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)
    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()

해시와 해시 함수 알아보기

표준 라이브러리

- sha256 알고리즘 : hashlib 모듈이 제공. 바이트 문자열의 해시값을 구하는 해시 알고리즘 생성자

- encode() 함수 : key를 문자열로 변환한 뒤, 함수에 전달하여 바이트 문자열 생성 -> sha에 전달

- hexdigest() 함수 : 해시값을 16진수 문자열로 꺼냄

- int() 함수 : hexdigest가 꺼낸 문자열을 int로 변환

search() : 원소로 키를 검색

add()

remove()

dump()

와 된다 ~

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