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

1. 알고리즘 소개 및 개념

해시 테이블 자료구조 이해하기는 효율적인 데이터 저장과 검색을 위한 핵심 자료구조입니다. 해시 테이블은 키-값 쌍을 저장하며, 해시 함수를 사용하여 키를 배열의 인덱스로 변환합니다. 이를 통해 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입, 검색, 삭제할 수 있습니다. 해시 테이블은 데이터베이스 인덱싱, 캐싱 시스템, 프로그래밍 언어의 딕셔너리나 맵 구현에 광범위하게 활용됩니다. 해시 함수의 품질과 충돌 해결 방법이 해시 테이블의 성능을 결정하는 핵심 요소입니다.

2. 동작 원리 상세 설명

해시 테이블의 동작 원리는 크게 세 단계로 구성됩니다. 첫째, 해시 함수가 키를 입력받아 고정된 범위의 해시 값으로 변환합니다. 이 해시 값은 배열의 인덱스로 사용됩니다. 둘째, 계산된 인덱스 위치에 값을 저장하거나 검색합니다. 셋째, 서로 다른 키가 같은 해시 값을 가지는 충돌(Collision)이 발생할 경우 이를 해결해야 합니다.

충돌 해결 방법은 크게 두 가지입니다. 체이닝(Chaining)은 각 배열 요소에 연결 리스트를 두어 같은 해시 값을 가진 여러 항목을 저장합니다. 개방 주소법(Open Addressing)은 충돌 시 다른 빈 슬롯을 찾아 저장하는 방식으로, 선형 탐사, 이차 탐사, 이중 해싱 등의 기법이 있습니다. 체이닝은 구현이 간단하고 삭제가 용이하지만 추가 메모리가 필요하며, 개방 주소법은 메모리 효율적이지만 삭제 처리가 복잡합니다.

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

시간 복잡도:

• 평균 경우: 삽입 O(1), 검색 O(1), 삭제 O(1)
• 최악 경우: 삽입 O(n), 검색 O(n), 삭제 O(n) – 모든 키가 같은 해시 값으로 충돌하는 경우

해시 테이블의 성능은 로드 팩터(Load Factor = 저장된 항목 수 / 배열 크기)에 크게 영향받습니다. 로드 팩터가 0.7을 초과하면 충돌이 급격히 증가하여 성능이 저하됩니다. 이 경우 리해싱(Rehashing)을 통해 테이블 크기를 확장해야 합니다.

공간 복잡도:

• O(n) – n은 저장된 키-값 쌍의 개수
• 체이닝 방식은 포인터 저장을 위한 추가 공간 필요
• 개방 주소법은 배열만 사용하므로 공간 효율적

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

  // 삽입 연산
  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;
  }

  // 삭제 연산
  delete(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 = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!valuesArray.includes(this.keyMap[i][j][1])) {
            valuesArray.push(this.keyMap[i][j][1]);
          }
        }
      }
    }
    return valuesArray;
  }
}

4.2 개방 주소법(선형 탐사) 구현

class OpenAddressingHashTable {
  constructor(size = 53) {
    this.size = size;
    this.keys = new Array(size);
    this.values = new Array(size);
    this.count = 0;
  }

  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      total = (total * PRIME + key.charCodeAt(i)) % this.size;
    }
    return total;
  }

  set(key, value) {
    if (this.count / this.size >= 0.7) {
      this._resize();
    }

    let index = this._hash(key);
    
    // 선형 탐사로 빈 슬롯 찾기
    while (this.keys[index] !== undefined && this.keys[index] !== key) {
      index = (index + 1) % this.size;
    }
    
    if (this.keys[index] === undefined) {
      this.count++;
    }
    
    this.keys[index] = key;
    this.values[index] = value;
  }

  get(key) {
    let index = this._hash(key);
    
    while (this.keys[index] !== undefined) {
      if (this.keys[index] === key) {
        return this.values[index];
      }
      index = (index + 1) % this.size;
    }
    return undefined;
  }

  _resize() {
    const oldKeys = this.keys;
    const oldValues = this.values;
    
    this.size *= 2;
    this.keys = new Array(this.size);
    this.values = new Array(this.size);
    this.count = 0;
    
    for (let i = 0; i < oldKeys.length; i++) {
      if (oldKeys[i] !== undefined) {
        this.set(oldKeys[i], oldValues[i]);
      }
    }
  }
}

5. 최적화 방법

1. 좋은 해시 함수 설계: 해시 함수는 키를 균등하게 분산시켜야 합니다. 소수를 곱하는 방법, 비트 연산 활용, FNV-1a, MurmurHash 같은 검증된 해시 함수 사용이 효과적입니다.

2. 적절한 테이블 크기 선택: 테이블 크기를 소수로 설정하면 충돌을 줄일 수 있습니다. 일반적으로 53, 97, 193 같은 소수를 사용합니다.

3. 동적 리사이징: 로드 팩터가 임계값(보통 0.7)을 초과하면 테이블 크기를 2배로 확장하고 모든 요소를 재배치합니다. 이를 통해 평균 성능을 O(1)로 유지할 수 있습니다.

4. 이중 해싱: 개방 주소법에서 선형 탐사 대신 이중 해싱을 사용하면 클러스터링을 방지하고 더 균등한 분산을 얻을 수 있습니다.

5. 캐시 친화적 설계: 체이닝보다 개방 주소법이 메모리 지역성이 좋아 캐시 성능이 우수합니다. 성능이 중요한 경우 개방 주소법을 고려하세요.

6. 실전 활용 예제

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

// 데이터 삽입
hashTable.set('name', 'John');
hashTable.set('age', 30);
hashTable.set('city', 'Seoul');
hashTable.set('email', '[email protected]');

// 데이터 검색
console.log(hashTable.get('name')); // 'John'
console.log(hashTable.get('age'));  // 30

// 데이터 업데이트
hashTable.set('age', 31);
console.log(hashTable.get('age'));  // 31

// 모든 키와 값 조회
console.log(hashTable.keys());   // ['name', 'age', 'city', 'email']
console.log(hashTable.values()); // ['John', 31, 'Seoul', '[email protected]']

// 데이터 삭제
hashTable.delete('email');
console.log(hashTable.get('email')); // undefined

// 실전 활용: 문자열에서 첫 번째 중복되지 않는 문자 찾기
function firstUniqueChar(str) {
  const charCount = new HashTable();
  
  // 각 문자의 출현 횟수 카운트
  for (let char of str) {
    const count = charCount.get(char) || 0;
    charCount.set(char, count + 1);
  }
  
  // 첫 번째 유일한 문자 찾기
  for (let char of str) {
    if (charCount.get(char) === 1) {
      return char;
    }
  }
  return null;
}

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

해시 테이블 자료구조 이해하기를 통해 빠른 데이터 접근이 필요한 다양한 문제를 효율적으로 해결할 수 있습니다. 두 수의 합 찾기, 애너그램 그룹화, LRU 캐시 구현 등 코딩 테스트의 많은 문제가 해시 테이블을 활용합니다.