파이썬으로 해시 테이블 구현하기

개요

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

• 키를 특정한 값으로 나눈 값을 해시값(Hash value)라고 하며, 해시값은 데이터에 접근할 때 기준이 된다.
• 키를 해시값으로 변환하는 과정을 해시 함수(Hash function)이라고 하고, 해시 테이블에서 만들어진 원소를 버킷(bucket)이라 한다.

해시 충돌(Hash collision)은 키와 해시값의 다대일(n:1) 관계에 의해 저장할 버킷이 중복되는 현상이다.

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

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

체인법의 동작 방식

오픈 주소법의 동작 방식

---

코드 구현

코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편에서 확인할 수 있다.

체인법

import hashlib

class Node:
    def __init__(self, key, value, next = None):
        self.key = key
        self.value = value
        self.next = next

class ChainedHash:
    def __init__(self, capacity):
        self.capacity = capacity
        self.table = [None] * self.capacity

    def hash_value(self, key):
        if isinstance(key, int): # type(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

        tmp = Node(key, value, self.table[hash])
        self.table[hash] = tmp
        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[hash]
            print(i, end='')
            while p is not None:
                print(f" -> {p.key} ({p.value})", end="")
                p = p.next
            print()