avatar

자료구조: 해시(Hash)

Algorithm
2025. 11. 27.
5분

이번 포스팅에서는 해시(Hash)에 대해 정리하고자 합니다.

해시란?

해시란 해시함수를 사용하여 변환한 값을 인덱스로 삼아 키(key)와 값(value)을 저장하여 빠른 데이터 탐색을 제공하는 자료구조 입니다. 보통은 인덱스를 활용해서 탐색을 빠르게 만들지만, 해시는 키를 활용하여 데이터 탐색을 빠르게 합니다.

키를 통해서 데이터에 바로 접근할 수 있어 사람에게는 숫자(인덱스)로 데이터를 관리하는 배열보다 접근성이 좋은 자료구조라고 할 수 있습니다.

해시 함수(hash function)

해시 함수(hash function)는 키를 입력으로 받아 해시 테이블(hash table)의 인덱스를 반환하는 함수

해시 테이블(hash table)

해시 테이블(hash table)은 해시 함수(hash function)를 사용하여 변환한 값을 인덱스로 삼아 키(key)와 값(value)을 저장하는 자료구조

해시의 특징

  1. 해시는 단방향으로 동작
  2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있음
  3. 값을 인덱스로 활용하기 위해서는 적절한 변환 과정을 거쳐야함

해시는 위와 같은 특징이 있습니다.

  • 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요가 없고, 단방향으로만 동작하는 해시의 특성은 외부에 정보를 안전하게 제공한다는 특징이 있어서 네트워크 보안에서 많이 활용함

해시 특성 활용 분야

  • 비밀번호 관리
  • DB 인덱싱
  • 블록체인

해시의 장단점

장점

  • 빠른 데이터 탐색
  • 단방향으로 동작하여 외부에 정보를 안전하게 제공
  • 키에 대한 데이터가 있는지 확인 쉬움

단점

  • 일반적으로 저장 공간 많이 필요
  • 해시 함수의 충돌 가능성 존재 -> 해결 위한 별도 자료구조 필요
  • 해시 함수의 복잡도

해시 시간 복잡도

  • 일반적으로 O(1)에서 바로 찾을 수 있음
  • 모든 인덱스에서 충돌하는 최악의 경우에는 O(n)에서 찾을 수 있음

해시 함수의 충돌 해결 방법

  • Chaining 기법
  • Linear Probing 기법
  • Open Addressing 기법

해시 구현 예제(Javascript)

class HashTable {
  constructor(size = 53) {
    this.buckets = Array.from({ length: size }, () => []);
  }
 
  _hash(key) {
    let total = 0;
    const PRIME = 31;
    const limit = Math.min(key.length, 100);
    for (let i = 0; i < limit; i++) {
      const char = key[i];
      const value = char.charCodeAt(0);
      total = (total * PRIME + value) % this.buckets.length;
    }
    return total;
  }
 
  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      const [k] = bucket[i];
      if (k === key) {
        bucket[i][1] = value; // update
        return;
      }
    }
    bucket.push([key, value]); // insert
  }
 
  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      const [k, v] = bucket[i];
      if (k === key) return v;
    }
    return undefined;
  }
 
  has(key) {
    return this.get(key) !== undefined;
  }
 
  delete(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      const [k] = bucket[i];
      if (k === key) {
        bucket.splice(i, 1);
        return true;
      }
    }
    return false;
  }
 
  keys() {
    const out = [];
    for (const bucket of this.buckets) {
      for (const [k] of bucket) out.push(k);
    }
    return out;
  }
 
  values() {
    const out = [];
    for (const bucket of this.buckets) {
      for (const [, v] of bucket) out.push(v);
    }
    return out;
  }
}
 
// example
const table = new HashTable();
table.set("apple", 100);
table.set("banana", 200);
table.set("grape", 300);
table.set("papel", 123); // 의도적 충돌 가능성 키
 
console.log(table.get("banana")); // 200
console.log(table.has("grape")); // true
console.log(table.delete("apple")); // true
console.log(table.get("apple")); // undefined
console.log(table.keys());
console.log(table.values());