ハッシュ表

ハッシュテーブルは、(Key,Value)でデータを格納するデータ構造の1つである.
その利点は、資料検索においてO(1)の時間的複雑さを有することである.

配列効率の低下

おなじみの配列を思い出してみましょう.
配列内で必要な値を検索する手順は、次のとおりです.

// 배열 내 3이라는 값을 찾고 싶다면?
const arr = [1,2,3,4,5]

for(let i = 0; i < arr.length; i++) {
    if(arr[i] === 3) {
        return arr[i];	// 3
    }
}

必要な値を検索する時間は、配列のサイズと同じです.=>O(N)の時間的複雑さを持つ.

ハッシュ・リストのコア、ハッシュ

ハッシュ・テーブルを実装するには、해싱を使用する必要があります.
ハッシュとは何かを直接実現し、理解しましょう.

A = 1
B = 2
C = 3
D = 4
E = 5
...

上記のコードによると、ACEは135です.
「ACE」=>「BED」キーとvalueが欲しい場合は、
上記のコードに従って、ACEは数字135に変換され、空の配列の135番目のインデックスに「BED」値が格納される.

const arr = [...X134, "BED" ];

このように、文字を数字に変換してインデックスにするのがハッシュです.
配列内でBEDという値を再び見つけたい場合は、ACEに再ハッシュされた135を入力します.

arr[135] === "BED"

このように,ハッシュテーブルは配列の大きさに関係なくO(1)の時間的複雑さを有する.

小さく並べても大丈夫

余海興に問題がある.
まず、ACEは135でハッシュされた.準備された配列は10格子しかないかもしれないからだ.
しかし、無条件に大きなサイズの配列を用意することはできません.
すなわち,我々の目標は,任意の文字列を準備した配列サイズよりも小さい数字にすることである.
よく使われる方法は以下の通りです.

let storage = [];
storage.length = 10;
function hash (key) {
        let hash = 0;

        if (typeof key === "number") {
            key += "";
        } else {
            [...key].forEach((e) => {
                hash += e.charCodeAt(0);
            });
        }
        return hash % storage.length;	// 해싱된 숫자를 배열의 크기로 나눈 나머지를 구했다.
    }

に入力された文字列を1文字ずつ数字に変換します.

で変更された数字を加算しました.

を足した数字を並べた大きさで分け、残りは返します.

配列サイズに等しい残りの部分をインデックスとして使用しているため、インデックスが配列サイズより大きい場合は絶対に発生しません.

競合の解決

上記のハッシュでは、配列に次の値が格納されているとします.

storage = [["ACE","Bed"],["SIDIZ","chair"],["IKEA","desk"],...]

しかし、別のハッシュ結果が0の値を格納する必要がある場合は、どうすればいいのでしょうか.
(storageの大きさは10なので、10で割った場合、残りの数は0の数が本当に多いのが一般的です.)
ここにはいろいろな解決策があり、配列内部を配列に分割する方法を選びました.

storage = [[["ACE","Bed"],["AEC","Angry"]],["SIDIZ","chair"],["IKEA","desk"],...]

storage[0]の[0]は[ACE]、[Bed]、[storage[0]の[1]は[AEC]、[Angry]を格納します.
このように、同じハッシュ値(0)が現れても、storage[0]でpushを継続することができる.
上記の方法は,ハッシュ関数が異なる値を最大限に抽出できるように設計してこそ効果的である.
なぜなら、どの文字列のハッシュ結果も0の場合、ハッシュ・テーブルは通常の配列と完全に同じになります.

ハッシュ表の実装

class HashTable {

    constructor(size) {
        this.storage = [];
        this.size = size;
    }


    hash = function (key) {
        let hash = 0;

        if (typeof key === "number") {
            key += "";
        } else {
            [...key].forEach((e) => {
                hash += e.charCodeAt(0);
            });
        }
        return hash % this.size;
    }

    insert = function (key, value) {
        const index = this.hash(key);

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

    search = function (key) {
        const index = this.hash(key);
        let value;

        this.storage[index].forEach(function(e) {
            if(e[0] === key) return value = e[1];
        });
        return value;
    }

    delete = function (key) {
        const index = this.hash(key);

        for(let i = 0; i < this.storage[index].length; i++){
            if(this.storage[index][i][0] === key) {
                this.storage[index].splice(i,1);
            }
        }
    }
}

データの挿入、検索、削除が可能なハッシュテーブルデータ構造を実現した.

ハッシュテーブルで解くアルゴリズム問題

https://velog.io/@goody/PR-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98

REFERENCE

誰もが独自のデータ構造とアルゴリズムを持っています(ジェイウィンガー)
https://mangkyu.tistory.com/102
https://medium.com/@clgh0331/javascript-node-js-hash-table%EC%9D%84-%EA%B5%AC%ED%98%84-f1442b24571c