해시 테이블(Hash Table)

Doozuu·2023년 3월 22일

자료구조 해시 테이블 해시함수

알고리즘&자료구조 (JS)

목록 보기

21/25

📌 Hash Table

해시 테이블은 데이터를 key-value 쌍으로 묶은 자료구조를 말한다.

거의 대부분의 언어에 해시 테이블 기능이 있으며, 자주 사용되는 자료 구조이다.
JS 에서는 object 와 Map이 해시 테이블에 해당한다. (특히 Map)
Python 에서는 Dictionary가 해시 테이블에 해당한다.
연속적인 데이터면 배열을 사용하면 되지만 연속적이지 않은 경우 해시 테이블을 사용한다.

📌 해시 함수

해시 함수란 임의의 크기를 가지는 데이터를 입력하면 정해진 크기의 데이터를 출력하는 함수를 말한다.
해시 함수는 개인 정보 보호, 일반 계산 업무 등에서 사용된다.

좋은 해시 함수의 요건

속도가 빨라야 한다.

데이터가 균일하게 퍼져있도록 해야 한다.

결정론적이어야 한다.(같은 값을 입력하면 항상 같은 출력값이 나와야 한다. 불확실하면 안됨.)

문자열을 숫자로 바꾸는 방법 : 유니코드 활용

알파벳을 charCodeAt() 해서 숫자로 바꾸고 96을 빼면 알파벳 순서와 같아진다.

문자열 각각의 문자를 위와 같이 숫자로 바꾸어서 전부 더한다.
더한 값을 11로 나눈 나머지를 이용해 0-9까지의 숫자가 나오도록 해준다.
(혹은 해시 테이블 길이로 나눈 나머지)

function hash(key, arrayLen) {
  let total = 0;
  for (let char of key) {
    // map "a" to 1, "b" to 2, "c" to 3, etc.
    let value = char.charCodeAt(0) - 96
    total = (total + value) % arrayLen;
  }
  return total;
}

성능 개선

데이터가 잘 겹치지 않게 하기 위해 소수를 활용한다.
해시 테이블 길이를 소수로 했을 때 충돌이 훨씬 덜 일어난다는 연구 결과가 있다.
또한 Math.min을 이용해 크기를 제한해준다.

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

📌 충돌 처리

데이터가 많은 경우 충돌이 더 자주 일어날 수 있다.
이때, 충돌은 데이터가 저장된 장소가 겹치는 것을 의미한다.

이를 처리하기 위한 두 가지 방법이 있다.

1. Seperate chaining

같은 장소에 여러 데이터를 저장할 때, 배열이나 연결 리스트와 같은 것을 활용해 이중 데이터 구조를 쓰는 것(중첩 구조)

아래는 이중 배열을 이용해 4 자리에 두 개의 데이터를 저장했다.

2. Linear Probing

각 위치에 하나의 데이터만 저장하는 규칙을 적용.
-> 충돌이 발생하면 다음 빈칸을 찾아 거기에 저장한다.

세 개의 데이터의 위치가 모두 4를 가리킬 때, 4 자리에 먼저 darblue를 넣는다.
4 자리가 이미 채워져 있으므로 salmon은 다음 빈 자리인 5에 놓고, tomato는 그 다음 빈 자리인 6에 놓아 각 위치에 하나의 데이터만 있도록 한다.

📌 Set & Get 메소드

Set

key, value를 받아서 어디에 저장할지 찾아내고 seperate chaining 하기

Get

key를 받아서 위치를 찾고 해당 value를 반환
(해당 인덱스(숫자)로 위치를 찾고, 중첩된 배열에서 반복문을 돌아 일치하는 key 찾기)

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);
    if(!this.keyMap[index]){
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
  get(key){
    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][1]
        }
      }
    }
    return undefined;
  }
}

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")

📌 keys & values 메소드

keys

모든 key를 배열에 담아서 출력.
(겹치는건 하나만 출력하도록 includes로 확인.)

values

모든 value를 배열에 담아서 출력
(겹치는건 하나만 출력하도록 includes로 확인.)

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);
    if(!this.keyMap[index]){
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
  get(key){
    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][1]
        }
      }
    }
    return undefined;
  }
  keys(){
    let keysArr = [];
    for(let i = 0; i < this.keyMap.length; i++){
      if(this.keyMap[i]){
        for(let j = 0; j < this.keyMap[i].length; j++){
          if(!keysArr.includes(this.keyMap[i][j][0])){
            keysArr.push(this.keyMap[i][j][0])
          }
        }
      }
    }
    return keysArr;
  }
  values(){
    let 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;
  }
}

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")
ht.set("purple","#DDA0DD")
ht.set("violet","#DDA0DD")


ht.keys().forEach(function(key){
  console.log(ht.get(key));
})