검색 알고리즘 - (해시법)

휴 이번단원은 정말 코드를 이해하는데 며칠이 걸렸다.

 

평소에 짧고 쉬운 코드만 보다가 갑자기 이렇게 길고 어려운 코드를 보니 내가 파이썬을 배운게 맞나 싶을정도로 이해가 되질 않았지만 알고리즘을 이해하고 한줄한줄 천천히 살펴보니 어느정도는 이해가 된 것 같다.

 

앞으로는 이런 코드를 많이 볼텐데 빨리 적응을해서 쉽게 코드를 볼 수 있었으면 좋겠다.

---

해시법

 

해시법이란 파이썬의 리스트처럼 인덱스와 위치를 연결하는 것이다. 따라서 한번의 계산만 하면 되기 때문에 인덱스 값이 1인 값을 구하는 과정과 인덱스값이 100,000인 값의 차이가 없다는게 장점이다. 

 

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


class Node:

    def __init__(self, key, value, next):		# 노드 구현
        self.key = key
        self.value = value
        self.next = next
class chained_Hash:

    def __init__(self, capacity):				# 초기화 (None)상태인 배열 생성
        self.capacity = capacity
        self.table = [None] * self.capacity

    def hash_value(self, key):					# 해시함수 생성 -> retrun값 : 해시값
        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, self.table[hash])
        self.table[hash] = 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):
        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()

위 코드는 추가, 삭제, 찾기, 덤프 이 4가지의 기능이 가능한 해시 클래스이다. 

 

다음은 사용 코드이다.

from enum import Enum
from hash_chain import chained_Hash

Menu = Enum('Menu', ['add','delete','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 = chained_Hash(13)	# 크기가 13인 배열을 만들어줍니다.

while True:
    menu = select_menu()

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

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

    elif menu == Menu.search:
        value = int(input('검색할 값을 입력하세요.: '))
        t = hash.search(key)
        if t is not None:
            print(f'검색한 값을 갖는 인덱스는 {t}입니다.')
        else:
            print('검색한 값이 없습니다.')

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

    else:
        break

 

해시충돌

 

해시법을 이용하면 해시 충돌이 일어날 수 밖에 없다. 물론 충돌을 최소화 하는게 가장 좋은 방법이겠지만 적은 테이블에 많은 양의 데이터가 들어가려면 충돌이 일어난다. 

 

이 때 같은 값의 인덱스를 가지고 있는 데이터를 저장하는 방법은 아래의 2가지가 있다. 

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

오픈주소법

체인법은 위 코드를 통해 설명했다. 오픈 주소법은 이렇게 5번 인덱스에 18이 추가되어 들어가려 하지만 이미 5라는 값이 있다. 

 

이 때 인덱스의 값을 1씩 증가시켜 6번 인덱스를 확인하지만 또 다른 값이 있다. 이렇게 점차 늘려나가서 7번 인덱스의 빈 자리에 18이라는 값이 들어가는 것이다. 

 

하지만 이렇게 되면 삭제할 때 큰 오류가 일어날 수 있다. 위 그림에서 5를 삭제하기위해 인덱스 5를 지워버린다면 18을 검색했을 때 같은 인덱스인 5번을 확인하고 값이 없다고 착각할 수도 있기 때문이다. 

 

그래서 각 인덱스에 값이 없을 때와 삭제되었을 때 다른 속성을 부여한다.

•  숫자 : 값이 있음 (숫자)
•   -  : 값이 없음 
• ★ : 값이 삭제됨

★을 만난다면 값이 삭제되었다는 뜻이니 원하는 값을 찾을 때 까지 재해시를 반복