Blog

해시 테이블 자료구조 이해하기 – 빠른 데이터 접근의 핵심

해시 테이블 자료구조 이해하기는 효율적인 프로그래밍을 위해 반드시 알아야 할 필수 개념입니다. 해시 테이블(Hash Table)은 키(Key)와 값(Value)을 쌍으로 저장하는 자료구조로, 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입, 검색, 삭제할 수 있습니다. 이는 배열의 인덱스를 활용한 빠른 접근 속도와 연결 리스트의 유연한 데이터 관리를 결합한 형태입니다. 해시 테이블은 데이터베이스 인덱싱, 캐싱 시스템, 중복 검사 등 실무에서 광범위하게 활용되며, 대부분의 프로그래밍 언어에서 Map, Dictionary, Object 등의 이름으로 기본 제공됩니다.

1. 알고리즘 소개 및 개념

해시 테이블은 해시 함수(Hash Function)를 사용하여 키를 배열의 인덱스로 변환하는 자료구조입니다. 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 매핑하는 함수로, 같은 입력에 대해서는 항상 같은 출력을 반환합니다. 예를 들어, 문자열 “apple”을 해시 함수에 넣으면 항상 동일한 숫자(예: 5)가 나오며, 이 숫자를 배열의 인덱스로 사용하여 데이터를 저장합니다. 이러한 방식으로 키를 통해 직접 데이터의 저장 위치를 계산할 수 있어 빠른 접근이 가능합니다. 해시 테이블의 핵심은 좋은 해시 함수를 설계하고 충돌(Collision)을 효과적으로 처리하는 것입니다.

2. 동작 원리 상세 설명

해시 테이블의 동작은 크게 세 단계로 이루어집니다. 첫째, 해시 함수를 통해 키를 해시 값으로 변환합니다. 예를 들어, 문자열의 각 문자 코드를 더하고 테이블 크기로 나눈 나머지를 인덱스로 사용할 수 있습니다. 둘째, 계산된 인덱스 위치에 데이터를 저장하거나 조회합니다. 셋째, 충돌이 발생했을 때 이를 해결합니다. 충돌은 서로 다른 키가 같은 해시 값을 가질 때 발생하며, 이는 해시 함수의 출력 범위가 입력 범위보다 작기 때문에 불가피합니다. 충돌 해결 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다. 체이닝은 같은 인덱스에 연결 리스트로 여러 값을 저장하고, 개방 주소법은 충돌 시 다른 빈 공간을 찾아 저장합니다. 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등의 기법이 개방 주소법에 속합니다.

3. 시간/공간 복잡도 분석

해시 테이블의 시간 복잡도는 해시 함수의 품질과 충돌 해결 방식에 따라 달라집니다. 이상적인 경우 삽입, 검색, 삭제 모두 O(1)의 시간 복잡도를 가집니다. 이는 해시 함수를 통해 바로 저장 위치를 계산할 수 있기 때문입니다. 하지만 최악의 경우, 모든 키가 같은 인덱스로 해싱되어 하나의 연결 리스트에 저장되면 O(n)의 시간 복잡도를 가집니다. 평균적으로는 O(1)에 가까운 성능을 보이며, 이는 로드 팩터(Load Factor = 저장된 항목 수 / 테이블 크기)를 적절히 관리함으로써 유지됩니다. 일반적으로 로드 팩터가 0.7을 초과하면 테이블 크기를 2배로 늘리는 리해싱(Rehashing)을 수행합니다. 공간 복잡도는 O(n)이며, 체이닝 방식을 사용할 경우 추가적인 포인터 공간이 필요합니다. 개방 주소법은 추가 공간이 적지만 로드 팩터가 높아지면 성능이 급격히 저하될 수 있습니다.

4. 단계별 구현 과정

