해시 테이블(Hash Table) 완벽 가이드

개발자 면접 단골 주제이자, 실무에서 매일 마주치는 해시 테이블. 이 글에서는 동작 원리부터 충돌 해결, 직접 구현, 면접 대비까지 한 번에 정리합니다.

1. 해시 테이블이란?

해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)에 통과시켜 얻은 인덱스에 값(Value)을 저장하는 자료구조입니다.

평균적으로 O(1) 시간 복잡도로 삽입, 삭제, 탐색이 가능하여 가장 널리 사용되는 자료구조 중 하나입니다.

동작 원리

1. 키 입력 → 해시 함수가 키를 정수(해시 값)로 변환
2. 인덱스 계산 → 해시 값 % 배열 크기로 저장 위치 결정
3. 값 저장 → 해당 인덱스의 버킷(bucket)에 값 저장
4. 충돌 처리 → 같은 인덱스에 여러 키가 매핑될 경우 충돌 해결 전략 적용

  Key        Hash Function      Index     Bucket
 ─────       ─────────────      ─────     ──────
 "apple"  →  hash("apple")   →  3    →  ["apple": 5]
 "banana" →  hash("banana")  →  7    →  ["banana": 3]
 "cherry" →  hash("cherry")  →  3    →  ["apple": 5] → ["cherry": 8]  (충돌!)

2. 시간 복잡도

3. 충돌 해결 전략

서로 다른 키가 같은 인덱스에 매핑되는 것을 **충돌(Collision)**이라 합니다. 이를 해결하는 대표적인 전략을 알아봅시다.

3.1 체이닝 (Separate Chaining)

같은 인덱스에 매핑되는 모든 키-값 쌍을 연결 리스트로 연결합니다.

Index   Bucket (Linked List)
┌─────┐
│  0  │ → null
├─────┤
│  1  │ → ["dog": 4] → null
├─────┤
│  2  │ → null
├─────┤
│  3  │ → ["apple": 5] → ["cherry": 8] → null
├─────┤
│  4  │ → null
├─────┤
│  5  │ → ["fox": 2] → null
├─────┤
│  6  │ → null
├─────┤
│  7  │ → ["banana": 3] → null
└─────┘

3.2 개방 주소법 (Open Addressing)

충돌 시 다른 빈 슬롯을 찾아서 저장합니다.

삽입 순서: "apple"→3, "cherry"→3(충돌!→4), "grape"→4(충돌!→5)

Index   Value            상태
┌─────┬──────────────┬──────────┐
│  0  │    null       │  비어있음  │
│  1  │    null       │  비어있음  │
│  2  │    null       │  비어있음  │
│  3  │  "apple": 5   │  원래 위치 │
│  4  │  "cherry": 8  │  3→4 이동 │
│  5  │  "grape": 1   │  4→5 이동 │
│  6  │    null       │  비어있음  │
└─────┴──────────────┴──────────┘

3.3 전략 비교

4. 해시 테이블 vs 다른 자료구조

5. JavaScript 구현

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
    this.size = size;
  }

  // 해시 함수: 문자열 키를 인덱스로 변환
  _hash(key) {
    let total = 0;
    const PRIME = 31; // 소수를 사용하면 충돌 감소
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.size;
    }
    return total;
  }

  // 삽입: 체이닝 방식
  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    // 기존 키가 있으면 값 업데이트
    const existing = this.keyMap[index].find(([k]) => k === key);
    if (existing) {
      existing[1] = value;
    } else {
      this.keyMap[index].push([key, value]);
    }
  }

  // 탐색
  get(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      const found = this.keyMap[index].find(([k]) => k === key);
      return found ? found[1] : undefined;
    }
    return undefined;
  }

  // 삭제
  delete(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      const idx = this.keyMap[index].findIndex(([k]) => k === key);
      if (idx !== -1) {
        this.keyMap[index].splice(idx, 1);
        return true;
      }
    }
    return false;
  }

  // 모든 키 반환
  keys() {
    const keysArr = [];
    for (const bucket of this.keyMap) {
      if (bucket) {
        for (const [key] of bucket) {
          keysArr.push(key);
        }
      }
    }
    return keysArr;
  }
}

// 사용 예시
const ht = new HashTable();
ht.set("apple", 5);
ht.set("banana", 3);
ht.set("cherry", 8);

console.log(ht.get("apple"));   // 5
console.log(ht.get("banana"));  // 3
ht.delete("banana");
console.log(ht.get("banana"));  // undefined
console.log(ht.keys());         // ["apple", "cherry"]

6. Python 구현

