자료구조와 알고리즘, Hash Table

 

해시 테이블(Hash Table)은 키(Key)와 값(Value)의 쌍을 저장하고, 빠르게 데이터를 검색, 삽입, 삭제할 수 있는 자료 구조입니다. 해시 테이블은 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용해 배열에 값을 저장합니다.

해시 테이블의 특징

1. 빠른 검색, 삽입, 삭제: 평균적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제 작업을 수행할 수 있습니다.
2. 해시 함수(Hash Function): 키를 입력받아 고정된 크기의 해시 값(주로 정수)을 반환하는 함수입니다. 좋은 해시 함수는 키를 고르게 분포시키고 충돌을 최소화합니다.
3. 충돌(Collision): 서로 다른 키가 동일한 해시 값을 갖는 상황을 충돌이라고 합니다. 충돌을 해결하는 방법으로 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다.

충돌 해결 방법

1. 체이닝(Chaining): 각 배열 요소를 연결 리스트로 관리하여, 충돌이 발생하면 해당 인덱스의 리스트에 노드를 추가하는 방식입니다.
2. 개방 주소법(Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장하는 방식입니다. 대표적인 방법으로 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.

자바스크립트로 해시 테이블 구현하기

간단한 해시 함수 구현

function hash(key, arrayLen) {
  let total = 0;
  let WEIRD_PRIME = 31;
  for (let i = 0; i < Math.min(key.length, 100); i++) {
    let char = key[i];
    let value = char.charCodeAt(0) - 96;
    total = (total * WEIRD_PRIME + value) % arrayLen;
  }
  return total;
}

체이닝을 이용한 해시 테이블 구현

class HashTable {
  // 소수 값을 기본 값으로 설정한다
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    // 소수를 곱하면, 단어간의 충돌 횟수가 현저히 줄어들었음
    let WEIRD_PRIME = 31;

    // 키 값의 길이가 100이 넘는다면, 100을 사용하여 루프를 돈다
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }

  set(key, value) {
    // Separate Chaining, Linear Probing 중 개별 체이닝 사용
    // Accepts a key and a value
    // Hashes the key
    // Stores the key-value pair in the hash table array via separate chaining
    let index = this._hash(key);

    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }

  get(key) {
    // Accepts a key
    // Hashes the key
    // Retrieves the key-value pair in the hash table
    let 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];
        }
      }
    }
    return undefined;
  }

  keys() {
    let results = [];
    for (let key of this.keyMap) {
      if (key) {
        for (let [key, value] of key) {
          if (!results.includes(key)) results.push(key);
        }
      }
    }
    return results;
  }

  values() {
    let results = [];
    for (let key of this.keyMap) {
      if (key) {
        for (let [key, value] of key) {
          if (!results.includes(value)) results.push(value);
        }
      }
    }
    return results;
  }
}

let newHashTable = new HashTable();

newHashTable.set('bowow', 'A');
newHashTable.set('cowow', 'B');
newHashTable.set('dowow', 'C');
newHashTable.set('Awwww', 'D');
newHashTable.set('Awwww', 'D');
newHashTable.set('Awwww', 'D');

newHashTable.get('Awwww');
console.log(newHashTable.keys());
console.log(newHashTable.values());

/**
 * newHashTable: HashTable {
  keyMap: [
    <19 empty items>,
    [ [Array] ],
    <3 empty items>,
    [ [Array], [Array] ],
    <3 empty items>,
    [ [Array] ],
    <25 empty items>
  ]
}
 */

선형 탐사를 통한 구현

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }

  set(key, value) {
    let index = this._hash(key);
    // 선형 탐사를 사용하여 빈 슬롯을 찾음
    while (this.keyMap[index] !== undefined && this.keyMap[index].key !== key) {
      index = (index + 1) % this.keyMap.length;
    }
    this.keyMap[index] = { key, value };
  }

  get(key) {
    let index = this._hash(key);
    // 선형 탐사를 사용하여 키를 찾음
    while (this.keyMap[index] !== undefined) {
      if (this.keyMap[index].key === key) {
        return this.keyMap[index].value;
      }
      index = (index + 1) % this.keyMap.length;
    }
    return undefined;
  }

  keys() {
    let keysArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        keysArr.push(this.keyMap[i].key);
      }
    }
    return keysArr;
  }

  values() {
    let valuesArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        valuesArr.push(this.keyMap[i].value);
      }
    }
    return valuesArr;
  }
}

// 사용 예시
let ht = new HashTable(17);
ht.set("maroon", "#800000");
ht.set("yellow", "#FFFF00");
ht.set("olive", "#808000");
ht.set("salmon", "#FA8072");
ht.set("lightcoral", "#F08080");
ht.set("mediumvioletred", "#C71585");
ht.set("plum", "#DDA0DD");

console.log(ht.get("yellow")); // #FFFF00
console.log(ht.keys()); // ["maroon", "yellow", "olive", "salmon", "lightcoral", "mediumvioletred", "plum"]
console.log(ht.values()); // ["#800000", "#FFFF00", "#808000", "#FA8072", "#F08080", "#C71585", "#DDA0DD"]

해시 테이블의 장점

1. 빠른 데이터 접근: 평균적으로 O(1) 시간 복잡도로 데이터 접근이 가능합니다.
2. 간단한 구현: 비교적 간단하게 구현할 수 있으며, 대부분의 프로그래밍 언어에서 내장 자료 구조로 제공됩니다.

해시 테이블의 단점

1. 충돌 처리: 충돌이 발생하면 성능이 저하될 수 있으며, 이를 해결하기 위한 추가적인 구조가 필요합니다.
2. 공간 낭비: 해시 테이블의 크기를 적절하게 설정하지 않으면 메모리 낭비가 발생할 수 있습니다.
3. 정렬되지 않은 데이터: 데이터가 특정 순서로 저장되지 않기 때문에 정렬된 데이터를 제공해야 하는 경우에는 적합하지 않습니다.

해시 테이블의 응용

1. 캐싱: 데이터베이스 조회 결과 등을 캐싱하여 성능을 향상시킬 때 사용됩니다.
2. 집합 연산: 집합의 포함 여부를 빠르게 확인할 수 있는 자료 구조로 사용됩니다.
3. 연관 배열: 키와 값을 맵핑하는 연관 배열이나 사전을 구현하는 데 사용됩니다.

해시 테이블은 매우 강력하고 효율적인 자료 구조로, 많은 알고리즘과 시스템에서 필수적인 역할을 합니다.