해시 충돌과 해결 — Chaining vs Open Addressing

# 충돌 예시
def simple_hash(key, size):
    return sum(ord(c) for c in key) % size

# 배열 크기 = 10
print(simple_hash("abc", 10))  # (97+98+99) % 10 = 4
print(simple_hash("bac", 10))  # (98+97+99) % 10 = 4  ← 충돌!

class ChainingHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # 각 슬롯 = 리스트

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

    def put(self, key, value):
        idx = self._hash(key)
        # 이미 같은 키가 있으면 덮어쓰기
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

class LinearProbingHashTable:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size

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

    def put(self, key, value):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:  # 같은 키면 덮어쓰기
                self.values[idx] = value
                return
            idx = (idx + 1) % self.size  # 다음 슬롯으로!
        self.keys[idx] = key
        self.values[idx] = value

    def get(self, key):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.size
        return None