해시 테이블(Hash Table) 메커니즘과 충돌 해결 기법

**해시 테이블(Hash Table)**은 임의의 길이인 키(Key)를 **해시 함수(Hash Function)**를 거쳐 고정 크기의 테이블 인덱스로 변환해 데이터를 저장하는 $O(1)$ 자료구조입니다.

1. 해시 충돌 해결 1: 개방 주소법 (Open Addressing)

충돌이 발생하면 테이블 내의 다른 비어있는 슬롯(Bucket)을 찾아 저장하는 방식입니다.

• 선형 조사법 (Linear Probing): 충돌 시 다음 슬롯(i + 1, i + 2, ...)을 순차적으로 탐사. (1차 군집화 문제 발생)
• 이차 조사법 (Quadratic Probing): $i^2$ ($1, 4, 9, 16...$) 단위로 스킵 탐사하여 1차 군집화 완화.
• 이중 해싱 (Double Hashing / Random Probing): 제2의 해시 함수를 이용해 이동 간격을 결정.

# 선형 조사법 (Linear Probing) 구현 예시
class LinearProbing:
    def __init__(self, size=13):
        self.M = size
        self.a = [None] * self.M
        self.d = [None] * self.M

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

    def put(self, key, data):
        initial_i = self.hash(key)
        i = initial_i
        while True:
            if self.a[i] is None or self.a[i] == key:
                self.a[i] = key
                self.d[i] = data
                return
            i = (i + 1) % self.M
            if i == initial_i:
                raise OverflowError("Hash Table Full")

2. 해시 충돌 해결 2: 체이닝 (Chaining)

동일한 해시 버킷 인덱스를 갖는 데이터를 **연결 리스트(Linked List)**로 매달아 관리하는 방식입니다.

class Chaining:
    class Node:
        def __init__(self, key, data, link):
            self.key = key
            self.data = data
            self.next = link

    def __init__(self, size=13):
        self.M = size
        self.a = [None] * self.M

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

    def put(self, key, data):
        i = self.hash(key)
        p = self.a[i]
        while p is not None:
            if key == p.key:
                p.data = data
                return
            p = p.next
        self.a[i] = self.Node(key, data, self.a[i])

3. 개방 주소법 vs 체이닝 성능 비교표

4. 자주 묻는 질문 (Q&A)

Q. 적재율(Load Factor, $alpha$)이란 무엇이며 왜 관리해야 하나요? A. 적재율 $alpha = N / M$ (저장된 데이터 수 / 테이블 크기) 입니다. 적재율이 높아지면 충돌 빈도가 늘어 연산 시간이 $O(1)$에서 $O(N)$으로 저하되므로, 보통 $alpha ge 0.75$ 일 때 테이블 크기를 2배로 재해싱(Rehashing)합니다.