알고리즘 - 해시법(1)

이진 검색에 이어 해시법입니다.

 

해시법

해시법은 데이터를 저장할 위치를 간단하게 연산으로 구하는 방법입니다.

이 방법은 데이터의 검색뿐만 아니라 추가, 삭제도 효율적으로 할 수 있습니다.

 

 

배열에서 각각의 원소 값을 배열의 크기로 나누어 원소에 접근할 때 기준 값으로 합니다.

원소 값	5	6	20	31	37	53	78
해시값 (7로 나눔)	5	6	6	3	2	4	1

 

 

해시값을 배열의 인덱스로 생각하고 다시 만들어 보면

인덱스	0	1	2	3	4	5	6
원소	None	78	37	31	53	5	6
							20

 

 

만약 숫자 21을 추가한다면 다른 원소들을 이동할 필요 없이

21을 7로 나눈 값인 0에 넣어주면 됩니다.

인덱스	0	1	2	3	4	5	6
원소	21	78	37	31	53	5	6
							20

 

하지만 문제가 있습니다.

6번 인덱스를 보면 원소 값이 6, 20 이렇게 2개가 있습니다.

이렇게 한 인덱스에 저장하는 값이 중복되는 현상을 충돌이라 하고

해결방법으로 체인법과 오픈 주소법이 있습니다.

 

이번 글에서는 체인법과 오픈 주소법 중에서 체인법을 하겠습니다.

 

---

체인법

체인법이란 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며

오픈 해시법이라고도 합니다.

 

체인법 그림

 

위 그림과 같이 해시값이 같은 원소를 연결 리스트를 사용해 체인 모양으로 연결합니다.

 

노드

이 작은 사각형들 하나 하나를 노드라 했을 때

같은 해시값을 갖는 원소는 연결 리스트의 앞쪽 노드를 참조합니다.

 

이번 코드는 2개의 파일로 작성하겠습니다.

하나는 class를 정의하는 파일(chain_hash.py), 하나는 실제 구동 파일(test.py)입니다.

 

 

chain_hash.py

 

from __future__ import annotations
from typing import Any, Type


class Node:
    def __init__(self, value: Any, next: Node) -> None:
        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, value: Any) -> int:
        return value % self.capacity  # 해시 값을 구해줌

 

배열의 크기를 지정하고, 지정한 크기만큼 배열을 만들어줍니다.

hash_value()는 입력한 값의 해시 값을 구해줍니다.

 

    def search(self, value: Any) -> Any:
        hash = self.hash_value(value)   # 입력 값의 해시값 저장
        p = self.table[hash]    # 해당 인덱스의 값을 가지는 노드

        while p is not None:
            # 해당 인덱스가 비어있지 않으면 값이 있기 때문에 계속 찾아줍니다.
            if p.value == value:
                return hash     # 입력 값을 찾으면 해시값을 리턴해줍니다.
            p = p.next  # 다음 노드를 보게합니다.

        return None     # 입력 값을 찾지 못했다면 None 리턴합니다.

    def add(self, value: Any) -> bool:
        hash = self.hash_value(value)   # 입력 값의 해시값 저장
        p = self.table[hash]    # 해당 인덱스의 값을 가지는 노드

        while p is not None:
            if p.value == value:    # 값을 넣어야 하는데 이미 있으면 안되기 때문에 넣어줍니다.
                return False
            p = p.next  # 다음 노드를 보게합니다.

        temp = Node(value, self.table[hash])    # 넣을 값이 배열 안에 없다면 노드로 만들어 주고
        self.table[hash] = temp     # 노드를 추가합니다.
        return True

    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.value}', end='')
                p = p.next
            print()

 

 

---

test.py

from enum import Enum
from class_test import ChainHash

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

while True:
    menu = select_menu()

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

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

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

    else:
        break

 

---

결과창

원소 추가하기

원소가 제대로 추가됐는지 3번을 눌러 확인해봅시다.

 

printed 화면

각 값들을 13으로 나누어 보면 제대로 들어간 것을 알 수 있습니다.

search로 올바른 인덱스 값이 나오는지 확인해봅시다.

 

search 화면

23을 입력했을 때 10을 리턴하는 것을 확인할 수 있습니다.

 

 

---

다음 포스팅도 같은 체인법이지만 hashlib 사용해 int형 말고 str형도 해보겠습니다.