해시 테이블(HASH Table)과 해시 테이블의 시간복잡도는?

해시 테이블(Hash Table)은 매우 빠른 데이터 검색을 가능하게 하는 자료구조입니다.

해시 테이블은 키(Key)와 값(Value)을 연결하여 데이터를 저장합니다.

각 키에는 해시 함수를 적용하여 고유한 인덱스(Index)를 생성하고, 이 인덱스를 사용해 값을 저장하거나 검색합니다.

해시 테이블의 시간 복잡도

• 평균적인 경우 (Average Case): 해시 테이블의 주요 장점은 평균적인 상황에서 삽입, 삭제, 검색 작업이 모두 의 시간 복잡도를 가진다는 것입니다. 이는 해시 함수가 고르게 분포된 인덱스를 생성하고, 충돌이 최소화될 때 성립합니다.

• 최악의 경우 (Worst Case): 해시 테이블에서 충돌(Collision)이 빈번하게 발생한다면, 특정 인덱스에 여러 값이 연결될 수 있습니다. 이 경우, 검색에 필요한 시간 복잡도가 까지 증가할 수 있습니다. 여기서 은 특정 인덱스에 연결된 요소의 수를 의미합니다. 이를 해결하기 위해 연결 리스트, 개방 주소법(Open Addressing), 더블 해싱(Double Hashing) 등 다양한 충돌 해결 방법이 사용됩니다.

해시 테이블 구현 예시 (Python)

Python에서는 내장된 dict 자료형이 실제로 해시 테이블을 사용하여 구현되어 있습니다. 하지만 여기서는 해시 테이블의 기본적인 개념을 보여주는 간단한 예시를 제공하겠습니다. 이 예시에서는 단순화를 위해 충돌 해결을 위한 별도의 메커니즘은 구현하지 않았습니다.

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

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

    def insert(self, key, value):
        index = self._hash_function(key)
        if self.table[index] is None:
            self.table[index] = []
        self.table[index].append((key, value))

    def search(self, key):
        index = self._hash_function(key)
        if self.table[index] is not None:
            for (k, v) in self.table[index]:
                if k == key:
                    return v
        return None

    def delete(self, key):
        index = self._hash_function(key)
        if self.table[index] is not None:
            for i, (k, v) in enumerate(self.table[index]):
                if k == key:
                    del self.table[index][i]

# 해시 테이블 사용 예시
ht = HashTable()
ht.insert("key1", "value1")
ht.insert("key2", "value2")
print(ht.search("key1"))  # "value1" 출력
ht.delete("key1")
print(ht.search("key1"))  # None 출력 (삭제 후)

이 코드는 해시 테이블의 기본적인 작동 원리를 보여줍니다. 실제 사용 시에는 더 정교한 해시 함수와 충돌 해결 메커니즘이 필요합니다.