전체 목록
자료구조Medium#27

해시 테이블(Hash Table)의 동작 원리와 충돌 해결 방법을 설명해주세요.

#자료구조#해시테이블#알고리즘
힌트

해시 함수, 버킷, 체이닝과 오픈 어드레싱을 생각해보세요.

정답 및 해설

해시 테이블(Hash Table)의 동작 원리와 충돌 해결 방법을 설명해주세요.

해시 테이블은 키(Key)를 해시 함수(Hash Function)로 변환한 인덱스에 값을 저장하는 자료구조입니다. 평균적으로 삽입, 삭제, 조회 모두 O(1)의 시간 복잡도를 가지며, 빠른 데이터 접근이 필요한 대부분의 실무 시나리오에서 활용됩니다. 단, 해시 충돌(Hash Collision)을 적절히 처리하지 않으면 성능이 크게 저하될 수 있습니다.

기본 동작 원리

해시 함수 (Hash Function)

해시 함수는 임의의 키를 배열의 유효한 인덱스로 변환합니다.

key → hash_function(key) → index → bucket[index] = value

def simple_hash(key, table_size):
    # 각 문자의 ASCII 값 합산 후 나머지 연산
    total = 0
    for char in str(key):
        total += ord(char)
    return total % table_size

# 예시
table_size = 10
print(simple_hash("name", table_size))   # → 특정 인덱스
print(simple_hash("age", table_size))    # → 특정 인덱스

해시 테이블 구조

키(key)   해시값    버킷(bucket)
"name" → hash → [ 3 ] → "Alice"
"age"  → hash → [ 7 ] → 30
"city" → hash → [ 1 ] → "Seoul"

배열:
index:  [0]  [1]       [2]  [3]       [4]  [5]  [6]  [7]
value: [null]["Seoul"][null]["Alice"][null][null][null][30]

좋은 해시 함수의 조건

  1. 결정적 (Deterministic): 같은 키는 항상 같은 해시값 반환
  2. 균등 분포 (Uniform Distribution): 해시값이 고르게 분포
  3. 빠른 계산: 해시 함수 자체의 시간 복잡도가 낮아야 함
  4. 눈사태 효과 (Avalanche Effect): 입력이 조금 달라도 해시값이 크게 달라져야 함
# Python의 내장 hash 함수 활용
class HashTable:
    def __init__(self, size=16):
        self.size = size
        self.buckets = [None] * size

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

    def put(self, key, value):
        index = self._hash(key)
        self.buckets[index] = value

    def get(self, key):
        index = self._hash(key)
        return self.buckets[index]

해시 충돌 (Hash Collision)

해시 충돌은 서로 다른 키가 동일한 해시값(인덱스)을 가질 때 발생합니다.

"abc" → hash → 5
"cba" → hash → 5  ← 충돌 발생!

비둘기집 원리(Pigeonhole Principle)에 의해, 키의 개수가 버킷 수보다 많으면 반드시 충돌이 발생합니다. 따라서 충돌 해결은 해시 테이블 구현의 핵심입니다.

충돌 해결 방법 1: 체이닝 (Chaining)

원리

같은 인덱스를 가지는 항목들을 연결 리스트(또는 다른 자료구조)로 연결합니다.

index 5: → [("abc", "Alice")] → [("cba", "Bob")] → null
index 3: → [("xyz", "Carol")] → null

구현

class HashTableChaining:
    def __init__(self, size=16):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # 각 버킷이 리스트

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

    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]

        # 이미 키가 존재하면 값 업데이트
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # 새로운 키-값 쌍 추가
        bucket.append((key, value))

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]

        for k, v in bucket:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return True
        return False

체이닝의 시간 복잡도

  • 평균: O(1) - 체인 길이가 짧을 때
  • 최악: O(n) - 모든 키가 같은 버킷에 들어갈 때
  • 부하율 α = n/m (n: 저장된 항목 수, m: 버킷 수)
    • α가 낮을수록 성능 향상, 일반적으로 α < 0.75 유지 권장

체이닝의 장단점

장점:

  • 구현이 간단하고 직관적
  • 부하율이 높아도 동작은 함 (다만 성능 저하)
  • 삭제가 용이

단점:

  • 포인터로 인한 추가 메모리 사용
  • 캐시 효율이 낮음 (연결 리스트의 비연속 메모리)

충돌 해결 방법 2: 오픈 어드레싱 (Open Addressing)

원리

충돌 발생 시 테이블 내의 다른 빈 슬롯을 탐색(probing)하여 그곳에 저장합니다. 모든 데이터가 배열 안에 저장됩니다.

