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

1. 알고리즘 소개 및 개념

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

2. 동작 원리 상세 설명

해시 테이블의 동작 원리는 해시 함수(Hash Function)를 중심으로 이루어집니다. 먼저 키를 입력받으면 해시 함수가 이를 고정된 크기의 해시 값(Hash Value)으로 변환합니다. 이 해시 값은 배열의 인덱스로 사용되어 해당 위치에 값을 저장합니다. 예를 들어, “apple”이라는 키가 해시 함수를 거쳐 5라는 인덱스로 변환되면, 배열의 5번째 위치에 “apple”에 대응하는 값을 저장합니다.

하지만 서로 다른 키가 같은 해시 값을 가질 수 있는 충돌(Collision) 문제가 발생할 수 있습니다. 이를 해결하기 위해 주로 두 가지 방법을 사용합니다. 첫째, 체이닝(Chaining) 방식은 같은 인덱스에 연결 리스트를 만들어 충돌한 데이터들을 저장합니다. 둘째, 개방 주소법(Open Addressing)은 충돌 시 다른 빈 공간을 찾아 데이터를 저장합니다. 선형 탐사, 이차 탐사, 이중 해싱 등의 기법이 있습니다. 좋은 해시 함수는 키를 균등하게 분산시켜 충돌을 최소화해야 합니다.

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

시간 복잡도:

• 평균 경우: 삽입, 삭제, 검색 모두 O(1) – 해시 함수가 키를 균등하게 분산시킬 때
• 최악 경우: O(n) – 모든 키가 같은 인덱스로 해싱되어 충돌이 발생할 때 (체이닝 방식에서 하나의 연결 리스트에 모든 데이터가 저장되는 경우)

공간 복잡도:

• O(n) – n개의 키-값 쌍을 저장하기 위한 공간
• 로드 팩터(Load Factor) = 저장된 데이터 개수 / 배열 크기
• 로드 팩터가 0.7~0.8을 초과하면 성능이 저하되므로 배열 크기를 늘리는 리해싱(Rehashing)이 필요합니다

효율적인 해시 테이블은 충돌을 최소화하고 로드 팩터를 적절히 유지하여 평균 O(1)의 성능을 보장합니다. 이는 배열의 O(n) 검색이나 이진 검색 트리의 O(log n)보다 훨씬 빠른 성능입니다.

4. 단계별 구현 과정

JavaScript로 체이닝 방식의 해시 테이블을 구현해보겠습니다.

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; // a=1, b=2, ...
      total = (total * PRIME + value) % this.keyMap.length;
    }
    
    return total;
  }
}

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 삭제(Delete) 메서드

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

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. 최적화 방법

1. 적절한 테이블 크기 선택: 소수(Prime Number)를 테이블 크기로 사용하면 해시 값의 분산이 더 균등해집니다. 53, 97, 193과 같은 소수를 권장합니다.

2. 동적 리사이징: 로드 팩터가 0.7을 초과하면 테이블 크기를 2배로 늘리고 모든 데이터를 재해싱합니다. 이를 통해 충돌 확률을 낮춥니다.

  resize() {
    const oldKeyMap = this.keyMap;
    this.keyMap = new Array(oldKeyMap.length * 2);
    
    for (let bucket of oldKeyMap) {
      if (bucket) {
        for (let [key, value] of bucket) {
          this.set(key, value);
        }
      }
    }
  }

3. 개선된 해시 함수: 더 복잡한 해시 함수(MurmurHash, CityHash 등)를 사용하여 충돌을 최소화합니다.

4. 이중 해싱: 개방 주소법 사용 시 두 번째 해시 함수를 적용하여 클러스터링을 방지합니다.

6. 실전 활용 예제

// 해시 테이블 생성 및 사용
const hashTable = new HashTable();

// 사용자 정보 저장
hashTable.set("user123", { name: "김철수", age: 25 });
hashTable.set("user456", { name: "이영희", age: 30 });
hashTable.set("user789", { name: "박민수", age: 28 });

// 데이터 조회
console.log(hashTable.get("user123")); // { name: "김철수", age: 25 }

// 데이터 수정
hashTable.set("user123", { name: "김철수", age: 26 });

// 데이터 삭제
hashTable.delete("user456");

// 모든 키 조회
console.log(hashTable.keys()); // ["user123", "user789"]

// 실전 활용: 중복 문자 찾기
function findDuplicates(str) {
  const charCount = new HashTable();
  
  for (let char of str) {
    const count = charCount.get(char) || 0;
    charCount.set(char, count + 1);
  }
  
  const duplicates = [];
  for (let char of charCount.keys()) {
    if (charCount.get(char) > 1) {
      duplicates.push(char);
    }
  }
  
  return duplicates;
}

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

마무리

해시 테이블 자료구조 이해하기를 통해 빠른 데이터 접근이 필요한 다양한 문제를 효율적으로 해결할 수 있습니다. 캐싱, 데이터베이스 인덱싱, 중복 검사, 빈도수 계산 등 실무에서 광범위하게 활용됩니다. 충돌 처리 방법과 최적화 기법을 이해하면 더욱 효율적인 해시 테이블을 구현할 수 있습니다. 해시 테이블 자료구조 이해하기는 코딩 테스트와 실무 개발 모두에서 필수적인 개념이므로, 직접 구현해보며 동작 원리를 체득하는 것이 중요합니다.