class HashTable:
    def __init__(self, size=53):
        self.size = size
        self.table = [[] for _ in range(size)]
        self.count = 0

    def _hash(self, key: str) -> int:
        """해시 함수: djb2 알고리즘"""
        hash_value = 5381
        for char in key:
            hash_value = ((hash_value << 5) + hash_value) + ord(char)
        return hash_value % self.size

    def set(self, key: str, value) -> None:
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])
        self.count += 1

        # 적재율이 0.75를 초과하면 리사이징
        if self.count / self.size > 0.75:
            self._resize()

    def get(self, key: str):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

    def delete(self, key: str) -> bool:
        index = self._hash(key)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                self.table[index].pop(i)
                self.count -= 1
                return True
        return False

    def _resize(self):
        """테이블 크기를 2배로 확장"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        for bucket in old_table:
            for key, value in bucket:
                self.set(key, value)


# 사용 예시
ht = HashTable()
ht.set("apple", 5)
ht.set("banana", 3)
ht.set("cherry", 8)

print(ht.get("apple"))    # 5
print(ht.get("grape"))    # None
ht.delete("banana")
print(ht.get("banana"))   # None

7. 좋은 해시 함수의 조건

좋은 해시 함수는 해시 테이블의 성능을 좌우합니다.

1. 결정적(Deterministic): 같은 입력에 항상 같은 출력
2. 균일 분포(Uniform Distribution): 인덱스가 고르게 분포
3. 빠른 계산: O(1) 또는 키 길이에 비례
4. 눈사태 효과(Avalanche Effect): 입력의 작은 변화가 출력에 큰 변화

적재율 (Load Factor)

적재율(α) = 저장된 항목 수 / 테이블 크기

α < 0.75  →  성능 양호 (보통 리사이징 기준)
α → 1.0   →  충돌 급증, 성능 저하
α > 1.0   →  체이닝에서만 가능

8. 실무 활용 사례

• 캐시(Cache): Redis, Memcached 같은 키-값 저장소
• 데이터베이스 인덱스: 해시 인덱스를 통한 빠른 조회
• 중복 검출: 이미 처리한 데이터인지 O(1)로 확인
• 카운팅: 빈도 분석 (문자 빈도, 단어 빈도)
• 라우팅 테이블: URL → 핸들러 매핑
• 심볼 테이블: 컴파일러의 변수/함수명 관리

9. 면접 단골 Q&A

Q1. 해시 테이블의 시간 복잡도가 최악의 경우 O(n)이 되는 이유는?

모든 키가 동일한 해시 값(인덱스)을 갖게 되면, 하나의 버킷에 모든 요소가 체인으로 연결됩니다. 이 경우 탐색 시 연결 리스트를 순회해야 하므로 O(n)이 됩니다. 이를 방지하기 위해 좋은 해시 함수 선택과 적절한 적재율 관리가 중요합니다.

Q2. 체이닝과 개방 주소법의 차이를 설명해주세요.

체이닝은 충돌 발생 시 연결 리스트로 같은 버킷에 여러 요소를 저장합니다. 개방 주소법은 충돌 시 다른 빈 슬롯을 탐색합니다. 체이닝은 삭제가 간단하고 적재율이 1을 초과해도 동작하지만 추가 메모리가 필요합니다. 개방 주소법은 캐시 효율이 좋지만 클러스터링 문제가 있고 삭제가 복잡합니다. 삭제가 빈번하면 체이닝, 메모리 효율이 중요하면 개방 주소법을 선택합니다.

Q3. JavaScript의 Map과 일반 객체({})의 차이는?

둘 다 해시 테이블 기반이지만, Map은 어떤 타입이든 키로 사용 가능하고 삽입 순서가 보장됩니다. 객체는 키가 문자열/심볼로 제한되고 프로토타입 체인 문제가 있습니다. Map은 size 프로퍼티로 크기를 바로 알 수 있고, 빈번한 추가/삭제에 최적화되어 있습니다.

Q4. 해시 테이블의 리사이징(Resizing)은 왜 필요하고, 어떻게 동작하나요?

적재율이 높아지면 충돌이 급증하여 성능이 저하됩니다. 보통 적재율이 0.75를 초과하면 테이블 크기를 2배로 확장합니다. 리사이징 시 기존 모든 요소를 새 테이블에 재해싱(rehashing)해야 하므로 O(n)의 비용이 발생하지만, 분할 상환 분석(amortized analysis)으로 보면 삽입 연산은 여전히 평균 O(1)입니다.

Q5. 해시 충돌을 최소화하는 방법은?

좋은 해시 함수 사용 (균일 분포, 눈사태 효과), 테이블 크기를 소수로 설정, 적절한 적재율 유지 (0.7~0.75 이하), 필요 시 동적 리사이징 적용. 실무에서는 MurmurHash, FNV, xxHash 같은 검증된 해시 함수를 사용합니다.

10. 핵심 키워드 정리