선형 탐사 (Linear Probing)

충돌 시 다음 슬롯부터 순서대로 빈 자리를 찾습니다.

hash(key) 충돌 → (hash(key) + 1) % size 시도
              → (hash(key) + 2) % size 시도
              → ...

class HashTableLinearProbing:
    def __init__(self, size=16):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
        self.DELETED = object()  # 삭제 표시용 sentinel

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

    def put(self, key, value):
        index = self._hash(key)

        while self.keys[index] is not None and self.keys[index] is not self.DELETED:
            if self.keys[index] == key:
                self.values[index] = value  # 업데이트
                return
            index = (index + 1) % self.size  # 다음 슬롯

        self.keys[index] = key
        self.values[index] = value

    def get(self, key):
        index = self._hash(key)
        original = index

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
            if index == original:  # 한 바퀴 돌았으면 없는 키
                break
        return None

문제점 - 군집화 (Clustering): 연속된 슬롯이 채워지면 이후 삽입 시 더 많은 탐사가 필요해집니다.

이중 해싱 (Double Hashing)

두 번째 해시 함수를 사용해 탐사 간격을 결정합니다.

index = (hash1(key) + i × hash2(key)) % size

def _hash2(self, key):
    # 두 번째 해시 함수 - 소수를 사용하면 좋음
    prime = 7
    return prime - (hash(key) % prime)

def put(self, key, value):
    h1 = self._hash(key)
    h2 = self._hash2(key)
    i = 0

    while True:
        index = (h1 + i * h2) % self.size
        if self.keys[index] is None:
            self.keys[index] = key
            self.values[index] = value
            return
        if self.keys[index] == key:
            self.values[index] = value
            return
        i += 1

이중 해싱은 선형 탐사보다 군집화 문제를 줄여 성능을 향상시킵니다.

부하율과 리해싱 (Load Factor & Rehashing)

부하율 (Load Factor)

부하율 α = 저장된 항목 수 / 전체 버킷 수

부하율이 높아질수록 충돌 확률이 증가하고 성능이 저하됩니다.

  • Java HashMap: 기본 부하율 0.75 → 초과 시 2배 확장
  • Python dict: 부하율 2/3 초과 시 확장

리해싱 (Rehashing)

def _rehash(self):
    old_buckets = self.buckets
    self.size *= 2  # 테이블 크기 2배 확장
    self.buckets = [[] for _ in range(self.size)]

    # 기존 항목들을 새 테이블에 재삽입
    for bucket in old_buckets:
        for key, value in bucket:
            self.put(key, value)  # 새 해시값으로 다시 배치

def put(self, key, value):
    # 부하율 체크
    if self._load_factor() > 0.75:
        self._rehash()

    index = self._hash(key)
    # ... 삽입 로직

def _load_factor(self):
    total = sum(len(b) for b in self.buckets)
    return total / self.size

리해싱은 O(n)의 비용이 발생하지만, 분할 상환 분석(Amortized Analysis)으로 평균 O(1)을 유지합니다.

실제 언어에서의 해시 테이블

// JavaScript - Map (해시 맵)
const map = new Map();
map.set("name", "Alice");     // O(1) 삽입
map.get("name");               // O(1) 조회 → "Alice"
map.has("age");                // O(1) 존재 확인 → false
map.delete("name");            // O(1) 삭제

// 객체(Object)도 해시 테이블 기반
const obj = {};
obj["key"] = "value";

// Java - HashMap (체이닝 + 트리 변환)
import java.util.HashMap;
HashMap<String, Integer> map = new HashMap<>();

map.put("apple", 1);   // O(1) 평균
map.get("apple");      // O(1) 평균 → 1
map.containsKey("banana");  // O(1) 평균 → false

// Java 8부터: 체인 길이가 8 이상이면 연결 리스트 → 레드-블랙 트리로 전환
// 최악의 경우에도 O(log n) 보장

# Python - dict (해시 테이블)
d = {}
d["name"] = "Alice"    # O(1)
d.get("name")          # O(1) → "Alice"
"age" in d             # O(1) → False
del d["name"]          # O(1)

충돌 해결 방법 비교

특성체이닝선형 탐사이중 해싱
구현 복잡도낮음낮음중간
캐시 효율낮음높음중간
군집화없음발생 가능거의 없음
삭제용이복잡 (sentinel 필요)복잡
부하율 > 1가능불가 (크기 제한)불가
메모리포인터 오버헤드효율적효율적
평균 성능O(1)O(1)O(1)
최악 성능O(n)O(n)O(n)
이전 질문다음 질문