Colin's Blog
[파이썬] 해시 테이블의 성능 개선과 충돌 해결

해시 테이블(Hash Table)은 데이터를 저장하는 데에 효과적인 자료 구조이지만, 충돌(Collision)이 발생할 수 있다는 단점이 있습니다. 충돌은 서로 다른 두 개의 키가 동일한 해시 값으로 매핑되는 경우입니다. 이러한 충돌은 테이블의 성능을 저하시킬 수 있으며, 이를 개선하고 충돌을 해결하기 위해 몇 가지 방법을 살펴보겠습니다.

1. 해시 함수 성능 개선

해시 함수는 주어진 키를 해시 값으로 매핑하는 역할을 합니다. 좋은 해시 함수는 다음과 같은 특징을 가집니다.

Python에서 제공하는 기본 해시 함수인 hash() 메서드는 일반적으로 좋은 성능을 보여줍니다. 하지만 경우에 따라서는 사용자 정의 해시 함수를 구현하여 성능을 개선할 수도 있습니다. 이때는 해시 값을 잘 분산시키는 알고리즘을 사용하는 것이 중요합니다.

def custom_hash(key):
    hashed_value = 0
    for char in key:
         hashed_value += ord(char)
    return hashed_value % table_size

위 예시에서는 입력된 문자열의 각 문자의 아스키 코드를 더한 뒤, 테이블의 크기로 나눠 해시 값을 계산합니다. 이렇게 함으로써 각 문자열에 대해 고르게 분산된 해시 값이 생성될 것입니다.

2. 충돌 해결 방법

2.1. 체이닝 (Chaining)

체이닝은 충돌이 발생할 경우 각 해시 값의 인덱스에 연결 리스트를 사용하여 충돌을 해결하는 방법입니다. 이 방법은 충돌이 발생한 위치에 데이터를 추가하여 저장하는 방식으로, 여러 개의 키가 동일한 해시 값에 저장될 수 있습니다.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
        
    def insert(self, key, value):
        hash_value = self._hash(key)
        bucket = self.table[hash_value]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        
    def get(self, key):
        hash_value = self._hash(key)
        bucket = self.table[hash_value]
        for pair in bucket:
            if pair[0] == key:
                return pair[1]
        return None
        
    def _hash(self, key):
        hashed_value = 0
        for char in key:
            hashed_value += ord(char)
        return hashed_value % self.size

위 예시는 체이닝을 사용하여 해시 테이블을 구현한 코드입니다. 충돌이 발생하면 해당 해시 값의 버킷에 키와 값을 연결 리스트로 저장합니다. insert() 메서드로 데이터를 저장하고, get() 메서드로 데이터를 조회할 수 있습니다.

2.2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌이 발생한 경우 다른 해시 값에 데이터를 저장하는 방법입니다. 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등 다양한 방법이 있습니다.

선형 탐사는 충돌이 발생한 해시 값 다음 위치에 순차적으로 데이터를 저장하는 방식입니다.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        
    def insert(self, key, value):
        hash_value = self._hash(key)
        while self.table[hash_value] is not None:
            if self.table[hash_value][0] == key:
                self.table[hash_value][1] = value
                return
            hash_value = (hash_value + 1) % self.size
        self.table[hash_value] = [key, value]
        
    def get(self, key):
        hash_value = self._hash(key)
        while self.table[hash_value] is not None:
            if self.table[hash_value][0] == key:
                return self.table[hash_value][1]
            hash_value = (hash_value + 1) % self.size
        return None
        
    def _hash(self, key):
        hashed_value = 0
        for char in key:
            hashed_value += ord(char)
        return hashed_value % self.size

위 예시는 선형 탐사를 사용하여 개방 주소법을 구현한 코드입니다. 충돌이 발생하면 다음 위치에 데이터를 저장하고, 조회할 때도 같은 방식으로 해당 키를 찾아갑니다.

결론

해시 테이블의 성능을 개선하고 충돌을 해결하는 방법으로는 해시 함수의 성능 개선과 체이닝 또는 개방 주소법을 사용하는 방법이 있습니다. 이를 이해하고 적절히 선택하여 사용하면 효율적인 해시 테이블을 구현할 수 있습니다. 충돌을 최소화하고 성능을 개선시키기 위해서는 알맞은 해시 함수와 충돌 해결 방법을 선택하는 것이 중요합니다.

© 2018 Colin. All rights reserved.