해시 테이블은 매우 유용한 자료구조입니다. 그러나 충돌(collisions)이 발생할 수 있는 문제가 있습니다. 충돌은 동일한 해시 값으로 인해 서로 다른 키(key)들이 동일한 버킷(bucket)에 저장되는 상황을 말합니다. 충돌이 일어나면 성능이 저하되며 검색 시간이 증가할 수 있습니다.
이번 글에서는 충돌을 해결하기 위한 몇 가지 방법과 성능을 개선하는 방법을 알아보겠습니다. Python 언어를 기반으로 예제 코드를 제시할 것입니다.
1. 충돌 해결 방법
1.1. Separate Chaining (분리 연결법)
분리 연결법은 각 버킷을 연결리스트로 구성하는 방식입니다. 충돌이 발생하면 충돌하는 키들을 해당 버킷의 연결리스트에 순차적으로 추가합니다. 이 방식은 충돌이 자주 발생하는 경우에 효과적입니다. 예제 코드는 아래와 같습니다:
class HashTable:
def __init__(self, size):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
self.buckets[index].append((key, value))
def get(self, key):
index = self._hash(key)
for item in self.buckets[index]:
if item[0] == key:
return item[1]
return None
1.2. Open Addressing (개방 주소법)
개방 주소법은 충돌 발생 시 다른 빈 버킷을 찾아 키를 저장하는 방식입니다. 선형 탐사법, 이차 탐사법, 이중 해싱 등이 개방 주소법의 예시입니다. 예제 코드는 선형 탐사법을 사용한 개방 주소법입니다:
class HashTable:
def __init__(self, size):
self.size = size
self.buckets = [None] * size
def _hash(self, key):
return hash(key) % self.size
def _linear_probe(self, index):
return (index + 1) % self.size
def insert(self, key, value):
index = self._hash(key)
while self.buckets[index] is not None:
index = self._linear_probe(index)
self.buckets[index] = (key, value)
def get(self, key):
index = self._hash(key)
while self.buckets[index] is not None:
if self.buckets[index][0] == key:
return self.buckets[index][1]
index = self._linear_probe(index)
return None
2. 성능 개선 방법
2.1. Load Factor (로드 팩터)
로드 팩터는 해시 테이블이 얼마나 가득 찼는지를 나타내는 비율입니다. 로드 팩터를 크게 설정하면 충돌이 발생할 확률이 커집니다. 충돌을 피하기 위해 로드 팩터가 일정 수준을 넘어가면 해시 테이블의 크기를 조정하는 작업을 수행할 수 있습니다.
2.2. 사용자 정의 해시 함수
Python은 기본적으로 hash() 함수를 제공하며, 대부분의 객체에 사용할 수 있습니다. 그러나 사용자 정의 객체를 키로 사용하는 경우 자체적인 해시 함수를 작성하는 것이 좋습니다. 이렇게 하면 충돌이 더 일어나지 않고 성능이 향상될 수 있습니다.
마무리
해시 테이블의 충돌을 해결하고 성능을 개선하는 여러 방법에 대해 알아보았습니다. 이러한 기법들을 적절하게 활용하여 데이터 구조에 맞게 선택하는 것이 중요합니다. Python에서 제공하는 내장 해시 테이블인 dict 객체도 이러한 기법들을 내부적으로 사용하고 있으므로, 이러한 개념을 이해하면 좀 더 효율적인 코드를 작성할 수 있을 것입니다.