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

1. 알고리즘 소개 및 개념

해시 테이블 자료구조 이해하기는 효율적인 데이터 검색과 저장을 위한 핵심 개념입니다. 해시 테이블(Hash Table)은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조로, 해시 함수를 사용하여 키를 배열의 인덱스로 변환합니다. 이를 통해 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입, 삭제, 검색할 수 있어 매우 효율적입니다. 해시 테이블은 딕셔너리, 맵, 연관 배열 등 다양한 이름으로 불리며, JavaScript의 Object, Python의 Dictionary, Java의 HashMap 등으로 구현되어 있습니다. 대용량 데이터 처리와 빠른 검색이 필요한 실무 환경에서 필수적으로 활용되는 자료구조입니다.

2. 동작 원리 상세 설명

해시 테이블의 핵심은 해시 함수(Hash Function)입니다. 해시 함수는 임의의 크기를 가진 키를 고정된 크기의 해시 값(해시 코드)으로 변환합니다. 이 해시 값은 배열의 인덱스로 사용되어 데이터가 저장될 위치를 결정합니다. 예를 들어, 문자열 “apple”을 키로 사용하면 해시 함수가 이를 숫자 5로 변환하고, 배열의 5번 인덱스에 해당 값을 저장합니다.

하지만 서로 다른 키가 같은 해시 값을 가지는 충돌(Collision) 문제가 발생할 수 있습니다. 이를 해결하기 위한 대표적인 방법은 두 가지입니다. 첫째, 체이닝(Chaining) 방식은 각 배열 요소를 연결 리스트로 구성하여 같은 인덱스에 여러 데이터를 저장합니다. 둘째, 개방 주소법(Open Addressing)은 충돌 발생 시 다른 빈 공간을 찾아 데이터를 저장합니다. 선형 탐사, 이차 탐사, 이중 해싱 등의 기법이 사용됩니다. 좋은 해시 함수는 데이터를 균등하게 분산시켜 충돌을 최소화하고, 계산이 빠르며, 결정적(같은 입력에 항상 같은 출력)이어야 합니다.

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

시간 복잡도:

• 평균 경우: 삽입, 삭제, 검색 모두 O(1) – 해시 함수가 데이터를 균등하게 분산시키고 충돌이 적을 때
• 최악 경우: O(n) – 모든 키가 같은 해시 값으로 매핑되어 하나의 버킷에 집중될 때 (체이닝 방식에서 연결 리스트 탐색)

공간 복잡도:

• O(n) – n개의 키-값 쌍을 저장
• 로드 팩터(Load Factor) = 저장된 항목 수 / 배열 크기. 일반적으로 0.75를 넘으면 배열을 확장(리해싱)하여 성능을 유지합니다.
• 체이닝 방식은 추가 포인터 공간이 필요하고, 개방 주소법은 배열만 사용하여 메모리 효율이 더 좋습니다.

해시 테이블은 공간을 조금 더 사용하는 대신 시간 효율성을 크게 향상시키는 트레이드오프 관계를 가집니다. 실무에서는 평균 O(1)의 성능을 활용하여 캐싱, 데이터베이스 인덱싱, 중복 제거 등에 광범위하게 사용됩니다.

4. 단계별 구현 과정

4.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;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    
    return total;
  }
}

해시 함수는 소수(Prime Number)를 사용하여 충돌을 줄입니다. 문자열의 각 문자를 숫자로 변환하고, 배열 크기로 나눈 나머지를 인덱스로 사용합니다.

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

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

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

5. 최적화 방법

5.1 적절한 테이블 크기 선택

소수(Prime Number)를 테이블 크기로 사용하면 해시 값의 분산이 더 균등해집니다. 53, 97, 193 같은 소수를 사용하세요.

5.2 동적 리사이징

  resize() {
    const oldKeyMap = this.keyMap;
    this.keyMap = new Array(oldKeyMap.length * 2);
    
    // 모든 데이터 재해싱
    for (let i = 0; i < oldKeyMap.length; i++) {
      if (oldKeyMap[i]) {
        for (let j = 0; j < oldKeyMap[i].length; j++) {
          this.set(oldKeyMap[i][j][0], oldKeyMap[i][j][1]);
        }
      }
    }
  }

로드 팩터가 0.75를 초과하면 테이블 크기를 2배로 늘려 성능을 유지합니다.

5.3 더 나은 해시 함수

murmur3, FNV-1a 같은 검증된 해시 알고리즘을 사용하면 충돌을 더욱 줄일 수 있습니다. 또한 다양한 데이터 타입(숫자, 객체 등)을 처리할 수 있도록 해시 함수를 확장하세요.

6. 실전 활용 예제

예제 1: 문자열에서 중복 문자 찾기

function findDuplicates(str) {
  const hashTable = new HashTable();
  const duplicates = [];
  
  for (let char of str) {
    const count = hashTable.get(char) || 0;
    hashTable.set(char, count + 1);
    
    if (count === 1) {
      duplicates.push(char);
    }
  }
  
  return duplicates;
}

console.log(findDuplicates("programming")); // ['r', 'g', 'm']

예제 2: 두 배열의 교집합

function intersection(arr1, arr2) {
  const hashTable = new HashTable();
  const result = [];
  
  // 첫 번째 배열의 요소를 해시 테이블에 저장
  for (let num of arr1) {
    hashTable.set(num.toString(), true);
  }
  
  // 두 번째 배열에서 해시 테이블에 있는 요소 찾기
  for (let num of arr2) {
    if (hashTable.get(num.toString())) {
      result.push(num);
      hashTable.remove(num.toString()); // 중복 방지
    }
  }
  
  return result;
}

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

예제 3: 캐싱 시스템 구현

class Cache {
  constructor() {
    this.cache = new HashTable();
  }
  
  get(key) {
    return this.cache.get(key);
  }
  
  set(key, value) {
    this.cache.set(key, value);
  }
  
  // 메모이제이션 예제
  memoizedFibonacci(n) {
    const cached = this.get(`fib_${n}`);
    if (cached !== undefined) return cached;
    
    if (n <= 1) return n;
    
    const result = this.memoizedFibonacci(n - 1) + this.memoizedFibonacci(n - 2);
    this.set(`fib_${n}`, result);
    return result;
  }
}

const cache = new Cache();
console.log(cache.memoizedFibonacci(50)); // 빠른 계산

마무리

해시 테이블 자료구조 이해하기를 통해 효율적인 데이터 관리의 핵심을 배웠습니다. 평균 O(1)의 시간 복잡도로 대용량 데이터를 빠르게 처리할 수 있으며, 충돌 해결 방법과 최적화 기법을 적용하면 실무에서 강력한 도구로 활용할 수 있습니다. 코딩 테스트에서는 빈도 계산, 중복 검사, 그룹핑 문제에 자주 사용되므로 반드시 숙지해야 합니다. 직접 구현해보고 다양한 문제에 적용하면서 해시 테이블 자료구조 이해하기를 완전히 마스터하세요!