해시 테이블을 JavaScript로 구현해보겠습니다. 체이닝 방식을 사용한 기본 구현입니다:

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(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.keyMap.length;
    }
    
    return total;
  }

  // 값 삽입
  set(key, value) {
    const index = this._hash(key);
    
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    
    // 이미 존재하는 키인지 확인
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        this.keyMap[index][i][1] = value; // 값 업데이트
        return;
      }
    }
    
    // 새로운 키-값 쌍 추가
    this.keyMap[index].push([key, value]);
  }

  // 값 조회
  get(key) {
    const index = this._hash(key);
    
    if (this.keyMap[index]) {
      for (let i = 0; i < this.keyMap[index].length; i++) {
        if (this.keyMap[index][i][0] === key) {
          return this.keyMap[index][i][1];
        }
      }
    }
    
    return undefined;
  }

  // 값 삭제
  delete(key) {
    const index = this._hash(key);
    
    if (this.keyMap[index]) {
      for (let i = 0; i < this.keyMap[index].length; i++) {
        if (this.keyMap[index][i][0] === key) {
          this.keyMap[index].splice(i, 1);
          return true;
        }
      }
    }
    
    return false;
  }

  // 모든 키 반환
  keys() {
    const keysArr = [];
    
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          keysArr.push(this.keyMap[i][j][0]);
        }
      }
    }
    
    return keysArr;
  }

  // 모든 값 반환
  values() {
    const valuesArr = [];
    
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!valuesArr.includes(this.keyMap[i][j][1])) {
            valuesArr.push(this.keyMap[i][j][1]);
          }
        }
      }
    }
    
    return valuesArr;
  }
}

// 사용 예제
const ht = new HashTable();
ht.set("apple", 100);
ht.set("banana", 200);
ht.set("cherry", 300);

console.log(ht.get("apple")); // 100
console.log(ht.keys()); // ["apple", "banana", "cherry"]
console.log(ht.values()); // [100, 200, 300]

이 구현에서 핵심은 _hash 메서드입니다. 문자열의 각 문자를 숫자로 변환하고, 소수(31)를 곱하여 충돌을 줄입니다. set 메서드는 체이닝 방식으로 충돌을 처리하며, 같은 키가 이미 존재하면 값을 업데이트합니다.

5. 최적화 방법

해시 테이블의 성능을 최적화하는 방법은 여러 가지가 있습니다. 첫째, 테이블 크기를 소수로 설정하면 해시 값의 분포가 더 균등해져 충돌이 감소합니다. 둘째, 좋은 해시 함수를 사용해야 합니다. 해시 함수는 결정적(같은 입력에 같은 출력), 균등 분포, 빠른 계산 속도를 만족해야 합니다. 셋째, 로드 팩터를 모니터링하고 임계값(보통 0.7-0.75)을 초과하면 동적 리사이징을 수행합니다. 리사이징 시에는 테이블 크기를 2배로 늘리고 모든 항목을 새로운 테이블에 재해싱합니다. 넷째, 자주 접근하는 데이터를 체인의 앞쪽에 배치하는 Move-to-Front 전략을 사용할 수 있습니다. 다섯째, 개방 주소법에서는 클러스터링을 방지하기 위해 이중 해싱을 사용하는 것이 효과적입니다. 마지막으로, 현대적인 구현에서는 Robin Hood Hashing이나 Cuckoo Hashing 같은 고급 기법을 사용하여 최악의 경우 성능을 개선할 수 있습니다.

6. 실전 활용 예제

해시 테이블은 실무에서 다양하게 활용됩니다. 중복 문자 검사, 두 배열의 교집합 찾기, 애너그램 그룹화, LRU 캐시 구현 등이 대표적입니다. 예를 들어, 배열에서 첫 번째로 반복되지 않는 문자를 찾는 문제는 해시 테이블로 각 문자의 빈도를 O(n) 시간에 계산한 후, 다시 배열을 순회하며 빈도가 1인 첫 번째 문자를 찾으면 됩니다. Two Sum 문제도 해시 테이블에 각 숫자와 인덱스를 저장하고, 목표값에서 현재 숫자를 뺀 값이 테이블에 있는지 확인하여 O(n)에 해결할 수 있습니다. 이처럼 해시 테이블 자료구조 이해하기를 통해 많은 알고리즘 문제를 효율적으로 해결할 수 있습니다.

// Two Sum 문제 - 해시 테이블 활용
function twoSum(nums, target) {
  const map = new Map();
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }
  
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

해시 테이블 자료구조 이해하기는 단순히 이론을 아는 것을 넘어 실제 문제에 적용할 수 있어야 합니다. 충돌 처리, 동적 리사이징, 적절한 해시 함수 선택 등의 세부 사항을 이해하면 더욱 효율적인 코드를 작성할 수 있습니다. 지속적인 연습을 통해 해시 테이블을 자유자재로 활용할 수 있는 능력을 키우시기 바랍니다.