JavaScript がハッシュ テーブルを実装する方法の詳細な紹介

この記事では、javascript に関する関連知識を提供します。主に、JavaScript がハッシュ テーブルを実装し、最終データが挿入される配列の構造全体をカプセル化する方法に関する関連問題を紹介します。はハッシュテーブルです。皆さんのお役に立てれば幸いです。

関連する推奨事項: JavaScript 学習チュートリアル

ハッシュ テーブルは通常、配列に基づいて実装されます。

1. 非常に高速な挿入、削除、検索操作を提供できます
2. データの量に関係なく、挿入と削除は一定に近い必要があります。時間: つまり、O(1) 時間レベルです。実際、それを行うには、いくつかの機械命令のみが必要です。
3. ハッシュ テーブルはツリーよりも高速で、基本的に目的の要素を即座に見つけることができます
4. ハッシュ テーブルはツリーよりもコーディングがはるかに簡単です

配列と比較したハッシュ テーブルのいくつかの欠点:

1. ハッシュ テーブル内のデータは順序が整っていないため、固定された方法で走査することができません。
通常、ハッシュ テーブル内のキーは繰り返すことができず、同じキーを配置することはできません。異なる要素を保存するために使用されます。
2. スペース使用率は高くなく、最下層uses は配列であり、一部のセルは使用されません

ハッシュ テーブルとは何ですか?

ハッシュ テーブルは、構造や原則をグラフィックの形式で表現できる配列、リンク リスト、ツリーとは異なり、理解するのが簡単ではありません。
• ハッシュ テーブルの構造は
• 配列 ですが、その魔法は 添え字値 の変換にあり、これを ハッシュ関数# と呼ぶことができます。 ##、HashCodeはハッシュ関数を通じて取得できます。

ハッシュ テーブルのいくつかの概念

ハッシュ:
• 変換 大きな数値 形成のプロセス 配列範囲内の添字 は ハッシュ と呼ばれます;
ハッシュ関数:
• 通常使用する Word は次のように変換されます。 bignumber、および hashing の bignumber のコード実装は、ハッシュ関数;## と呼ばれる関数に配置されます。 #ハッシュ テーブル:
最終データに挿入された
• 配列 の 構造 全体をカプセル化し、ハッシュ テーブル を取得します。 。
まだ解決する必要がある問題

:

ハッシュされた添字はまだ可能です

重複

、これを解決する方法どうしたの？この状況は
• 紛争 と呼ばれます。紛争は 必然 であり、我々が解決できるのは 競合 だけです。 競合を解決する方法

競合を解決する 2 つの一般的な解決策:

オプション 1:

チェーン アドレス方法

(
• zipper メソッド );下の図に示すように、各数値の
10

に対して剰余演算を実行し、残り

0~9 の範囲は配列の添字値として使用されます。さらに、配列内の各添字値に対応する位置には数値が格納されなくなり、剰余演算後の剰余が同じ数値で構成される array または linked list## が格納されます。 。

要約: チェーン アドレス方式による競合を解決する方法は、

各アレイ ユニットに格納されているデータ

が存在しないことです。長い 単一のデータ ですが、 チェーン 。このチェーンに一般的に使用されるデータ構造は、配列またはリンク リスト です。2 つのデータ構造の検索効率は次のとおりです。同等です (チェーンの要素は一般に多すぎないため)。 オプション 2: オープン アドレス メソッド

;

• オープン アドレス メソッドの主な作業方法は、空白セルを探す##です。
# 競合する

データ項目を配置します。

空白セルの位置を検出するさまざまな方法に応じて、次の 3 つの方法に分けることができます。

線形検出

• 二次検出
• リハッシュ法
• 負荷率が増加するにつれて、 、平均 検出長は直線的かつ緩やかに増加します。開発ではチェーン アドレス方式がよく使用され、たとえば Java の HashMap では チェーン アドレス方式 が使用されます。

優れたハッシュ関数

ハッシュ テーブルの利点はその速度であるため、ハッシュ関数は高いパフォーマンスを消費する複雑なアルゴリズムを使用できません。速度を向上させる 1 つの方法は、ハッシュ関数の 乗算と除算を最小限に抑えることです。

高パフォーマンスのハッシュ関数には、次の 2 つの利点がある必要があります:

• 快速的計算；
• #均勻的分佈;

快速計算

#霍納法則：在中國霍納法則也叫做

秦九韶演算法

，具體演算法為：

求多項式的值時，先計算最內層括號內一次多項式的數值，再由內向外逐層計算一次多項式的數值。這個演算法把求n次多項式f(x)的值就轉換成求n個一次多項式的值。

變換之前：

乘法次數：n（n 1）/2次；

加法次數：n次；變換之後：

乘法次數：n次；加法次數：n次；

如果使用大O表示時間複雜度的話，直接從變換前的O(N2)降到了O(N)

。

均勻分佈

為了確保資料在雜湊表中均勻分佈，當我們需要
使用常數的地方

，盡量使用###質數###；例如：哈希表的長度、N次方的底數等。 ######Java中的HashMap採用的是鏈結位址法，哈希化採用的是公式為：###index = HashCode（key）&（Length-1）#########即將資料化為二進位進行###與###運算，而不是取餘運算。這樣計算機直接運算二進位數據，效率更高。但是JavaScript在進行叫大數據的###與###運算時會出現問題，所以以下使用JavaScript實作哈希化時還是會採用取餘運算。 ###

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i  this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i  7 && this.count  0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i ############相關推薦：###javascript學習教學#########

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