JavaScript のハッシュテーブル (ハッシュテーブル) の詳細な紹介 (コード例)-jsチュートリアル-php.cn

JavaScript のハッシュテーブル (ハッシュテーブル) の詳細な紹介 (コード例)

不言

リリース： 2019-01-02 09:37:53

転載

4418 人が閲覧しました

この記事では、JavaScript のハッシュテーブル (ハッシュテーブル) について詳しく説明します。必要な方は参考にしてください。

ハッシュテーブル

ハッシュテーブル (ハッシュテーブル、ハッシュテーブルとも呼ばれる) は、キー (Key) データ構造に基づいてメモリの格納場所に直接アクセスします。つまり、必要なクエリデータをテーブル内の場所にマップするキー値の関数を計算することによってレコードにアクセスし、検索を高速化します。このマッピング関数をハッシュ関数と呼び、レコードを格納する配列をハッシュテーブルと呼びます。

JavaScript のハッシュテーブル (ハッシュテーブル) の詳細な紹介 (コード例)

上の図から分析を開始します。

1000、10、1000 の集合 U があります。 152、9733、1555、997、1168
右側は 10 個のスロットのリスト (ハッシュテーブル) です。集合 U 内の整数をこのリストに格納する必要があります##。
#それをどのスロットに保管するか?この問題はハッシュ関数を使用して解決する必要があります。私の保存方法は、10 の余りを取得することです。この図を見てみましょう

1000 =0, 10 =0 すると、2 つの整数 1000 と 10 が保存されます。スロット番号が 0
152 =2 の場合、スロット 2
9733 =3 スロット番号 3## に格納されます。

#上記の簡単な例を通じて、次の点を一般的に理解できるはずです

#ハッシュ関数は、セット U 内のキーを変換する独自の設計方法です。値は、何らかの方法でハッシュテーブルに保存されます。計算 (例の残りなど)
#ハッシュテーブルには計算されたキーが格納されます

たとえば、キー 1000 と値 'Zhang San' を保存します ---> {key: 1000, value: 'Zhang San'} 上記の説明より、それは1000のスロットに格納されるべきですか？

キーを通じて値 Zhang San を見つけたい場合、キースロット内を検索するだけでよいでしょうか?この時点で、立ち止まって考えることができます。

ハッシュに関するいくつかの用語 (簡単に見てみましょう)

ハッシュテーブルに表示されるすべてのキーは完全セット U

##スロットの数を表すには M を使用します。
キーが与えられると、ハッシュ関数はそれがどのスロットに表示されるかを計算します。ハッシュ関数 h=k%上記の例 M では、ハッシュ関数 h はキー k からスロットへのマッピングです。
1000 と 10 は両方とも 0 番のスロットに格納されます。この状況は衝突と呼ばれます。
これを読んで、ハッシュ関数とは何かについて一般的に理解できたかどうかはわかりません。この例と考え方を通じて、記事の冒頭にあるハッシュテーブルの定義を遡って読むことができます。読めれば理解できると思います。

整数 h=>k%M の処理 (つまり、上記の例)

文字列の処理:

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

ログイン後にコピー

ハッシュアルゴリズムはここでは焦点ではありません、そして私はそれを深く勉強していません。ここで重要なことは、ハッシュテーブルがどのようなデータ構造であり、どのような利点があり、具体的には何をするのかを理解することです。

ハッシュ関数は、特定のアルゴリズムを通じてキーをリストにマッピングするだけです。

ハッシュテーブルの構築

上記の説明を踏まえて、ここで簡単なハッシュテーブルを作成していきます

ハッシュテーブルの構成

M スロット

ハッシュ関数があります
キー値をハッシュテーブルに追加する add メソッドがあります
削除するための delete メソッドがあります
キーに基づいて対応する値を見つけるための検索メソッドがあります
初期化
#- ハッシュテーブルにあるスロットの数を初期化します

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

ログイン後にコピー

ハッシュ関数

ハッシュ関数文字列の処理では、値を文字列に転送することもできるため、ここでは文字列が使用されます。

まず、より厳密にするために、渡されたキー値を文字列に変換します。 ##文字列は配列です (例: 'abc' => [...'abc'] => ['a','b','c']

charCodeAt を計算します。各キャラクターの残りを個別に取得する目的は、スロットの数に正確に対応することです。スロットは合計 10 個しかなく、あなたの値は必ず 0 ～ 9

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

ログイン後にコピー

## のスロットに収まります。 #Add

ハッシュ関数を呼び出します。対応するストレージアドレス (例のスロットです) を取得します。

スロットには複数の値が格納されている可能性があるため、それを表す必要があります。計算したスロット番号が 0 (slot[0]) であるなど、2 次元配列で表すと、後から来るスロットもスロット番号が [0] である場合は、スロット [0] に格納する必要があります。 0 の場合は、slot[0] [1]

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        this.slots[h].push(value);
    }

ログイン後にコピー

Delete

ハッシュアルゴリズムを通じてスロットを検索

フィルタリングを通じて削除

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }

ログイン後にコピー

## に保存する必要があります。 #Find

ハッシュアルゴリズムを通じて対応するスロットを検索します。

検索関数を使用して同じキーの値を検索します。

対応する値を返します

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

ログイン後にコピー

总结

讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。