Colin's Blog
[파이썬] 해시 테이블의 성능 최적화와 해싱 기법

해시 테이블은 데이터를 효율적으로 저장하고 검색할 수 있는 데이터 구조입니다. 그러나 많은 데이터를 다룰 때 성능이 저하될 수 있습니다. 이러한 성능 문제를 해결하기 위해 해시 테이블의 성능을 최적화할 수 있는 다양한 방법과 해싱 기법을 살펴보겠습니다.

해싱 기법

해싱은 데이터를 고정된 길이의 값으로 매핑하는 기법입니다. 이러한 해싱 기법을 사용하여 해시 테이블의 키를 해시 값으로 변환하여 데이터를 저장하고 검색합니다. 해싱은 O(1)의 시간 복잡도를 가지기 때문에 매우 효율적입니다.

파이썬에서 해싱을 구현하는 가장 간단한 방법은 hash() 함수를 사용하는 것입니다. 예를 들어, 다음과 같이 문자열에 대한 해시 값을 구할 수 있습니다.

data = "Hello"
hash_value = hash(data)
print(hash_value)

해시 값을 구하기 위해서는 hash() 함수를 사용하면 됩니다.

충돌(Collision) 해결

해시 테이블에서 가장 흔히 발생하는 문제는 충돌(Collision) 입니다. 충돌은 서로 다른 데이터가 같은 해시 값에 위치하는 현상을 말합니다. 충돌이 발생하면 데이터의 검색이 지연되거나 잘못된 데이터가 반환될 수 있습니다.

파이썬에서 기본적으로 제공하는 해시 테이블인 dict 자료형은 충돌을 해결하는 Open addressing 방식과 Separate chaining 방식을 사용합니다. 충돌을 해결하는 두 가지 방식을 간단히 살펴보겠습니다.

Open addressing

Open addressing 방식은 충돌이 발생한 경우 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다. 대표적인 Open addressing 방식은 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다. 이를 사용하기 위해서는 해시 테이블의 크기를 충분히 크게 설정해야 합니다.

선형 탐사는 충돌이 발생한 위치에서 일정 간격으로 다음 슬롯을 확인하는 방법입니다. 이차 탐사는 충돌이 발생한 위치에서 일정한 제곱수 간격으로 다음 슬롯을 확인하는 방법입니다. 이중 해싱은 두 개의 해시 함수를 사용하여 충돌이 발생한 위치에서 다음 슬롯을 확인하는 방법입니다.

# Open addressing 방식의 해시 테이블 생성 예시

class HashTable:
    def __init__(self):
        self.size = 10
        self.keys = [None] * self.size
        self.values = [None] * self.size

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

    def rehash(self, key, i):
        return (self.hash(key) + i) % self.size

    def put(self, key, value):
        index = self.hash(key)
        i = 1
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = value
                return
            index = self.rehash(key, i)
            i += 1
        self.keys[index] = key
        self.values[index] = value

    def get(self, key):
        index = self.hash(key)
        i = 1
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = self.rehash(key, i)
            i += 1
        return None

Separate chaining

Separate chaining 방식은 충돌이 발생한 위치에 연결 리스트를 이용하여 데이터를 저장하는 방법입니다. 충돌이 발생하면 해당 위치의 연결 리스트에 데이터를 추가합니다. 파이썬의 dict 자료형은 기본적으로 Separate chaining 방식을 사용합니다.

# Separate chaining 방식의 해시 테이블 생성 예시

from collections import defaultdict

class HashTable:
    def __init__(self):
        self.table = defaultdict(list)

    def hash(self, key):
        return hash(key)

    def put(self, key, value):
        hash_value = self.hash(key)
        self.table[hash_value].append((key, value))

    def get(self, key):
        hash_value = self.hash(key)
        for k, v in self.table[hash_value]:
            if k == key:
                return v
        return None

해시 테이블의 성능 최적화

해시 테이블의 성능을 최적화하기 위해서는 다음과 같은 방법들을 고려할 수 있습니다.

해시 테이블은 데이터를 효율적으로 저장하고 검색할 수 있는 강력한 자료 구조입니다. 해싱 기법과 충돌 해결 방법을 이해하고 해시 테이블의 성능을 최적화하는 방법을 알고 있다면, 더욱 효율적인 코드를 작성할 수 있습니다.

© 2018 Colin. All rights reserved.