Blog

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

해시 테이블 자료구조 이해하기는 효율적인 프로그래밍을 위해 반드시 알아야 할 핵심 개념입니다. 해시 테이블(Hash Table)은 키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조로, 평균 O(1)의 시간 복잡도로 데이터를 삽입, 삭제, 검색할 수 있습니다. 이는 배열의 인덱스를 활용하되, 해시 함수를 통해 임의의 키를 배열 인덱스로 변환함으로써 달성됩니다. 실무에서는 데이터베이스 인덱싱, 캐싱 시스템, 중복 검사 등 다양한 분야에서 활용되며, 대부분의 프로그래밍 언어에서 기본 자료구조로 제공됩니다.

해시 테이블의 핵심 동작 원리

해시 테이블의 동작 원리는 해시 함수(Hash Function)를 중심으로 이루어집니다. 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수로, 키를 입력받아 배열의 인덱스로 사용할 수 있는 정수를 반환합니다. 예를 들어, 문자열 키 “apple”을 해시 함수에 넣으면 특정 인덱스 값(예: 5)이 나오고, 이 인덱스에 해당하는 배열 위치에 값을 저장합니다.

하지만 서로 다른 키가 같은 해시 값을 가질 수 있는데, 이를 충돌(Collision)이라고 합니다. 충돌을 해결하는 대표적인 방법으로는 두 가지가 있습니다. 첫 번째는 체이닝(Chaining) 방식으로, 각 배열 요소에 연결 리스트를 만들어 같은 해시 값을 가진 데이터들을 체인처럼 연결합니다. 두 번째는 개방 주소법(Open Addressing)으로, 충돌이 발생하면 다른 빈 공간을 찾아 저장하는 방식입니다. 선형 탐사, 이차 탐사, 이중 해싱 등의 기법이 여기에 속합니다. 좋은 해시 함수는 데이터를 균등하게 분산시켜 충돌을 최소화하며, 계산이 빠르고 결정적이어야 합니다.

시간 복잡도와 공간 복잡도 분석

시간 복잡도:

• 평균 경우: 삽입, 삭제, 검색 모두 O(1) – 해시 함수가 데이터를 균등하게 분산시키고 충돌이 적을 때
• 최악 경우: O(n) – 모든 키가 같은 해시 값으로 매핑되어 하나의 체인에 모든 데이터가 저장될 때

공간 복잡도: O(n) – n개의 키-값 쌍을 저장하기 위해 필요한 공간입니다. 실제로는 로드 팩터(Load Factor = 저장된 항목 수 / 배열 크기)를 일정 수준 이하로 유지하기 위해 배열 크기를 동적으로 조절하므로, 실제 사용 공간은 n보다 클 수 있습니다. 일반적으로 로드 팩터가 0.75를 초과하면 배열 크기를 2배로 늘려 재해싱(Rehashing)을 수행합니다.

해시 테이블의 성능은 해시 함수의 품질과 충돌 해결 전략에 크게 의존합니다. 좋은 해시 함수를 사용하면 실제로 평균 O(1)에 가까운 성능을 얻을 수 있어, 대량의 데이터를 다루는 애플리케이션에서 매우 효율적입니다.

JavaScript로 해시 테이블 구현하기

체이닝 방식을 사용한 해시 테이블을 단계별로 구현해보겠습니다.

1단계: 기본 구조 및 해시 함수 구현

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; // 'a' = 1, 'b' = 2, ...
      total = (total * PRIME + value) % this.keyMap.length;
    }
    
    return total;
  }
}

2단계: 데이터 삽입(set) 메서드

  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]);
  }

3단계: 데이터 검색(get) 메서드

  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;
  }

4단계: 데이터 삭제(remove) 메서드

  remove(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;
  }

5단계: 유틸리티 메서드

  // 모든 키 반환
  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;
  }
}

해시 테이블 최적화 방법

1. 적절한 초기 크기 설정: 해시 테이블의 크기는 소수(Prime Number)로 설정하는 것이 좋습니다. 소수를 사용하면 해시 값이 더 균등하게 분산되어 충돌이 줄어듭니다. 일반적으로 53, 97, 193 같은 값을 사용합니다.

2. 동적 리사이징: 로드 팩터가 특정 임계값(보통 0.75)을 초과하면 배열 크기를 2배로 늘리고 모든 데이터를 재해싱합니다. 이를 통해 평균 성능을 O(1)에 가깝게 유지할 수 있습니다.

  _resize() {
    const oldKeyMap = this.keyMap;
    this.keyMap = new Array(oldKeyMap.length * 2);
    
    for (let bucket of oldKeyMap) {
      if (bucket) {
        for (let [key, value] of bucket) {
          this.set(key, value);
        }
      }
    }
  }

3. 좋은 해시 함수 사용: 해시 함수는 빠르고, 결정적이며, 균등 분산을 제공해야 합니다. 실무에서는 MurmurHash, CityHash 같은 검증된 해시 함수를 사용합니다.

실전 활용 예제

// 해시 테이블로 문자열에서 첫 번째 반복되지 않는 문자 찾기
function firstUniqueChar(s) {
  const hashTable = new HashTable();
  
  // 각 문자의 빈도수 카운트
  for (let char of s) {
    const count = hashTable.get(char) || 0;
    hashTable.set(char, count + 1);
  }
  
  // 첫 번째 빈도수 1인 문자 찾기
  for (let char of s) {
    if (hashTable.get(char) === 1) {
      return char;
    }
  }
  
  return null;
}

console.log(firstUniqueChar("leetcode")); // "l"
console.log(firstUniqueChar("loveleetcode")); // "v"

해시 테이블 자료구조 이해하기를 통해 배운 내용은 코딩 테스트의 투 포인터, 슬라이딩 윈도우, 그룹 애너그램 등 다양한 문제에 활용됩니다. 실무에서도 캐싱, 데이터베이스 인덱싱, 세션 관리 등에 필수적으로 사용되므로, 확실히 익혀두시기 바랍니다.