JavaScriptハッシュとは何ですか-jsチュートリアル-php.cn

JavaScript では、ハッシュはハッシュテーブルを指します。ハッシュテーブルは、データ要素の格納場所とデータのキーワードを介して、キーワードに基づいてメモリの格納場所に直接アクセスするデータ構造です。要素と要素の間には一定の対応関係が成立し、この対応関係を成立させる関数をハッシュ関数と呼びます。

JavaScriptハッシュとは何ですか

このチュートリアルの動作環境: Windows7 システム、JavaScript バージョン 1.8.5、Dell G3 コンピューター。

JavaScript ハッシュの基本概念:

ハッシュテーブル (ハッシュテーブル) は、メモリの格納場所に直接アクセスするデータの一種です。キーワードハッシュテーブルによって、データ要素の格納場所とデータ要素のキーとの間に一定の対応関係が確立され、この対応関係を確立する関数をハッシュ関数と呼びます。
JavaScriptハッシュとは何ですか
ハッシュテーブル構築方法:

格納するデータ要素数をn個とし、長さm(m>n)の連続格納単位を設定し、各データ要素のキーワード Ki (0

数学的な観点から見ると、ハッシュ関数は実際にはキーワードをメモリ単位にマッピングしたものであるため、ハッシュ関数を使用して、ハッシュ関数によって計算された華西アドレスを、一連のメモリユニットへのバックマッピングでは、ハッシュ関数を構築する際に 3 つの重要なポイントがあります: (1) ハッシュテーブルの挿入と検索の効率を向上させるために、演算プロセスは可能な限り単純かつ効率的である必要があります。 (2) ハッシュ関数は、ハッシュ衝突の可能性を減らすために適切なハッシュタイプを持つ必要があります。第三に、メモリを節約するためにハッシュ関数の圧縮率を高める必要があります。

一般的に使用される方法:

直接アドレス方法: キーワードの特定の線形関数値をハッシュアドレスとして使用します。これは hash(K)=aK C; と表現できます。利点は、競合が発生しないことです。欠点は、空間の複雑さが高くなる可能性があることであり、要素が少ない場合に適しています。
剰余除算法: データ要素のキーワードを一定の定数で除算し、その剰余をハッシュアドレスとする方法で、計算が簡単で応用範囲が広く、よく使われるハッシュ関数です。
hash(K=K mod C; この方法の鍵となるのは、定数の選択です。一般的な要件は、定数がハッシュテーブル自体の長さに近いか、それと等しいことです。理論によれば、定数は素数を選択するときに最も効果的であることが示されています
数値分析方法: この方法は、データ要素キーワード内のいくつかの均一な数値をハッシュアドレスとして取得する方法です。これにより、競合を可能な限り回避できますが、この方法はすべてのキーワードにのみ適しています。既知の状況は、より一般的なハッシュテーブルを設計したい人には当てはまりません。
二乗和法: 現在の文字列を Unicode 値に変換し、二乗を求めます。この値の 2 乗を計算します値の中央の桁数は、現在の数値のハッシュ値です。特定の数値は、現在のハッシュテーブルのサイズによって異なります。
分割された合計方法:現在のハッシュテーブルの桁数に従って、値をいくつかのセグメントに分割し、セグメントを追加し、最上位ビットを破棄した結果がこの値のハッシュ値になります。ハッシュ競合の解決策:

構造内ハッシュテーブルを使用する場合、問題があります: 2 つの異なるキーワードについて、ハッシュ関数を使用してハッシュアドレスを計算すると、同じハッシュアドレスが得られます。これをこれと呼びます。

##ハッシュ競合は主に 2 つの要因に関連しています JavaScriptハッシュとは何ですか
(1) 充填係数、充填係数とは、ハッシュの競合が存在するものを指します。ハッシュテーブルに格納されているハッシュアドレス空間のサイズに対する入力データ要素数の比 a=n/m; aが小さいほど競合の可能性は小さくなり、逆に競合の可能性はハッシュの競合とストレージスペースの使用率を考慮するため、a は通常 0.6 ～ 0.9 の間で制御されますが、a が小さいほどスペースの使用率が向上します。 .net は a. の最大値を 0.72 と直接定義しています (Microsoft の公式 MSDN では、HashTable のデフォルトの充填係数は 1.0 であると記載されていますが、実際には 0.72 の倍数です)

(2) 使用されるハッシュ関数に関係しますハッシュ関数が適切であれば、ハッシュ関数を作成することができますハッシュアドレスはハッシュアドレス空間内で可能な限り均等に分散され、それによって競合の発生が減少しますが、適切なハッシュ関数の取得は多くの実践に大きく依存します.

1) オープンアドレッシング方法

Hi=(H(key) di) MOD m i=1,2,…k(k Where H( key) はハッシュ関数、m はハッシュテーブルの長さ、di は増分シーケンスです。インクリメンタルシーケンスは 3 つあります。

①線形検出とハッシュ化: di=1,2,3,…,m-1

②二次検出とハッシュ化: di=1

2,- 1
2,2
2,-2
2,…±k^2(k ③擬似乱数検出とハッシュ化: di=擬似乱数列^欠点:

現象が確認できます。テーブル内の位置 i、i 1、および i 2 にレコードがすでに入力されている場合、ハッシュアドレス i、i 1、i 2、および i 3 を持つ次のレコードが入力されます。 in. i の位置 3. 競合を処理するプロセス中に、最初のハッシュアドレスが異なる 2 つのレコードが後続の同じハッシュアドレスをめぐって競合するこの現象は、「二次集約」と呼ばれます。つまり、同義語の競合を処理するプロセスで追加されました。非同義の競合。しかしその一方で、線形検出を使用してから競合を処理するためにハッシュを使用すると、ハッシュテーブルがいっぱいでない限り、競合しないアドレス Hk を常に見つけることができることが保証されます。二次検出と再ハッシュは、ハッシュテーブルの長さ m が 4j 3 (j は整数) の形式の素数である場合にのみ可能です。つまり、オープンアドレッシング方法では二次集約が発生し、検索に悪影響を及ぼします。

JavaScriptハッシュとは何ですか
2) リハッシュ方法

Hi = RHi (key)、i=1,2,…k RHi はすべて異なるハッシュ関数です。つまり、同義語の場合アドレスの競合が発生すると、競合が発生しなくなるまで別のハッシュ関数アドレスが計算されます。この方法では集計が行われにくくなりますが、計算時間が長くなります。

欠点: 計算時間が増加します。

3) チェーンアドレス方式（ジッパー方式）

キーワードが同義語であるすべてのレコードを同じ線形連結リストに格納します。

利点:

①ジッパー方式は競合の処理が簡単で、蓄積現象がありません。つまり、非同義語が競合することがないため、平均検索長が短くなります。
②ジッパー方式は各リンクリスト上のノード空間が動的に適用されるため、テーブルを作成する前にテーブルの長さを決定できない状況に適しています;
③ 競合を減らすために、オープンアドレッシング方式は充填率 α は小さくする必要があるため、ノードサイズが大きくなると、多くのスペースが無駄になります。ジッパー方式では α ≥ 1 が許容され、ノードが大きい場合はジッパー方式で追加されたポインタ領域を無視できるため、スペースを節約できます;
④ ジッパー方式で構築されたハッシュテーブルでは、演算実装が簡単。リンクされたリスト上の対応するノードを削除するだけです。オープンアドレス方式で構築されたハッシュテーブルの場合、ノードを削除しても単に削除したノードの空間を空のままにすることはできず、そうでないとハッシュテーブルに埋め込まれたシノニムノードの検索パスが切り捨てられてしまいます。これは、さまざまなオープンアドレス方法において、空のアドレス単位 (つまり、オープンアドレス) が検索失敗の条件となるためです。したがって、オープンアドレス方式を使用して競合を処理するハッシュテーブルに対して削除操作を実行する場合、削除されたノードに削除のマークを付けることしかできず、実際にノードを削除することはできません。

欠点:

ジッパー方式の欠点は、ポインタに追加のスペースが必要になることです。したがって、ノードサイズが小さい場合は、オープンアドレッシング方式の方がスペースを節約できます。ポインタ空間が使用されます。ハッシュテーブルのサイズを大きくすると、フィルファクタが小さくなり、オープンアドレッシング方法での競合が減少し、平均検索速度が向上します。

JavaScriptハッシュとは何ですか

#4) 公開オーバーフロー領域の確立

ハッシュ関数の値の範囲を [0,m-1] とすると、次に、ベクトル HashTable[0...m-1] を基本テーブルとし、各コンポーネントにレコードを格納し、ベクトル OverTable[0...v] をオーバーフローテーブルとして設定します。ハッシュ関数によって取得されたハッシュアドレスに関係なく、キーワードが基本テーブルのキーワードと同義であるすべてのレコードは、競合が発生した場合にオーバーフローテーブルに書き込まれます。

競合処理を行わない単純なハッシュ関数のハッシュテーブル実装

class Hash {
  constructor() {
    this.table = new Array(1024);
  }
  hash(data) {
    //就将字符串中的每个字符的ASCLL码值相加起来，再对数组的长度取余
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    console.log("Hash Value: " + data + " -> " + total);
    return total % this.table.length;
  }
  insert(key, val) {
    var pos = this.hash(key);
    this.table[pos] = val;
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

ログイン後にコピー

JavaScriptハッシュとは何ですか
ハッシュ関数を構築するために正方形の中央メソッドを使用し、線形検出メソッドにオープンアドレスメソッドを使用します。競合を解決するために。

class Hash {
  constructor() {
    this.table = new Array(1000);
  }
  hash(data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    //把字符串转化为字符用来求和之后进行平方运算
    var s = total * total + ""
    //保留中间2位
    var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1
    console.log("Hash Value: " + data + " -> " + index);
    return index;
  }
  solveClash(index, value) {
    var table = this.table
    //进行线性开放地址法解决冲突
    for (var i = 0; index + i < 1000; i++) {
      if (table[index + i] == null) {
        table[index + i] = value;
        break;
      }
    }
  }
  insert(key, val) {
    var index = this.hash(key);
    //把取中当做哈希表中索引
    if (this.table[index] == null) {
      this.table[index] = val;
    } else {
      this.solveClash(index, val);
    }
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

ログイン後にコピー

JavaScriptハッシュとは何ですか