해시 테이블 자료구조 이해하기 – 개념부터 구현까지 완벽 마스터

해시 테이블 자료구조 이해하기는 효율적인 데이터 저장과 검색을 위한 핵심 알고리즘입니다. 해시 테이블(Hash Table)은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 배열의 인덱스로 변환함으로써 평균 O(1)의 시간 복잡도로 데이터를 저장하고 검색할 수 있습니다. 이는 배열의 빠른 접근 속도와 연결 리스트의 유연한 데이터 관리를 결합한 강력한 자료구조입니다.

1. 알고리즘 소개 및 개념

해시 테이블은 키(key)를 해시 함수(hash function)에 통과시켜 해시값(hash value)을 얻고, 이를 배열의 인덱스로 사용하여 값(value)을 저장하는 자료구조입니다. 예를 들어, “apple”이라는 키를 해시 함수에 넣으면 숫자 5가 나오고, 배열의 5번 인덱스에 해당 값을 저장하는 방식입니다. 이를 통해 데이터를 빠르게 찾을 수 있으며, 사전(Dictionary), 맵(Map), 캐시(Cache) 등 다양한 용도로 활용됩니다. 해시 테이블의 핵심은 좋은 해시 함수를 설계하고 충돌(collision)을 효과적으로 처리하는 것입니다.

2. 동작 원리 상세 설명

해시 테이블의 동작은 크게 세 단계로 이루어집니다. 첫째, 해시 함수 적용 단계에서 키를 해시 함수에 입력하여 정수형 해시값을 생성합니다. 해시 함수는 동일한 입력에 대해 항상 같은 출력을 반환해야 하며, 가능한 한 균등하게 분포된 값을 생성해야 합니다. 둘째, 인덱스 계산 단계에서 해시값을 배열 크기로 나눈 나머지를 구하여 실제 저장 위치를 결정합니다(index = hashValue % arraySize). 셋째, 충돌 처리 단계에서 서로 다른 키가 같은 인덱스를 가리킬 때 이를 해결합니다. 대표적인 충돌 해결 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다. 체이닝은 같은 인덱스에 연결 리스트로 여러 값을 저장하고, 개방 주소법은 다른 빈 공간을 찾아 저장합니다.

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

시간 복잡도: 이상적인 경우 삽입, 검색, 삭제 모두 O(1)의 평균 시간 복잡도를 가집니다. 하지만 최악의 경우(모든 키가 같은 인덱스로 해시될 때) O(n)까지 증가할 수 있습니다. 좋은 해시 함수와 적절한 로드 팩터(load factor) 유지를 통해 평균 케이스를 유지하는 것이 중요합니다. 로드 팩터는 (저장된 항목 수 / 배열 크기)로 계산되며, 일반적으로 0.7을 넘으면 배열 크기를 늘려 재해싱(rehashing)을 수행합니다.

공간 복잡도: 저장된 키-값 쌍의 개수를 n이라 할 때 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] = [];
    }
    // 기존 키 업데이트 또는 새로운 키-값 추가
    const bucket = this.keyMap[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    bucket.push([key, value]);
  }

  // 데이터 검색
  get(key) {
    const index = this._hash(key);
    const bucket = this.keyMap[index];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          return bucket[i][1];
        }
      }
    }
    return undefined;
  }

  // 데이터 삭제
  delete(key) {
    const index = this._hash(key);
    const bucket = this.keyMap[index];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          bucket.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;
  }
}

5. 최적화 방법

1. 소수 크기 배열 사용: 배열 크기를 소수(prime number)로 설정하면 해시값이 더 균등하게 분포되어 충돌을 줄일 수 있습니다. 위 구현에서 기본 크기를 53으로 설정한 이유입니다.

2. 동적 재해싱(Dynamic Resizing): 로드 팩터가 임계값(보통 0.7-0.75)을 초과하면 배열 크기를 2배로 늘리고 모든 요소를 재해싱합니다. 이를 통해 평균 O(1) 성능을 유지할 수 있습니다.

3. 더 나은 해시 함수: 단순 합산 대신 곱셈과 비트 연산을 활용한 해시 함수(예: MurmurHash, FNV-1a)를 사용하면 충돌을 크게 줄일 수 있습니다.

4. 개방 주소법 최적화: 선형 탐사(Linear Probing) 대신 이차 탐사(Quadratic Probing)나 이중 해싱(Double Hashing)을 사용하면 클러스터링을 방지할 수 있습니다.

6. 실전 활용 예제

// 사용 예제
const ht = new HashTable();

// 데이터 삽입
ht.set("apple", 100);
ht.set("banana", 200);
ht.set("orange", 150);

// 데이터 검색
console.log(ht.get("apple")); // 100

// 데이터 수정
ht.set("apple", 120);
console.log(ht.get("apple")); // 120

// 모든 키 조회
console.log(ht.keys()); // ["apple", "banana", "orange"]

// 데이터 삭제
ht.delete("banana");
console.log(ht.get("banana")); // undefined

// 실전 문제: 두 배열에서 공통 요소 찾기
function findCommon(arr1, arr2) {
  const ht = new HashTable();
  const result = [];
  
  for (const item of arr1) {
    ht.set(item, true);
  }
  
  for (const item of arr2) {
    if (ht.get(item)) {
      result.push(item);
    }
  }
  
  return result;
}

console.log(findCommon([1,2,3,4], [3,4,5,6])); // [3, 4]

마무리

해시 테이블 자료구조 이해하기를 통해 효율적인 데이터 관리의 핵심을 배웠습니다. 해시 테이블은 데이터베이스 인덱싱, 캐싱 시스템, 중복 제거, 빈도수 계산 등 다양한 실전 문제에 활용됩니다. 좋은 해시 함수 설계와 충돌 처리 전략을 숙지하면 코딩 테스트와 실무에서 큰 도움이 될 것입니다. 해시 테이블 자료구조 이해하기의 핵심은 평균 O(1) 성능을 유지하기 위한 최적화에 있습니다.