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

1. 알고리즘 소개 및 개념

해시 테이블 자료구조 이해하기는 현대 프로그래밍에서 가장 중요한 주제 중 하나입니다. 해시 테이블(Hash Table)은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조로, 해시 함수를 사용하여 키를 배열의 인덱스로 변환합니다. 이를 통해 데이터의 검색, 삽입, 삭제 연산을 평균적으로 O(1) 시간 복잡도로 수행할 수 있어 매우 효율적입니다. 해시 테이블은 데이터베이스 인덱싱, 캐시 구현, 중복 검사 등 다양한 실무 환경에서 핵심적으로 활용되며, 코딩 테스트에서도 빈번하게 출제되는 필수 자료구조입니다.

2. 동작 원리 상세 설명

해시 테이블의 동작 원리는 해시 함수(Hash Function)를 중심으로 이루어집니다. 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수로, 키를 입력받아 배열의 인덱스를 반환합니다. 예를 들어, 문자열 “apple”을 해시 함수에 넣으면 숫자 3이 나올 수 있고, 이는 배열의 3번 인덱스를 의미합니다.

해시 충돌(Hash Collision)은 서로 다른 키가 동일한 해시 값을 가질 때 발생합니다. 이를 해결하기 위한 대표적인 방법은 두 가지입니다:

• 체이닝(Chaining): 각 배열 요소에 연결 리스트를 두어 같은 해시 값을 가진 데이터들을 체인 형태로 연결합니다.
• 개방 주소법(Open Addressing): 충돌 발생 시 다른 빈 버킷을 찾아 데이터를 저장합니다. 선형 탐사, 이차 탐사, 이중 해싱 등의 방법이 있습니다.

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

해시 테이블의 성능은 해시 함수의 품질과 충돌 처리 방식에 따라 달라집니다.

시간 복잡도:

• 평균 경우: 검색, 삽입, 삭제 모두 O(1) – 이상적인 해시 함수와 적절한 로드 팩터 유지 시
• 최악 경우: O(n) – 모든 키가 동일한 해시 값으로 충돌하여 하나의 체인에 연결될 때

공간 복잡도:

• O(n) – n개의 키-값 쌍을 저장
• 로드 팩터(Load Factor) = 저장된 항목 수 / 배열 크기. 일반적으로 0.75를 초과하면 배열 크기를 2배로 늘려 재해싱(Rehashing)을 수행합니다.

좋은 해시 함수는 키들을 배열 전체에 균등하게 분산시켜 충돌을 최소화하고 O(1) 성능을 유지합니다.

4. 단계별 구현 과정

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

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;
      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: 삭제(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;
}

Step 5: 유틸리티 메서드

// 모든 키 반환
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;
}

5. 최적화 방법

해시 테이블 자료구조 이해하기를 넘어 성능을 극대화하는 최적화 기법들입니다:

1) 좋은 해시 함수 선택

• 빠른 계산 속도 (O(1))
• 균등 분산: 키들을 배열 전체에 고르게 분배
• 결정적: 동일한 입력에 항상 동일한 출력
• 소수(Prime Number) 사용: 배열 크기를 소수로 설정하면 충돌 감소

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++) {
        const [key, value] = oldKeyMap[i][j];
        this.set(key, value);
      }
    }
  }
}

3) 로드 팩터 관리

로드 팩터가 0.75를 초과하면 자동으로 리사이징하여 성능 저하를 방지합니다.

6. 실전 활용 예제

해시 테이블은 다양한 실전 문제에 활용됩니다:

예제 1: 두 배열의 교집합 찾기

function findIntersection(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.delete(num.toString()); // 중복 방지
    }
  }
  
  return result;
}

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

예제 2: 문자열에서 첫 번째 반복되지 않는 문자 찾기

function firstUniqueChar(str) {
  const hashTable = new HashTable();
  
  // 각 문자의 출현 횟수 카운트
  for (let char of str) {
    const count = hashTable.get(char) || 0;
    hashTable.set(char, count + 1);
  }
  
  // 첫 번째 고유 문자 찾기
  for (let char of str) {
    if (hashTable.get(char) === 1) {
      return char;
    }
  }
  
  return null;
}

console.log(firstUniqueChar("leetcode")); // "l"

예제 3: 애너그램 그룹화

function groupAnagrams(words) {
  const hashTable = new HashTable();
  
  for (let word of words) {
    const sorted = word.split('').sort().join('');
    const group = hashTable.get(sorted) || [];
    group.push(word);
    hashTable.set(sorted, group);
  }
  
  return hashTable.values();
}

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

마무리

해시 테이블 자료구조 이해하기를 통해 효율적인 데이터 관리의 핵심을 배웠습니다. 평균 O(1)의 시간 복잡도로 검색, 삽입, 삭제를 수행할 수 있는 해시 테이블은 실무와 코딩 테스트 모두에서 필수적인 자료구조입니다. 좋은 해시 함수 설계, 적절한 충돌 처리, 그리고 동적 리사이징을 통해 최적의 성능을 달성할 수 있습니다. 지속적인 연습을 통해 해시 테이블 자료구조 이해하기를 완벽히 마스터하시기 바랍니다.