[파이썬] 해시 테이블 (Hash Tables)의 동작 원리

01 Sep 2023

python

해시 테이블은 매우 효율적인 데이터 구조로서, 데이터를 저장하고 검색하는 데 사용됩니다. 이러한 데이터 구조는 키-값 쌍의 형태로 데이터를 저장하며, 키를 사용하여 값을 검색할 수 있습니다. 해시 테이블은 해시 함수에 의해 값이 저장되는 위치를 계산하고, 해당 위치에 값을 저장합니다. 이러한 동작 원리를 통해 매우 빠른 검색 속도를 제공할 수 있습니다.

해시 함수의 역할

해시 함수는 주어진 입력에 대해 고유한 해시 값을 생성하는 함수입니다. 이 해시 값은 해시 테이블의 인덱스로 사용되며, 값이 저장될 위치를 계산하는 데 사용됩니다. 해시 함수는 안정성과 고유성을 보장해야 하며, 최대한 충돌이 적게 발생하도록 설계되어야 합니다. 이는 다른 입력에 대해 같은 해시 값을 생성하지 않는 것을 의미합니다.

def hash_function(key):
    # 해시 함수의 로직을 구현합니다.
    # 입력된 키를 해시 값으로 변환합니다.
    hash_value = ... 
    return hash_value

충돌 해결 방법

해시 함수를 사용하여 해시 테이블의 인덱스를 계산하고 값을 저장하면 충돌(collision)이 발생할 수 있습니다. 충돌이란, 서로 다른 입력에 대해 같은 해시 값이 나오는 상황을 의미합니다. 이러한 충돌을 해결하기 위한 다양한 방법이 있습니다.

1. 개별 체이닝 (Separate Chaining)

개별 체이닝은 각 해시 테이블 슬롯(bucket)마다 연결 리스트를 사용하여 충돌을 해결하는 방법입니다. 여러 개의 키-값 쌍이 같은 슬롯에 저장될 수 있으며, 각각의 연결 리스트에 순차적으로 연결됩니다. 검색 시에는 해당 슬롯의 연결 리스트를 순회하며 값을 찾아야 합니다.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
        
    def insert(self, key, value):
        index = self._hash_function(key)
        self.table[index].append((key, value))
        
    def search(self, key):
        index = self._hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        return None
        
    def _hash_function(self, key):
        # 해시 함수의 로직을 구현합니다.
        hash_value = ...
        return hash_value

2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌 발생 시 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다. 선형 탐사(linear probing), 이차 탐사(quadratic probing), 이중 해시(doubld hashing) 등의 방법이 있습니다. 개방 주소법은 슬롯 내부에 직접 값들을 저장하기 때문에 추가적인 메모리 사용이 없습니다.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        
    def insert(self, key, value):
        index = self._hash_function(key)
        while self.table[index] is not None:
            index = self._next_index(index)
        self.table[index] = (key, value)
        
    def search(self, key):
        index = self._hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = self._next_index(index)
        return None
        
    def _hash_function(self, key):
        # 해시 함수의 로직을 구현합니다.
        hash_value = ...
        return hash_value
    
    def _next_index(self, index):
        # 다음 인덱스를 계산하는 로직을 구현합니다.
        next_index = ...
        return next_index

요약

해시 테이블은 효율적인 데이터 구조로서, 해시 함수와 충돌 해결 방법을 통해 데이터를 저장하고 검색합니다. 개별 체이닝과 개방 주소법은 충돌을 해결하는 두 가지 주요 방법입니다. 개발 시에는 데이터의 크기와 구조에 맞게 적절한 해시 함수와 충돌 해결 방법을 선택하여 사용해야 합니다.