[파이썬] 해시 테이블의 충돌 해결과 최적화

04 Sep 2023

python

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조입니다. 하지만 해시 테이블을 사용할 때 가장 큰 문제 중 하나는 충돌(collision)입니다. 충돌은 서로 다른 키(key)가 동일한 해시 값(hash value)을 가지는 상황을 말합니다. 충돌이 발생하면 해시 테이블의 성능을 저하시키고, 데이터 접근 속도를 늦추는 원인이 됩니다. 이번 글에서는 해시 테이블의 충돌을 해결하고 성능을 최적화하는 방법들을 살펴보겠습니다.

충돌 해결 방법

1. 체이닝 (Chaining)

체이닝은 충돌이 발생했을 때 충돌한 위치에 데이터를 연결 리스트로 연결하는 방법입니다. 즉, 동일한 해시 값에 대한 데이터들을 링크드 리스트로 연결하여 저장하는 방식입니다. 충돌이 발생한 경우에도 데이터를 삽입 및 검색할 수 있기 때문에 충돌이 발생하더라도 성능에 큰 영향을 미치지 않습니다. 하지만 체이닝은 추가적인 메모리를 사용하게 되는 단점이 있습니다.

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

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

    def _hash_function(self, key):
        # 해시 함수 구현

    def insert(self, key, value):
        index = self._hash_function(key)
        if self.table[index] is None:
            self.table[index] = Node(key, value)
        else:
            node = self.table[index]
            while node.next:
                node = node.next
            node.next = Node(key, value)

    def search(self, key):
        index = self._hash_function(key)
        node = self.table[index]
        while node:
            if node.key == key:
                return node.value
            node = node.next
        return None

2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌이 발생했을 때 다른 해시 버킷에 데이터를 저장하는 방법입니다. 충돌이 발생하면 다음 해시 버킷으로 이동하여 데이터를 저장하므로 추가적인 메모리를 사용하지 않습니다.

2-1. 선형 탐사 (Linear Probing)

선형 탐사는 충돌이 발생한 경우 다음 해시 버킷에 데이터를 저장하는 방법입니다. 하지만 충돌이 지속적으로 발생할 경우, 클러스터(cluster)가 형성되어 탐색 속도가 떨어지는 문제가 있습니다.

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

    def _hash_function(self, key):
        # 해시 함수 구현

    def _next_index(self, index):
        return (index + 1) % self.capacity

    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]:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = self._next_index(index)
        return None

2-2. 이차 탐사 (Quadratic Probing)

이차 탐사는 충돌이 발생한 경우 해당 해시 버킷으로부터 정해진 간격만큼 떨어진 다음 해시 버킷에 데이터를 저장하는 방법입니다. 이차 탐사는 선형 탐사의 클러스터 문제를 해결할 수 있으나, 해시 테이블이 작을 경우에는 해시 버킷을 전부 탐색하게 될 수도 있습니다.

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

    def _hash_function(self, key):
        # 해시 함수 구현

    def _next_index(self, index, i):
        return (index + i ** 2) % self.capacity

    def insert(self, key, value):
        index = self._hash_function(key)
        i = 0
        while self.table[index] is not None:
            i += 1
            index = self._next_index(index, i)
        self.table[index] = (key, value)

    def search(self, key):
        index = self._hash_function(key)
        i = 0
        while self.table[index]:
            if self.table[index][0] == key:
                return self.table[index][1]
            i += 1
            index = self._next_index(index, i)
        return None

해시 테이블 최적화

1. 좋은 해시 함수 선택

좋은 해시 함수를 선택하는 것은 해시 테이블의 성능을 향상시키는 핵심 요소입니다. 좋은 해시 함수는 가능한 범위에서 충돌을 최소화해야 합니다. 해시 함수에 대한 충분한 연구와 테스트를 통해 가장 효율적인 해시 함수를 선택하는 것이 좋습니다.

2. 적절한 해시 테이블 크기 선택

해시 테이블의 크기는 충돌을 최소화하는 데 중요합니다. 해시 테이블의 크기를 작게 설정하면 충돌이 더 많이 발생하고 성능이 저하될 수 있으며, 크기를 크게 설정하면 메모리를 낭비하게 됩니다. 작은 크기에서 충돌이 발생할 경우 개방 주소법을 사용하는 것이 좋고, 큰 크기에서 충돌이 발생할 경우 체이닝을 사용하는 것이 효율적입니다.

결론

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조입니다. 충돌은 해시 테이블의 성능을 저하시키는 주요한 문제입니다. 이를 해결하기 위해 체이닝과 개방 주소법을 사용할 수 있으며, 좋은 해시 함수와 적절한 해시 테이블 크기 선택은 해시 테이블의 성능을 최적화하는 데 중요한 역할을 합니다. 충돌을 해결하고 성능을 향상시킬 수 있는 적절한 방법을 선택하여 해시 테이블을 사용하면 좀 더 효율적인 데이터 관리가 가능합니다.