Blog

해시 테이블 자료구조 이해하기: 빠른 검색의 핵심

해시 테이블 자료구조 이해하기는 효율적인 프로그래밍을 위한 필수 과정입니다. 해시 테이블(Hash Table)은 키-값 쌍을 저장하는 자료구조로, 평균 O(1)의 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있습니다. 해시 함수를 사용하여 키를 배열의 인덱스로 변환하고, 해당 위치에 값을 저장하는 방식으로 동작합니다. 이러한 특성 덕분에 대용량 데이터를 다루는 현대 애플리케이션에서 필수적으로 사용되며, 데이터베이스 인덱싱, 캐시 구현, 중복 검사 등 다양한 분야에서 활용됩니다.

1. 알고리즘 소개 및 개념

해시 테이블은 연관 배열(Associative Array) 추상 자료형을 구현하는 가장 효율적인 방법 중 하나입니다. 기본 원리는 해시 함수(Hash Function)를 통해 임의의 키를 고정된 크기의 해시 값으로 변환하고, 이를 배열의 인덱스로 사용하는 것입니다. 예를 들어, “apple”이라는 키를 해시 함수에 입력하면 정수 값(예: 3)이 출력되고, 배열의 3번 인덱스에 해당 값을 저장합니다. 이를 통해 키만 알면 배열을 순회하지 않고 직접 데이터에 접근할 수 있습니다. 해시 테이블의 핵심은 좋은 해시 함수를 설계하여 충돌을 최소화하고, 충돌 발생 시 적절한 해결 방법을 적용하는 것입니다.

2. 동작 원리 상세 설명

해시 테이블의 동작은 크게 세 단계로 이루어집니다. 첫째, 해시 함수 적용: 입력된 키를 해시 함수에 전달하여 해시 값을 계산합니다. 좋은 해시 함수는 입력 값을 균등하게 분산시켜 충돌을 최소화합니다. 둘째, 인덱스 계산: 해시 값을 배열 크기로 나눈 나머지를 계산하여 실제 저장 위치를 결정합니다(index = hashValue % arraySize). 셋째, 충돌 처리: 서로 다른 키가 같은 인덱스를 가리키는 충돌(Collision)이 발생할 수 있습니다. 이를 해결하는 주요 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다. 체이닝은 같은 인덱스에 연결 리스트로 여러 항목을 저장하고, 개방 주소법은 충돌 시 다음 빈 슬롯을 찾아 저장합니다. 데이터 삭제 시에도 같은 과정을 거쳐 해당 위치를 찾고 제거하며, 체이닝의 경우 연결 리스트에서 노드를 제거합니다.

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

시간 복잡도: 해시 테이블의 가장 큰 장점은 빠른 연산 속도입니다. 이상적인 경우(충돌이 없을 때) 검색, 삽입, 삭제 모두 O(1)의 시간 복잡도를 가집니다. 그러나 최악의 경우(모든 키가 같은 인덱스로 해싱될 때) O(n)까지 증가할 수 있습니다. 이는 모든 데이터가 하나의 체인에 연결되어 선형 탐색이 필요하기 때문입니다. 평균적으로는 O(1 + α)의 시간 복잡도를 가지며, 여기서 α는 적재율(Load Factor = n/m, n은 항목 수, m은 테이블 크기)입니다. 공간 복잡도: 기본적으로 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;
  }

  // 삭제 연산
  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;
  }

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

구현 포인트 설명:

• 해시 함수: 소수(31)를 곱셈 인자로 사용하여 충돌을 줄입니다. 문자열의 각 문자를 숫자로 변환하고 누적 계산합니다.
• 체이닝: 각 인덱스에 배열을 저장하여 충돌된 항목들을 관리합니다.
• 키 업데이트: 같은 키로 다시 삽입하면 값을 업데이트합니다.
• 선형 탐색: 체인 내에서는 선형 탐색을 수행하므로, 체인이 길어지지 않도록 적절한 테이블 크기를 유지해야 합니다.

5. 최적화 방법

해시 테이블의 성능을 최적화하는 핵심 방법들은 다음과 같습니다. 1. 적절한 테이블 크기 선택: 소수를 테이블 크기로 사용하면 해시 값의 분산이 더 균등해집니다. 일반적으로 예상 데이터 개수의 1.3~2배 크기를 권장합니다. 2. 동적 리사이징: 적재율이 0.7~0.8을 초과하면 테이블 크기를 두 배로 늘리고 모든 항목을 재해싱(rehashing)합니다. 이를 통해 O(1) 성능을 유지할 수 있습니다. 3. 좋은 해시 함수 설계: 균등 분산, 결정적 결과, 빠른 계산 속도를 고려해야 합니다. 실무에서는 MurmurHash, CityHash 같은 검증된 해시 함수를 사용합니다. 4. 충돌 해결 방법 선택: 메모리가 충분하면 체이닝이, 캐시 지역성이 중요하면 개방 주소법이 유리합니다. 5. 이중 해싱: 개방 주소법 사용 시 두 개의 해시 함수를 사용하여 클러스터링을 방지합니다.

6. 실전 활용 예제

해시 테이블은 다양한 실전 문제에서 활용됩니다. 중복 검사: 배열에서 중복 요소를 찾을 때 O(n) 시간에 해결할 수 있습니다. 빈도 계산: 문자열이나 배열의 요소 빈도를 계산하는 데 사용됩니다. 캐싱: LRU 캐시 구현에서 빠른 조회를 위해 해시 테이블을 사용합니다. 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 null;
}

// 사용 예시
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

해시 테이블 자료구조 이해하기를 통해 효율적인 알고리즘 설계의 기초를 다질 수 있습니다. 실무에서는 JavaScript의 Map/Set, Python의 dict, Java의 HashMap 등 최적화된 내장 구현을 사용하지만, 내부 동작 원리를 이해하면 더 나은 성능 최적화와 문제 해결이 가능합니다.