알고리즘 - 해시법(2)

저번 포스팅에 이어서 체인법입니다.

 

이번에는 노드를 key, value, next 이렇게 세 가지로 구성해서 key 값도 넣겠습니다.

또한 value가 str형일 때 hashlib을 사용해 해시값을 구해보겠습니다.

 

 

chain_hash.py

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 ChainHash:

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity  # 배열의 크기 지정
        self.table = [None] * 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)

 

먼저 위쪽에 import hashlib으로 hashlib을 불러왔습니다.

그리고 Class Node 쪽에 key를 추가했고, Class ChainHash 쪽 hash_value에 조건문을 넣었습니다.

조건은 key값이 int형이면 전처럼 그냥 나머지를 구해주는 것이고,

int형이 아니면 hashlib를 사용하는 것입니다.

 

sha256는 바이트 문자열의 해시값을 구하는 해시 알고리즘의 생성자입니다.

encode()는 바이트 문자열을 만들어줍니다.

hexdigest()는 해시값을 16진수 문자열로 바꿔줍니다.

그리고 int()에서는 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     # 입력 값을 찾지 못했다면 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]
        bp = None   # 바로 앞의 노드
        while p is not None:
            if p.key == key:    # 삭제할 값을 찾았을 때 실행합니다.
                if bp is None:  
                    self.table[hash] = p.next   
                    # 앞 노드가 None이면table[hash]값을 삭제할 노드의 다음 노드 값을 줍니다.
                else:
                    bp.next = p.next    
                    # 앞 노드가 None이 아니면 앞 노드에 삭제할 노드의 다음 노드 값을 줍니다.
                return True
            bp = p
            p = p.next
            # 값을 찾을 때까지 앞 노드와 현재 노드 값을 한 단계씩? 바꿔줍니다.
        return False

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

 

다른 부분은 저번과 달라진 것이 크게 없고 기준 값을 value -> key로 바꾸었습니다.

새로 추가한 것은 remove 함수로 데이터를 삭제하는 함수입니다.

 

---

test.py

from enum import Enum
from class_test import ChainHash

Menu = Enum('Menu', ['add', 'remove','search', 'printed', 'exit'])
# 메뉴를 만들어줍니다.

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 = ChainHash(13)

while True:
    menu = select_menu()

    if menu == Menu.add:
        key = input('추가할 키를 입력하세요.:')
        value = input('추가할 값을 입력하세요.: ')
        if not hash.add(key, value):
            print('추가 실패')
        else:
            print('추가 성공')

    elif menu == Menu.remove:
        key = input('삭제할 키를 입력하세요.:')
        if not hash.remove(key):
            print('삭제를 실패했습니다.')
        else:
            print('삭제 성공')

    elif menu == Menu.search:
        key = input('검색할 키를 입력하세요.:')
        t = hash.search(key)
        if t is not None:
            print(f'검색한 키를 갖는 값은 {t}입니다.')
        else:
            print('검색에 실패 했습니다.')

    elif menu == Menu.printed:
        hash.printed()

    else:
        break

 

Menu에 remove를 추가, 조건문에 삭제 추가, key값을 입력 받음 --> 이 부분들이 달라졌습니다.

---

결과창

먼저 키와 값을 넣어줍니다. 키에는 사람 이름을 값에는 나이를 넣어보겠습니다.

 

add

 

총 5명의 이름과 키를 넣었습니다.

search로 경민을 검색해봅시다.

 

search

 

키와 값이 제대로 매칭 됩니다.

 

이제 printed를 해봅시다.

 

printed

 

다음은 경민을 삭제하고 printed로 제대로 삭제됐는지 확인해보겠습니다.

 

remove, printed

8번에서 경민이 제대로 삭제된 것을 확인할 수 있습니다.