HashTable(해시테이블) with JavaScript

* node 에서는 기본적으로 class를 사용하지 못하므로 babel을 사용해야 한다. 적용법은 최하단 링크에 있다. 귀찮으면 아래 링크의 git을 clone을 하시면 된다. 

Hash Table (이미지 출처 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94)

HashTable (해시테이블): Key 값와 Value 값을 매핑하여 사용하는 자료구조. 해시 함수를 이용하여 인덱스(색인)을 구할 수 있다.

Hash 함수 : 해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

 

왜 이런 짓을 하느냐? 뺘르게하려고!

내가 생각하는 해시테이블은 공간복잡도를 희생하여 시간복잡도를 높이려고 사용하는 기법이다.

---

* Hash Table은 대략 아래와 같은 형태를 가진다. 

value 1

value2

value3

value4

value5

Hash 함수를 이용하여 배열 내의 index 값을 얻어오고, 해당하는 index에 값을 넣은 형태로 자료를 구성한다.

배열 크기가 소수이고, 배열 내에 들어가는 값들의 수가 그보다 조금 작은 소수일 경우에 효율이 좋다고 한다.  

또, 배열이 꽉 차는 것보다 어느 정도 빈 공간이 있는 것이 효율이 좋다고 한다.

---

임의의 값 A와 B의 Hash 함수로 얻어온 index의 값이 같다고 가정해보자.

value 1

value 2, value 3

value4

위와 같은 경우를 충돌 Collision 이라고 한다. 

문제이므로 해결을 해야하는데, 대표적으로 두 가지 방법이 있다.

• Open Addressing
• Separate Chaining

 

Open Addresing : 옆에 빈 자리에 끼워넣는 방법. 이후에 찾을때는 hash 값 이후부터 key 값이 같은 녀석이 나올때까지 찾는다.

value 1

value 2

value 4

value 3

Separate Chaining : Linked List를 이용하여 다음 링크에 끼워넣는 방법. 찾을때는 그냥 링크타고 가면 된다.

value 1

value 2 -> value 3

value4

---

const hash = (string, storageSize) => {
    let hash = 0;
    for (let i = 0; i < string.length; i++) hash += string.charCodeAt(i);
    return hash % storageSize;
};

class Node {
    key;
    value;
    chain;

    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    setChain = (chain) => this.chain = chain;
}

class HashTable {
    size;
    storage;

    constructor(size) {
        this.size = size;
        this.storage = new Array(size);
    }

    add = (key, value) => {
        const node = new Node(key, value);
        const index = hash(key, this.size);

        if (!this.storage[index]) {
            this.storage[index] = node;
        } else {
            this.collision(node, index);
        }
        return;
    }

    collision = (node, index) => {
        if (!node.chain) {      // chain 값 없음
            this.storage[index].chain = node;
        } else {                // chain 값이 있을때
            this.collision(node.chain, index);
        }
    }

    lookUp = (key) => {
        const index = hash(key, this.size);
        const foundNode = this.storage[index];
        if (foundNode.key === key) {
            return foundNode;
        } else {
            return this.lookUpChain(foundNode.chain, key);
        }
    }

    lookUpChain(node, key) {
        if (node.key === key) {
            return node;
        } else {
            return this.lookUpChain(node.chain, key);
        }
    }

    countAll = () => {
        let cnt = 0;
        this.storage.map(each => cnt += this.countChains(each))
        return cnt;
    }

    countChains = (node) => {
        let eachCnt = 0;
        if (!node) {
            return 0;
        } else {
            eachCnt++;
            eachCnt += this.countChains(node.chain);
        }
        return eachCnt;
    }

}


const hTable = new HashTable(23);
for (let i = 0; i < 17; i++) {
    hTable.add(`Node ${i}`, Math.random() * 10);
}

console.log(hTable.storage);
console.log(hTable.countAll());

Separate Chaining 방식으로 구현하였다.

 

---

https://velog.io/@760kry/JS-hash-table-javascript-hash-table-%EA%B5%AC%ED%98%84-45k5i3f0gw

[data structure] hash table / javascript hash table 구현

https://bcho.tistory.com/1072

Hashtable의 이해와 구현 #1

http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html

Linear Probing Hash Tables

https://ktko.tistory.com/entry/HashTable-Java%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

자바로 HashTable 구현하기

https://github.com/iamdap91/basic-data-structure

iamdap91/basic-data-structure

http://jeonghwan-kim.github.io/2016/07/19/babel.html

불러오는 중입니다...