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

04 Sep 2023

python

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위해 많이 사용되는 자료구조입니다. 하지만 데이터의 수가 많아지면 해시 충돌이 발생할 수 있습니다. 이러한 충돌을 해결하고 해시 테이블의 성능을 최적화하는 방법에 대해 알아보겠습니다.

1. 충돌 해결 방법

1.1. 개별 체이닝 (Separate Chaining)

개별 체이닝은 해시 테이블의 각 슬롯에 연결 리스트를 사용하여 충돌을 해결하는 방법입니다. 충돌이 발생하면 해당 슬롯에 있는 연결 리스트에 데이터를 추가하는 방식입니다. 이 방법은 간단하고 구현하기 쉽지만, 리스트의 길이가 길어질 경우 검색 시간이 증가할 수 있습니다.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def _hash(self, key):
        return hash(key) % self.size

    def add(self, key, value):
        index = self._hash(key)
        self.table[index].append((key, value))

    def get(self, key):
        index = self._hash(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        raise KeyError('Key not found')

hash_table = HashTable(100)
hash_table.add('apple', 42)
hash_table.add('banana', 24)
print(hash_table.get('apple'))  # Output: 42

1.2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌 발생 시 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다. 이 방법은 선형 탐사, 제곱 탐사, 이중 해싱 등의 방법이 있습니다. 개방 주소법은 추가 메모리를 사용하지 않고 충돌을 해결할 수 있으며, 데이터가 클러스터링되는 경향이 있어 검색 시간이 증가할 수 있습니다.

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

    def _hash(self, key):
        return hash(key) % self.size

    def _linear_probing(self, index, attempt):
        return (index + attempt) % self.size

    def add(self, key, value):
        index = self._hash(key)
        attempt = 0
        while self.table[index] is not None:
            attempt += 1
            index = self._linear_probing(index, attempt)
        self.table[index] = (key, value)

    def get(self, key):
        index = self._hash(key)
        attempt = 0
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            attempt += 1
            index = self._linear_probing(index, attempt)
        raise KeyError('Key not found')

hash_table = HashTable(100)
hash_table.add('apple', 42)
hash_table.add('banana', 24)
print(hash_table.get('apple'))  # Output: 42

2. 해시 테이블 최적화

2.1. 로드 팩터 조정

로드 팩터는 해시 테이블에 저장된 데이터의 개수와 슬롯의 개수의 비율을 의미합니다. 로드 팩터가 너무 높으면 충돌이 자주 발생할 수 있으므로 슬롯의 개수를 늘려야 하고, 로드 팩터가 너무 낮으면 메모리를 낭비하게 됩니다. 적절한 로드 팩터를 조정하여 해시 테이블의 성능을 최적화할 수 있습니다.

2.2. 해시 함수 개선

해시 함수의 품질은 해시 테이블의 성능에 큰 영향을 미칩니다. 충분히 분산되는 값으로 해싱하는 함수를 사용해야 합니다. 해시 테이블의 크기에 맞게 해시 함수를 설계하고, 성능을 향상시킬 수 있는 해싱 알고리즘을 고려해야 합니다.

결론

해시 테이블은 충돌을 해결하고 성능을 최적화하는 다양한 방법이 있습니다. 개별 체이닝과 개방 주소법을 사용하여 충돌을 해결할 수 있으며, 로드 팩터 조정 및 해시 함수 개선을 통해 최적화할 수 있습니다. 따라서 해시 테이블을 사용할 때는 충돌 문제와 최적화에 대한 고려가 필요합니다.