[자료구조] 해시, 해시법(hashing) / Python 파이썬

해시법

해시법(hashing) '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다.

이 방법은 원소의 검색뿐 아니라 추가 · 삭제도 효율적으로 수행할 수 있다. 배열의 키(원소의 값)를 원소 갯수인 7로 나눈 나머지를 해시값(hash value)라고 한다. 해시값은 데이터에 접근할 때 기준이 된다.

 

 

11을 7로 나눈 나머지는 4이므로 x[4]에 바로 저장한다. 이렇게 키를 해시값으로 변환하는 과정을 해시 함수(hash function)라고 한다. 또한 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다. 해시 테이블에서 만들어진 원소를 버킷(bucket)이라고 한다.

---

 해시 충돌

앞에서 만든 해시 테이블에 18을 추가하면 7로 나눈 나머지는 4이므로 저장할 곳은 버킷 x[4]이지만, 이곳에는 이미 값이 들어있다. 키와 해시값의 대응 관계가 꼭 1 : 1 일 필요는 없다. 키와 해시값은 일반적으로 다 대 1(n:1)이다. 이처럼 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다.

해시 함수는 가능한 한 해시값이 한쪽으로 치우치지 않고 고르게 분산된 값을 출력하도록 만드는 것이 가장 좋다.

 

이렇게 해시법에서 충돌이 발생하는 경우 다음 2가지 방법으로 대처할 수 있다.

1. 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.
2. 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

---

체인법

체인법(chaining)이란 해시값이 같은 데이터를 체인 모양의 연결리스트로 연결하는 방법을 말하며 오픈 해시법(open hashing)이라고도 한다.

 

 

1. Node 클래스 만들기

• key : 키 (임의의 자료형)
• value : 값 (임의의 자료형)
• next : 뒤쪽 노드를 참조 (Node형)

## 체인법으로 해시 함수 구현하기
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   # 뒤쪽 노드를 참조

 

Node 클래스는 키와 값이 짝을 이루는 구조이다. 키에 해시 함수를 적용하여 해시값을 구한다. Node형 인스턴스를 초기화하는 __init__( ) 함수는 3개의 인수 key, value, next를 전달받아 각각 대응하는 필드인 self.key, self.value, self.next에 대입한다.

 

2. ChainedHash 해시 클래스 만들기

• capacity : 해시 테이블의 크기(배열 table의 원소 수)를 나타낸다.
• table : 해시 테이블을 저장하는 list형 배열을 나타낸다.

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)

(1) __init__( ) 함수로 초기화하기

__init__( ) 함수는 빈 해시 테이블을 생성한다. 매개변수 capacity에 전달받는 것은 해시 테이블의 크기이다. 원소 수가 capacity인 list형의 배열 table을 생성하고 모든 원소를 None으로 한다.

 

(2) hash_value( ) 해시 함수 만들기

hash_value( ) 함수는 인수 key에 대응하는 해시값을 구한다.

 

 

3. 키로 원소를 검색하는 search( ) 함수

1. 해시 함수를 사용하여 키를 해시값으로 변환한다.
2. 해시값을 인덱스로 하는 버킷에 주목한다.
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔한다. 키와 같은 값이 발견되면 검색에 성공하고, 원소의 맨 끝까지 스캔해서 발견되지 않으면 검색에 실패한다.

def search(self, key: Any) -> Any:
    """키가 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              # 검색 실패

 

4. 원소를 추가하는 add( ) 함수

add( ) 함수는 키가 key이고 값이 value인 원소를 추가한다.

 

1. 해시 함수를 사용하여 키를 해시값으로 변환한다.
2. 해시값을 인덱스로 하는 버킷에 주목한다.
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 한다. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패한다. 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가한다.

def add(self, key: Any, value: Any) -> bool:
    """키가 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                  # 삽입 성공

 

5. 원소를 삭제하는 remove( ) 함수

키가 key인 원소를 삭제한다.

 

1. 해시 함수를 사용하여 키를 해시값으로 변환한다.
2. 해시값을 인덱스로 하는 버킷에 주목한다.
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 한다. 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제한다. 그렇지 않으면 삭제에 실패한다.

def remove(self, key: Any) -> bool:
    """키가 key인 원소를 삭제"""
    hash = self.hash_value(key)  # 삭제할 키의 해시값
    p = self.table[hash]         # 주목하고 있는 노드
    pp = None                    # 바로 앞 주목 노드

    while p is not None:
        if p.key == key:  # key를 발견하면 아래를 실행
            if pp is None:
                self.table[hash] = p.next
            else:
                pp.next = p.next
            return True  # key 삭제 성공
        pp = p
        p = p.next       # 뒤쪽 노드에 주목
    return False         # 삭제 실패(key가 존재하지 않음)

 

6. 원소를 출력하는 dump( ) 함수

dump( ) 함수는 모든 원소를 덤프하는 것, 즉 해시 테이블의 내용을 한꺼번에 통째로 출력한다. 해시 테이블의 모든 원소인 table[0] ~ table[capacity - 1] 까지 뒤쪽 노드를 찾아가면서 각 노드의 키와 값을 출력하는 작업을 반복한다. 

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

 

7. 체인법을 구현하는 해시 클래서 ChainedHash의 사용

from enum import Enum
from chained_hash 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)     # 크기가 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

위 코드의 출력 값

 

REFERENCE

do it! 자료구조와 함께 배우는 알고리즘 입문-파이썬 편