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

1. 알고리즘 소개 및 개념

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

2. 동작 원리 상세 설명

해시 테이블의 동작 원리는 해시 함수(Hash Function)를 중심으로 이루어집니다. 먼저 키 값이 입력되면 해시 함수가 이를 정수형 해시 코드로 변환합니다. 이 해시 코드를 배열의 크기로 나눈 나머지를 구해 실제 저장 위치인 버킷(Bucket) 인덱스를 결정합니다. 예를 들어, 키 “apple”이 해시 함수를 통해 12345로 변환되고, 배열 크기가 10이라면 12345 % 10 = 5번 인덱스에 저장됩니다. 하지만 서로 다른 키가 같은 인덱스로 매핑되는 충돌(Collision)이 발생할 수 있습니다. 이를 해결하기 위해 체이닝(Chaining) 방식은 같은 인덱스에 연결 리스트로 여러 값을 저장하고, 개방 주소법(Open Addressing)은 다른 빈 공간을 찾아 저장합니다. 좋은 해시 함수는 키를 균등하게 분산시켜 충돌을 최소화하며, 이는 해시 테이블의 성능을 결정하는 핵심 요소입니다.

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

시간 복잡도:

• 평균 경우: 삽입 O(1), 삭제 O(1), 검색 O(1)
• 최악 경우: 삽입 O(n), 삭제 O(n), 검색 O(n) – 모든 키가 하나의 버킷에 충돌할 때

해시 함수가 잘 설계되고 적절한 로드 팩터(Load Factor)를 유지하면 평균 O(1) 성능을 보장합니다. 로드 팩터는 (저장된 항목 수 / 버킷 수)로 계산되며, 일반적으로 0.7~0.75를 초과하면 리해싱(Rehashing)을 통해 테이블 크기를 확장합니다.

공간 복잡도: O(n) – n개의 키-값 쌍을 저장하며, 체이닝 방식은 연결 리스트를 위한 추가 포인터 공간이 필요합니다. 개방 주소법은 배열만 사용하지만 충돌 해결을 위해 더 큰 배열이 필요할 수 있습니다.

4. 단계별 구현 과정

해시 테이블 자료구조 이해하기를 위해 체이닝 방식으로 구현해보겠습니다.

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

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

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

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

Step 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.75)을 초과하면 테이블 크기를 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. 더 나은 해시 함수: 충돌을 최소화하기 위해 SHA-256 같은 암호화 해시 함수를 사용하거나, 문자열의 모든 문자를 고려하는 해시 함수를 구현합니다.

4. 개방 주소법 활용: 메모리 효율이 중요한 경우 선형 탐사(Linear 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

// 데이터 삭제
ht.remove("banana");

// 모든 키와 값 조회
console.log(ht.keys());   // ["apple", "orange"]
console.log(ht.values()); // [120, 150]

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

console.log(findDuplicates("hello world")); // ["l", "o"]

마무리

해시 테이블 자료구조 이해하기를 통해 효율적인 데이터 관리의 핵심 원리를 배웠습니다. 해시 테이블은 빠른 검색이 필요한 캐싱, 데이터베이스 인덱싱, 중복 체크 등 다양한 실무 상황에서 필수적입니다. 충돌 처리 방법과 최적화 기법을 숙지하면 더욱 효율적인 프로그램을 작성할 수 있습니다.