Hash Table (collision, chaining, rehashing)

해싱(Hashing)은 데이터 관리를 위한 중요한 기법 중 하나이다. 해싱은 어떤 입력값을 고정된 길이의 값으로 변환하는 과정을 말하며, 이 때 사용되는 함수를 해시 함수라 한다. 해시 함수는 다양한 길이의 입력을 받아서 고정된 길이의 해시값을 출력한다. 이 해시값은 데이터의 저장 위치를 결정하는 데 사용된다.

 

해시 테이블(Hash Table)은 해싱 기법을 사용하여 데이터를 저장하는 자료구조이다. 각 데이터는 해시 함수를 통해 계산된 해시값에 따라 해시 테이블 내의 특정 위치에 저장된다. 해시 테이블은 키-값 쌍으로 데이터를 저장하며, 이때 키를 해시 함수에 입력하여 그 결과로 나온 해시값을 사용하여 값을 저장하거나 검색한다.

 

해시 테이블의 주요 장점은 데이터의 추가, 삭제, 검색 작업을 평균적으로 상수 시간(O(1)) 내에 수행할 수 있다는 점이다. 하지만 최악의 경우(모든 키가 동일한 위치에 해시되는 경우)에는 모든 데이터를 검색해야 하므로 성능이 크게 저하될 수 있다.

 

Python의 dict, Java의 HashMap 같은 프로그래밍 언어의 내장 자료구조도 내부적으로 해시 테이블을 사용한다. Python에서는 hash() 함수를 사용하여 객체의 해시값을 얻을 수 있다. 이 함수는 내장 데이터 타입(예: 정수, 문자열)에 대해 해시값을 반환한다. 하지만 사용자 정의 객체의 경우, 객체가 해시 가능하도록 __hash__() 메소드를 구현해야 한다.

 

또한, Python의 dict 타입은 내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장한다. 이를 통해 키에 대한 빠른 접근과 검색, 추가, 삭제 작업을 지원한다.

# 정수의 해시값
hash_value = hash(100)
print(hash_value)

# 문자열의 해시값
hash_value = hash("Hello, World!")
print(hash_value)

class Student:
    def __init__(self, id, name):
        self.id = id
        self.name = name

    # 객체가 해시 가능하도록 __hash__ 메소드 구현
    def __hash__(self):
        return hash((self.id, self.name))

    # __eq__ 메소드도 구현하여 객체의 동등성 비교 가능하게 함
    def __eq__(self, other):
        return self.id == other.id and self.name == other.name

# 사용자 정의 객체 생성
student = Student(1, "John Doe")

# 사용자 정의 객체의 해시값
print(hash(student))

__hash__() 메소드는 객체의 해시값을 계산하여 반환하며, __eq__() 메소드는 두 객체의 동등성을 비교한다. Python에서는 두 객체가 동등하다고 판단되면, 이들의 해시값도 동일해야 한다.

 

해시 충돌(Collision)은 두 개 이상의 키가 해시 함수를 통해 동일한 해시값(즉, 동일한 위치)을 가리키는 경우 발생하는 현상이다. 해시 테이블의 효율성을 저하시키며, 이를 효과적으로 처리하는 것이 해시 테이블 설계의 핵심적인 부분이다. 충돌이 발생했을 때 체이닝과 재해싱은 이를 해결하기 위한 두 가지 주요 방법이다.

 

체이닝(Chaining)은 충돌이 발생했을 때 같은 해시값을 가진 요소들을 연결 리스트와 같은 자료구조를 사용하여 연결하는 방식이다. 이렇게 하면 한 버킷에 여러 요소가 저장될 수 있으며, 충돌로 인한 문제를 효율적으로 해결할 수 있다. 체이닝 방식의 장점은 해시 테이블의 크기와 무관하게 충돌을 관리할 수 있다는 점이며, 구현이 비교적 간단하다는 것도 장점이다. 다만, 체인이 길어지면 검색 성능이 저하될 수 있다.

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash_function(self, key):
        return key % self.size
    
    def insert(self, key, value):
        hash_index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[hash_index]):
            if k == key:
                self.table[hash_index][i] = (key, value)
                return
        self.table[hash_index].append((key, value))
    
    def search(self, key):
        hash_index = self.hash_function(key)
        for k, v in self.table[hash_index]:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        hash_index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[hash_index]):
            if k == key:
                del self.table[hash_index][i]
                return True
        return False

 

 

재해싱(rehashing)은 해시 테이블의 크기를 조정하고, 모든 요소를 새로운 크기에 맞는 해시 함수를 사용하여 재배치하는 방법이다. 주로 해시 테이블의 사용률(로드 팩터)이 높아져 성능 저하가 예상될 때 사용된다. 재해싱은 충돌의 가능성을 줄이고, 해시 테이블의 성능을 유지하는 데 도움이 된다. 재해싱 과정은 모든 요소를 새로운 해시 테이블로 이동시켜야 하므로, 리소스와 시간이 많이 소모되는 작업이다. 그래서, 재해싱은 해시 테이블의 성능을 개선하기 위해 필요할 때만 수행되어야 한다.

class HashTableRehashing:
    def __init__(self, size=10):
        self.size = size
        self.count = 0
        self.table = [None] * size
    
    def hash_function(self, key):
        return key % self.size
    
    def rehash(self, key, step=1):
        return (key + step) % self.size
    
    def resize_and_rehash_all(self):
        old_table = self.table[:]
        self.size *= 2
        self.table = [None] * self.size
        self.count = 0
        for item in old_table:
            if item:
                key, value = item
                self.insert(key, value)
    
    def insert(self, key, value):
        if self.count / self.size >= 0.7:  # Load factor threshold
            self.resize_and_rehash_all()
        
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                self.table[hash_index] = (key, value)
                return
            hash_index = self.rehash(hash_index, step)
            step += 1
        
        self.table[hash_index] = (key, value)
        self.count += 1
    
    def search(self, key):
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                return self.table[hash_index][1]
            hash_index = self.rehash(hash_index, step)
            step += 1
        return None
    
    def delete(self, key):
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                self.table[hash_index] = None
                self.count -= 1
                return True
            hash_index = self.rehash(hash_index, step)
            step += 1
        return False

 

위 코드에선 해시 테이블이 일정 수준으로 채워지면(load factor >= 0.7), 해시 테이블의 크기를 늘리고 모든 요소를 새로운 크기에 맞게 재해싱하여 충돌 가능성을 줄인다.