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

해시 테이블 자료구조 이해하기는 효율적인 데이터 저장과 검색을 위한 핵심 개념입니다. 해시 테이블(Hash Table)은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하며, 해시 함수를 사용하여 키를 배열의 인덱스로 변환합니다. 이를 통해 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입, 검색, 삭제할 수 있어 실무에서 가장 많이 활용되는 자료구조 중 하나입니다. 해시 테이블은 데이터베이스 인덱싱, 캐시 구현, 중복 검사 등 다양한 분야에서 필수적으로 사용됩니다.

1. 알고리즘 소개 및 개념

해시 테이블은 연관 배열(Associative Array) 구조를 구현한 자료구조로, 키를 해시 함수에 통과시켜 얻은 해시 값을 배열의 인덱스로 사용합니다. 예를 들어, “apple”이라는 키를 해시 함수에 넣으면 숫자 5가 나오고, 배열의 5번 인덱스에 값을 저장하는 방식입니다. 이 과정에서 서로 다른 키가 같은 해시 값을 가질 수 있는데, 이를 충돌(Collision)이라고 합니다. 해시 테이블의 성능은 좋은 해시 함수 설계와 효과적인 충돌 해결 방법에 달려 있습니다. JavaScript의 Object, Python의 Dictionary, Java의 HashMap이 모두 해시 테이블을 기반으로 구현되어 있습니다.

2. 동작 원리 상세 설명

해시 테이블의 동작은 크게 세 단계로 이루어집니다. 첫째, 해시 함수가 키를 받아 고정된 크기의 해시 값으로 변환합니다. 일반적으로 문자열의 각 문자 코드를 더하거나 곱한 후 배열 크기로 나눈 나머지를 사용합니다. 둘째, 계산된 해시 값을 배열의 인덱스로 사용하여 데이터를 저장하거나 검색합니다. 셋째, 충돌이 발생하면 이를 해결합니다. 충돌 해결 방법에는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다. 체이닝은 같은 인덱스에 연결 리스트로 여러 값을 저장하는 방식이고, 개방 주소법은 충돌 시 다른 빈 공간을 찾아 저장하는 방식입니다. 체이닝은 구현이 간단하고 테이블이 가득 차도 동작하지만, 추가 메모리가 필요합니다. 개방 주소법은 메모리 효율적이지만 클러스터링 문제가 발생할 수 있습니다. 좋은 해시 함수는 키를 균등하게 분산시켜 충돌을 최소화해야 합니다.

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

해시 테이블의 시간 복잡도는 해시 함수의 품질과 충돌 해결 방법에 따라 달라집니다. 이상적인 경우 삽입, 검색, 삭제 모두 O(1)의 시간 복잡도를 가집니다. 이는 해시 함수가 키를 균등하게 분산시키고 충돌이 거의 없을 때입니다. 하지만 최악의 경우, 모든 키가 같은 인덱스로 해시되면 O(n)의 시간 복잡도를 가집니다. 체이닝을 사용할 경우 한 인덱스의 연결 리스트를 순회해야 하므로 최악의 경우 O(n)입니다. 평균적으로는 로드 팩터(Load Factor, 저장된 요소 수 / 배열 크기)가 0.7 이하로 유지되면 O(1)에 가까운 성능을 보입니다. 공간 복잡도는 O(n)으로, n개의 요소를 저장하기 위한 배열과 체이닝의 경우 추가 연결 리스트가 필요합니다. 로드 팩터가 높아지면 배열 크기를 늘리고 모든 요소를 재해싱(Rehashing)해야 하는데, 이 과정은 O(n)의 시간이 걸리지만 드물게 발생하므로 분할 상환 분석으로 O(1)로 간주됩니다.

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; // 'a' = 1, 'b' = 2, ...
      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 keysArray = [];
    
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          keysArray.push(this.keyMap[i][j][0]);
        }
      }
    }
    
    return keysArray;
  }

  // 모든 값 반환
  values() {
    const valuesArray = [];
    const seen = new Set();
    
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          const value = this.keyMap[i][j][1];
          if (!seen.has(value)) {
            valuesArray.push(value);
            seen.add(value);
          }
        }
      }
    }
    
    return valuesArray;
  }
}

이 구현에서 핵심은 해시 함수입니다. 소수(31)를 곱하는 방식으로 문자열의 각 문자를 처리하여 균등한 분산을 만들어냅니다. set 메서드는 충돌 시 체이닝으로 처리하며, 같은 키가 있으면 값을 업데이트합니다.

5. 최적화 방법

해시 테이블의 성능을 최적화하는 방법은 여러 가지가 있습니다. 첫째, 적절한 초기 크기를 설정합니다. 저장할 데이터 수를 예상하여 로드 팩터가 0.7을 넘지 않도록 배열 크기를 설정합니다. 둘째, 좋은 해시 함수를 사용합니다. 균등 분포를 만들기 위해 소수를 활용하고, 충분히 큰 범위로 해시 값을 생성합니다. 셋째, 동적 리사이징을 구현합니다. 로드 팩터가 임계값을 초과하면 배열 크기를 2배로 늘리고 모든 요소를 재해싱합니다. 넷째, 적절한 충돌 해결 방법을 선택합니다. 데이터가 많고 메모리가 충분하면 체이닝을, 메모리 효율이 중요하면 이중 해싱을 사용합니다. 다섯째, 캐시 친화적인 구조를 사용합니다. 개방 주소법은 연속된 메모리를 사용하여 캐시 효율이 좋습니다. 마지막으로 문자열 키의 경우 해시 값을 캐싱하여 중복 계산을 피합니다.

6. 실전 활용 예제

해시 테이블 자료구조 이해하기의 실전 예제로 두 수의 합 문제를 해결해보겠습니다:

// 배열에서 합이 target이 되는 두 수의 인덱스 찾기
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]

// 문자열에서 첫 번째 중복되지 않는 문자 찾기
function firstUniqChar(s) {
  const charCount = new Map();
  
  // 각 문자의 빈도 계산
  for (const char of s) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }
  
  // 첫 번째 빈도 1인 문자 찾기
  for (let i = 0; i < s.length; i++) {
    if (charCount.get(s[i]) === 1) {
      return i;
    }
  }
  
  return -1;
}

console.log(firstUniqChar('leetcode')); // 0 ('l')
console.log(firstUniqChar('loveleetcode')); // 2 ('v')

이러한 문제들은 해시 테이블을 사용하면 O(n) 시간에 해결할 수 있지만, 브루트 포스 방식으로는 O(n²)이 걸립니다. 해시 테이블은 코딩 테스트와 실무에서 필수적인 자료구조이므로, 개념을 완벽히 이해하고 직접 구현해보는 것이 중요합니다.