JavaScript로 설명하는 Hash Table

Hash Table

Hash라는 개념은 컴퓨터 공학을 공부하다보면 정말 자주 나오는 개념이다.

블록체인이나 암호학을 공부한다면 정말 한번도 빼놓지 않고 들을 수 있고, 데이터베이스를 공부하다보면 해시테이블에 관한 내용을 심심치 않게 접한다.

개요

먼저 간단하게 Hash Table(Hash Map)이 무엇인지 설명하겠다.

위 그림은 전화번호부에 있는 사람들을 Hash Table에 저장을 할 때 어떤 식으로 저장이 되는지 묘사한 그림이다.

Key인 사람이름을 Hash Function을 통해 인덱싱을 한다. 해당 Index에 값인 Value는 bucket (slot)에 저장이 된다.

컴퓨터 공학에서는 associative array라고 분류를 한다. (map, symbol table, dictionary가 해당) 즉, 연관배열이라는 뜻이다.

(key, value) 이런식으로 저장을 한다.

그런데 해싱을 하면 똑같은 Index번호를 받을 수 있는데 (여기서 Index 번호라고 설명하겠다. 정확히는 digest 혹은 해시함수 값)

이런 경우를 충돌(Collision)이 났다고 말한다. 그러면 중복이 일어나는데 

이때 Hash Table은 Linked List형식으로 체인으로 연결한다.

Hash Table JavaScript 코드

const hash = (string, max) => {
  let hash = 0;
  for (let i = 0; i < string.length; i++) hash += string.charCodeAt(i);
  return hash % max;
};
 
const HashTable = function() {
  let storage = [];
  const storageLimit = 4;
 
  this.add = (key, value) => {
    const index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      storage[index] = [[key, value]];
    } else {
      const inserted = false;
      for (let i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          storage[index][i][1] = value;
          inserted = true;
        }
      }
      if (inserted == false) storage[index].push([key, value]);
    }
  };
 
  this.remove = key => {
    const index = hash(key, storageLimit);
    if (sotrage[index].lengh === 1 && storage[index][0][0] === key)
      delete storage[index];
    else {
      for (let i = 0; i < storage[index]; i++) {
        if (storage[index][i][0] === key) delete storage[index][i];
      }
    }
  };
 
  this.lookup = key => {
    const index = hash(key, storageLimit);
    if (storage[index] === undefined) return undefined;
    else {
      for (let i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) return storage[index][i][1];
      }
    }
  };
 
  this.print = () => {
    console.log(storage);
  };
};
 
console.log(hash('dongwoo', 10));
 
const ht = new HashTable();
ht.add('a', 'a');
ht.add('b', 'b');
ht.add('c', 'c');
ht.add('d', 'd');
console.log(ht.lookup('asd'));
ht.print();

[참고자료]

https://en.wikipedia.org/wiki/Hash_table

https://www.youtube.com/watch?v=F95z5Wxd9ks