해시 테이블(Hash Tables)

해시 테이블(Hash Tables) 개요

해시 테이블은 키(key)-값(value) 쌍을 저장하는 자료구조이다. 키를 해시 함수(hash function)를 통해 특정한 인덱스로 변환하여, 배열과 같은 자료구조에 값을 저장한다. 해시 테이블의 주요 장점은 빠른 데이터 검색, 삽입, 삭제이다. 평균적으로 O(1) 시간 복잡도를 가지기 때문에 효율적이다.

하지만 해시 테이블에서 중요한 문제는 충돌(collision)이다. 충돌은 두 개 이상의 서로 다른 키가 동일한 해시 값을 갖게 되어 동일한 인덱스에 저장하려고 할 때 발생한다. 이 문제를 해결하기 위해 여러 가지 기법이 사용된다.

 

충돌 처리 기법

충돌을 처리하기 위한 대표적인 방법으로 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)이 있다.

1. 체이닝 (Chaining)

체이닝은 동일한 해시 인덱스에 여러 개의 요소가 저장될 수 있도록 하는 방법이다. 기본적으로 해시 테이블의 각 인덱스는 연결 리스트(linked list)나 다른 자료구조를 가리키게 된다. 충돌이 발생하면 해당 인덱스에 새 요소를 추가할 수 있다.

장점:

• 간단하고 구현이 용이하다.
• 테이블이 꽉 차더라도 성능 저하가 상대적으로 적다.

단점:

• 연결 리스트나 다른 자료구조의 오버헤드가 발생한다.
• 최악의 경우 모든 키가 같은 버킷에 저장되어 O(n)의 시간 복잡도를 가질 수 있다.

체이닝 구현 힌트:

• 배열의 각 요소가 연결 리스트(혹은 리스트)를 가리키도록 한다.
• 해시 충돌 시 해당 인덱스의 리스트에 새 값을 추가한다.

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

    def polynomial_hash(self, key, p=31):
        hash_value = 0
        p_pow = 1
        for char in key:
            hash_value = (hash_value + (ord(char) - ord("a") + 1) * p_pow) % self.size
            p_pow = (p_pow * p) % self.size
        return hash_value

    def insert(self, key, value):
        hash_index = self.polynomial_hash(key)
        for pair in self.table[hash_index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[hash_index].append([key, value])

    def search(self, key):
        hash_index = self.polynomial_hash(key)
        for pair in self.table[hash_index]:
            if pair[0] == key:
                return pair[1]

        return None

hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
print(hash_table.search("apple"))  # Output: 1
print(hash_table.search("banana"))  # Output: 2
print(hash_table.search("cherry"))  # Output: None

 

2. 오픈 어드레싱 (Open Addressing)

오픈 어드레싱은 충돌이 발생했을 때 해시 테이블의 다른 빈 자리를 찾아 데이터를 저장하는 방법이다. 이 방식은 추가적인 자료구조 없이 해시 테이블 내부에서 해결하는 것이 특징이다. 오픈 어드레싱에는 몇 가지 대표적인 방법이 있다.

1. 선형 탐사 (Linear Probing):
   • 충돌이 발생하면 다음 빈 자리를 순차적으로 찾는다. (i + 1) % Table_Size 방식으로 이동한다.
   • 단점: 클러스터링(Clustering) 현상이 발생할 수 있다. 즉, 한 곳에 데이터가 몰리는 현상이다.
2. 이차 탐사 (Quadratic Probing):
   • 선형 탐사 대신 제곱 값을 이용해 탐사한다. (i + k^2) % Table_Size 방식으로 이동한다.
   • 클러스터링을 어느 정도 완화할 수 있다.
   • 그러나 이 방법은 테이블의 크기가 소수(prime number)가 아닌 경우, 모든 슬롯을 탐색하지 못할 수도 있다.
3. 이중 해싱 (Double Hashing):
   • 두 번째 해시 함수를 사용하여 충돌 시 탐사할 위치를 결정한다. (i + k * hash2(key)) % Table_Size 방식으로 이동한다.
   • 이 방법은 클러스터링을 효과적으로 방지할 수 있다.

구현 시 유의 사항

1. 해시 함수의 선택: 해시 함수는 충돌을 최소화하는 방향으로 설계되어야 한다.
2. 재해싱(Rehashing): 해시 테이블이 너무 꽉 차게 되면 해시 테이블의 크기를 증가시키고 모든 요소를 다시 해시해야 한다.
3. 성능 최적화: 오픈 어드레싱의 경우 클러스터링 현상을 최소화할 수 있도록 테이블 크기나 해시 함수의 선택에 주의해야 한다.

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

    def polynomial_hash(self, key, p=31):
        hash_value = 0
        p_pow = 1
        for char in key:
            hash_value = (hash_value + (ord(char) - ord("a") + 1) * p_pow) % self.size
            p_pow = (p_pow * p) % self.size
        return hash_value

    def insert(self, key, value):
        index = self.polynomial_hash(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.polynomial_hash(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.polynomial_hash(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

hash_table = HashTableLinearProbing(10)

# 데이터 삽입
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("grape", 3)

# 데이터 검색
print(hash_table.search("apple"))   # Output: 1
print(hash_table.search("banana"))  # Output: 2
print(hash_table.search("grape"))   # Output: 3
print(hash_table.search("cherry"))  # Output: None

# 데이터 삭제
hash_table.delete("banana")

# 삭제 후 데이터 검색
print(hash_table.search("banana"))  # Output: None

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms