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

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

ハッシュ テーブル

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

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

• 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は、ハッシュ テーブルに表示される可能性のあるキーです。

• #ハッシュ関数は、セット 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 メソッドがあります

• キーに基づいて対応する値を見つけるための検索メソッドがあります

• 初期化

  #- ハッシュ テーブルにあるスロットの数を初期化します
- 配列を使用して M スロットを作成します

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

总结

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

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。

以上がJavaScript のハッシュ テーブル (ハッシュ テーブル) の詳細な紹介 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。