ハッシュテーブルのJavaScript実装の詳細な説明
1. ハッシュテーブルの原理ハッシュ テーブルは非常に重要なデータ構造です。ほぼすべてのプログラミング言語は、このデータ構造を直接的または間接的に適用しています。通常は配列に基づいて実装されます。当時は、配列よりも多くの利点がありました。
ただし、ハッシュ テーブルには配列に比べていくつかの欠点もあります。
では、ハッシュ テーブルとは一体何でしょうか? その構造は配列ですが、その魔法は添え字値の変換にあります。これをハッシュ関数と呼び、これを通じて HashCode を取得できます。 次に、例を見てみましょう。 データ構造を使用して単語情報を保存します。たとえば、単語が 50,000 個あり、単語が見つかった後、各単語には独自の特定のアプリケーションなどがあります。どのように進めればよいでしょうか? おそらく、文字を適切な下付き文字に変換してみるとよいでしょう。しかし、文字を配列の添え字値に変換するにはどうすればよいでしょうか?単語を配列の添え字値に変換する方法はありますか?単語を配列の添え字に変換しておけば、将来的に特定の単語の情報を検索したい場合、添え字の値に応じて 1 ステップで目的の要素にアクセスできます。では、文字列を下付き文字の値に変換するにはどうすればよいでしょうか? 実際、単語の文字を数字で置き換えるコンピュータ コーディング スキーム (文字エンコード) は数多くあります。もちろん、a は 1、b は 2、c は 3 など、独自のコーディング システムを設計することもできます。しかし、コーディング システムができたので、単語を数字に変換するにはどうすればよいでしょうか。 ここでは 2 つのオプションがあります。 解決策1: 数字を追加する 単語を変換する簡単な方法は、単語の各文字のエンコードを合計することです。 たとえば、単語 cats は数値に変換されます: 3+1+20+19=43。その後、43 が単語 cats の添え字として配列に格納されます。 しかし、この解決策には明らかな問題があります。多くの単語が下付き文字 43 で終わってしまう可能性があるのです。 配列内のインデックス値の位置には 1 つのデータしか格納できないことはわかっています。後からデータを格納すると、必然的にデータの上書きが発生します。したがって、1 つのインデックスにこれほど多くの単語を格納するのは明らかに不合理です。 解決策2: 累乗 実際、私たちが通常使用する10より大きい数字は、乗算によって一意に表すことができます。たとえば、6543 = 6 *10³+5 *10²+4 *10 + 4 このスキームを使用して単語を表すこともできます。たとえば、cats = 3 * 27³+1 * 27² + 20 * 27+17 = 60337 この方法で取得された番号は基本的にその一意性を保証でき、他の単語と重複することはありません。 しかし、問題があります。単語がzzzzzzzzzzの場合、得られる数値は70000000000000を超えます。配列は、そのような大きな添え字値を表現できない可能性があります。たとえそのような大きな配列を作成できたとしても、実際には無効な単語が多くなり、意味がありません。 2 つのソリューションの概要: 最初のソリューション (数値を加算する) では配列インデックスが少なすぎ、2 番目のソリューション (27 の累乗を乗算して合計する) では配列インデックスが多すぎます。 したがって、べき乗方式システムで取得された巨大な整数範囲を許容可能な配列範囲に圧縮する圧縮方法が必要になります。簡単な方法は、ある数値を別の数値で割った後の余りを取得するために使用される剰余演算子を使用することです。 剰余演算の実装: (0～199 の数値) 0～199（大きい）の数字を0～9（小さい）の数字に圧縮するとします。 下付き文字の結果は、インデックス = 大 % 小 数が10で割り切れる場合、余りは0から9の間である必要があります 例えば、16%10 = 6、23%10 = 3 繰り返しは発生しますが、繰り返しの回数は明らかに少なくなります。たとえば、0 から 199 までの 5 つの数字を長さ 10 の配列に入れると、繰り返しは発生しますが、繰り返しの確率は非常に小さくなります。 2. ハッシュテーブルの概念ハッシュの原理を理解したので、いくつかの概念を見てみましょう。 ハッシュ: 配列範囲内で大きな数値を添え字に変換するプロセスをハッシュと呼びます。 ハッシュ関数: たとえば、単語を大きな数値に変換し、その大きな数値をハッシュするコードを関数に組み込む関数がハッシュ関数です。 ハッシュ テーブル: 最後に、この配列にデータが挿入され、構造全体のカプセル化はハッシュ テーブルと呼ばれることがあります。 3. ハッシュ競合問題前述のように、ハッシュされた下付き文字の値は繰り返される可能性があり、競合が発生します。たとえば、0 から 199 までの 5 つの数字を選択して長さ 10 のセルに入れ、33、45、27、86、92 をランダムに選択した場合、最終的な位置は 3-5-7-6-2 となり、競合は発生しません。しかし、86 と 66 もあったらどうなるでしょうか。ここで衝突が起こります。この問題を解決するにはどうすればいいでしょうか? 一般的な解決策は 2 つあります。 1. チェーンアドレス方式チェーン アドレス方式は、競合解決の一般的なソリューションです (ジッパー方式とも呼ばれます)。 次の図に示すように:
10 のメモリを持つ配列が作成されます。ここで、いくつかの数字を配列に格納する必要があります。これらの数字は、ハッシュ後に繰り返される場合があります。リンクされたリストまたは配列を介して同じ添え字値を持つ数字をリンクする方法は、チェーン アドレス方式と呼ばれます。値を検索する場合、まずその添字に従って対応するリンク リストまたは配列を検索し、その内部を検索します。 図から、チェーン アドレス方式が競合を解決する方法は、各配列ユニットが単一のデータではなくチェーンを格納することであり、このチェーンの一般的な構造は配列またはチェーンであることがわかります。では、特定のアプリケーションではどの方法を使用すればよいのでしょうか?実際、どちらの方法も受け入れられ、効率性は似ています。もちろん、実装によっては、新しく挿入されたデータが配列またはリンク リストの先頭に配置されます。この場合は、リンク リストを使用するのが最適です。配列の最初の位置にデータを挿入するには、他のすべての項目を戻す必要がありますが、リンク リストではこの問題は発生しません。 2. オープンアドレス方式オープン アドレス メソッドは、基本的に空白セルを探して重複データを追加することによって機能します。次の図に示すように:
32 という数字があり、それを配列に挿入したい場合、解決策は次のようになります。
しかし、この場所を探索する方法は 3 つあります。 1. 線形探索 つまり、空白セルの線形検索 挿入32
クエリ32
位置 32 の値が以前に挿入されていない場合は、値が存在するかどうかを判断するためにハッシュ テーブル全体を照会する必要がないことに注意してください。代わりに、空の位置が見つかった場合は停止します。 32 より前の空の位置をスキップして他の位置に移動することは不可能だからです。 線形検出にも問題があります。以前に挿入されたデータが連続して挿入されると、新しく挿入されたデータには長い検出距離が必要になります。 2. 二次探査 二次探索は線形探索に基づいて最適化されます。 線形検出は、たとえば、下付き文字の値 x から開始し、x+1、x+2、x+3 を順番に検出する、ステップ サイズが 1 の検出と見なすことができます。 2 回目の検出では、ステップ サイズを最適化します。たとえば、下付き値 x から始めて、x+1²、x+2²、x+3² を順番に検出します。 ただし、二次検出にはまだ問題があります。たとえば、32-112-82-42-52 を連続して挿入すると、1 つずつ累積するとステップ長は同じになります。この場合、異なるステップ長のクラスタリングが発生し、効率に影響します。この問題を解決するにはどうすればよいでしょうか。再ハッシュを見てみましょう。 3. 再考 再ハッシュ法は、別のハッシュ関数を使用してキーワードを再度ハッシュし、ハッシュ結果をステップ サイズとして使用する方法です。指定されたキーワードの場合、ステップ サイズは検出全体を通じて変更されず、異なるキーワードでは異なるステップ サイズが使用されます。 2 番目のハッシュには次の特性が必要です。 最初のハッシュ関数とは異なる 出力は 0 にできません (そうでない場合、ステップ長がなくなり、各挿入が同じ場所に配置され、アルゴリズムが無限ループに入ります) そして、コンピューターの専門家は、非常にうまく機能するハッシュ関数を設計しました。 ここで、定数は配列の容量よりも小さい素数であり、キーは最初のハッシュによって取得された値です。 たとえば、stepSize = 5-(key%5) は要件を満たし、結果は 0 にはなりません。 4. ハッシュ関数の実装ハッシュ テーブルの主な利点は、その速度です。速度を上げる 1 つの方法は、ハッシュ関数での乗算と除算をできるだけ少なくすることです。適切に設計されたハッシュ関数には、次の利点が必要です。 （１）高速計算 （２）均一分布 具体的に実装してみましょう: まず、実装したハッシュ関数の主な操作は、文字を比較的大きな数値に変換し、大きな数値を配列の範囲に圧縮することです。以下のように表示されます。
関数hashFunc(str,size){
//hashCode変数を定義します。var hashCode = 0;
//ホーナーのアルゴリズムに従って、hashCodeの値を計算します //まず文字列をデジタルコードに変換します for(var i =0;i<str.length;i++){
ハッシュコード = 37*ハッシュコード + str.charCodeAt(i)
}
//剰余演算 var index = hashCode % size;
インデックスを返します。
}
コードテスト:
console.log( hashFunc('abc',7));
console.log( hashFunc('cba',7));
console.log( hashFunc('nba',7));
console.log( hashFunc('rgt',7));
テスト結果は次のとおりです。
取得した文字列に対応する下付き文字の値は非常に均等に分布していることがわかります。 5. ハッシュテーブルのカプセル化ここでは、チェーン アドレス メソッドを使用してハッシュ テーブルを実装します。 3 つのプロパティが定義されています。
実装されたハッシュ テーブル (ストレージ配列に基づく) は、各インデックスの配列 (バケット) に対応し、バケットには (キーと値) が格納されます。最終的なハッシュ テーブルのデータ形式は次のようになります: [[[k,v],[k,v],[[k,v],[k,v]],[k,v]] 次の図に示すように:
コードは次のとおりです。
関数ハッシュテーブル(){
// プロパティを定義します this.storage = [];
カウント = 0;
制限 = 8;
}
先ほどプロトタイプを通じてカプセル化したハッシュ関数を追加します。
関数ハッシュテーブル(){
// プロパティを定義します this.storage = [];
カウント = 0;
制限 = 8;
HashTable.prototype.hashFunc = function(str,size){
//hashCode変数を定義します。var hashCode = 0;
//まず文字列をデジタルコードに変換します for(var i =0;i<str.length;i++){
ハッシュコード = 37*ハッシュコード + str.charCodeAt(i)
}
//剰余演算 var index = hashCode % size;
インデックスを返します。
}
}
6. ハッシュテーブル操作1. 挿入と変更操作ハッシュ テーブルの挿入操作と変更操作は同じ機能です。これは、ユーザーが <キー、値> を渡したときに、キーが存在しない場合は挿入操作になり、キーがすでに存在する場合は変更操作に対応するためです。 具体的な実装の考え方は、まず渡されたキー、つまり配列のインデックスに応じて対応するハッシュコードを取得し、次にハッシュテーブルのインデックス位置から別の配列（バケット）を取り出し、前のステップのバケットが空かどうかを確認します。空の場合は、この位置にこれまで何も配置されていないことを意味するため、新しい配列 [] が作成されます。次に、キーに対応する値が以前に配置されたかどうかを確認します。配置されていた場合は、新しいデータを挿入するのではなく、置換操作です。変更操作でない場合は、新しいデータを挿入し、データ項目に 1 を追加します。 実装コードは次のとおりです。
//挿入および変更操作 HashTable.prototype.put = function(key,value){
//キーに応じて対応するインデックスを取得します
var index = this.hashFunc(str,this.limit);
//インデックスに従って対応するバケットを取得します
var バケット = this.storage[インデックス];
//値が空の場合は、バケットに配列を割り当てます if(bucket === null){
バケット = [];
this.storage[インデックス] = バケット;
}
//データを変更するかどうかを判断する for(let i =0;i<bucket.length;i++){
var タプル = バケット[i];
if (タプル[0] === キー) {
タプル[1] = 値;
戻る;
}
}
//追加操作を実行します。bucket.push([key,value]);
カウント += 1;
}
テストコード:
ht.put('a',12)
ht.put('b',67)
ht.put('c',88)
ht.put('d',66)
コンソールにログ出力します。
印刷結果は次のとおりです。
テスト成功 2. 取得操作まず、キーに応じて対応するインデックスを取得し、次に対応するインデックスに応じて対応するバケットを取得し、バケットが空かどうかを判断します。空の場合は null を返します。それ以外の場合は、バケット内のキーが渡されたキーと等しいかどうかを線形検索します。等しい場合は、対応する値を直接返します。そうでない場合は、null を直接返します。 実装コードは次のとおりです。
HashTable.prototype.get = function(キー){
//キーに応じて対応するインデックスを取得します
var index = this.hashFunc(key,this.limit);
//インデックスに従って対応するバケットを取得します
var バケット = this.storage[インデックス];
//空かどうかを判断します if (bucket == null) {
null を返します。
}
//線形探索 for(let i = 0;i<bucket.length;i++){
var タプル = バケット[i];
if (タプル[0] === キー) {
タプル[1]を返す。
}
}
null を返します。
}
テストコード: たとえば、キーdを持つ要素の値を返す
console.log("ht.get('d'):"+ht.get('d'));
3. 削除操作このメソッドは、get 操作のメソッドに似ています。まず、キーに応じて対応するインデックスを取得し、次に対応するインデックスに応じて対応するバケットを取得し、バケットが空かどうかを判断します。空の場合は null を返します。それ以外の場合は、バケット内のキーが渡されたキーと等しいかどうかを線形検索します。等しい場合は削除します。それ以外の場合は、直接 null を返します。
HashTable.prototype.remove = function(キー){
//キーに応じて対応するインデックスを取得します
var index = this.hashFunc(key,this.limit);
//インデックスに従って対応するバケットを取得します
var バケット = this.storage[インデックス];
//空かどうかを判断します if (bucket == null) {
null を返します。
}
// splice() による線形検索と削除 for(let i =0;i<bucket.length;i++){
var タプル = バケット[i];
if (タプル[0] === キー) {
バケットをスプライスします(i,1);
カウント -= 1;
tuole[1]を返す;
}
}
null を返します。
}
テストコード: キーbの要素を削除する
console.log("ht.remove('b'):"+ht.remove('b'));
4.ハッシュテーブルが空かどうかを判定する
HashTable.prototype.isEmpty = function(){
this.count === 0 を返します。
}
コードテスト:
console.log("空ですか: "+ht.isEmpty());結果：
5. ハッシュテーブル内の要素数を取得する
ハッシュテーブル.プロトタイプ.サイズ = 関数(){
this.count を返します。
}
コードテスト:
console.log("ハッシュテーブル要素の数:"+ht.size());結果：
7. ハッシュテーブルの拡張1. ハッシュテーブル拡張のアイデア上記のコードのカプセル化では、すべてのデータ項目を長さ 5 の配列に配置します。チェーン アドレス方式を使用しているため、ハッシュ テーブル内の現在のデータ量と全体の長さの比率は 1 より大きくなる可能性があり、このハッシュ テーブルは新しいデータを無制限に挿入できます。しかし、データ量が増えると、各インデックスに対応するバケットがどんどん長くなり、効率も低下します。そのため、適切な状況で配列を拡張する必要があります。では、どのように容量を拡大すればよいのでしょうか?容量の拡張は単純に容量を2倍にすることで実現できますが、この場合、すべてのデータ項目を同時に変更する必要があります（ハッシュ関数を呼び出して別の場所を取得する）。どのような状況で容量を拡張できますか？現在のデータ量と全体の長さの比率が 0.75 より大きい場合にハッシュ テーブルを拡張できる場合が一般的です。 2. ハッシュテーブル拡張の実装実装のアイデア: まず、古い配列の内容を保存し、次にすべての属性をリセットし、保存された古い配列の内容を走査して、バケットが空かどうかを判断します。空の場合はスキップします。それ以外の場合は、データを取り出して再挿入します。実装コードは次のとおりです。
HashTable.prototype.resize = function(newLimit){
// 古い配列の内容を保存します var oldStorge = this.storage;
//すべてのプロパティをリセットします this.storage = [];
カウント = 0;
this.limit = 新しい制限;
//古い配列の内容を走査する for(var i =0;i<oldStorge.length;i++){
//対応するバケットを取り出す
var バケット = oldStorge[i];
//バケットが空かどうかを判断します if (bucket == null) {
続く;
}
//データを取り出して再挿入する for(var j =0;j<bucket.length;j++){
var タプル = バケット[j];
this.put(タプル[0],タプル[1]);
}
}
}
カプセル化が完了したら、データ項目が追加されるたびに容量を拡張するかどうかを判断し、必要に応じて拡張を実行します。コードは次のとおりです。
if(this.count > this.limit*0.75){
this.limit*2 をリサイズします。
}
したがって、対応する拡張容量と対応する削減容量があります。データ項目を削除すると、残っているデータ項目が小さい場合は、容量を削減できます。コードは次のとおりです。
if(this.limit > 5 && this.count < this.limit/2){
this.resize(Math.floor(this.limit/2))
}
8. 完全なコード
関数ハッシュテーブル(){
// プロパティを定義します this.storage = [];
カウント = 0;
制限 = 5;
HashTable.prototype.hashFunc = function(str,size){
//hashCode変数を定義します。var hashCode = 0;
//ホーナーのアルゴリズムに従って、hashCodeの値を計算します //まず文字列をデジタルコードに変換します for(var i =0;i<str.length;i++){
ハッシュコード = 37*ハッシュコード + str.charCodeAt(i)
}
//剰余演算 var index = hashCode % size;
インデックスを返します。
}
//挿入および変更操作 HashTable.prototype.put = function(key,value){
//キーに応じて対応するインデックスを取得します
var index = this.hashFunc(key,this.limit);
//インデックスに従って対応するバケットを取得します
var バケット = this.storage[インデックス];
//値が空の場合は、バケットに配列を割り当てます if(bucket == null){
バケット = [];
this.storage[インデックス] = バケット;
}
//データを変更するかどうかを判断する for(let i =0;i<bucket.length;i++){
var タプル = バケット[i];
if (タプル[0] === キー) {
タプル[1] = 値;
戻る;
}
}
//追加操作を実行します。bucket.push([key,value]);
カウント += 1;
//容量を拡張する if(this.count > this.limit*0.75){
this.limit*2 をリサイズします。
}
}
// 取得操作 HashTable.prototype.get = function(key){
//キーに応じて対応するインデックスを取得します
var index = this.hashFunc(key,this.limit);
//インデックスに従って対応するバケットを取得します
var バケット = this.storage[インデックス];
//空かどうかを判断します if (bucket == null) {
null を返します。
}
//線形探索 for(let i = 0;i<bucket.length;i++){
var タプル = バケット[i];
if (タプル[0] === キー) {
タプル[1]を返す。
}
}
null を返します。
}
//削除操作 HashTable.prototype.remove = function(key){
//キーに応じて対応するインデックスを取得します
var index = this.hashFunc(key,this.limit);
//インデックスに従って対応するバケットを取得します
var バケット = this.storage[インデックス];
//空かどうかを判断します if (bucket == null) {
null を返します。
}
// splice() による線形検索と削除 for(let i =0;i<bucket.length;i++){
var タプル = バケット[i];
if (タプル[0] === キー) {
バケットをスプライスします(i,1);
カウント -= 1;
タプル[1]を返す。
//容量を減らす if (this.limit > 5 && this.count < this.limit/2) {
this.resize(Math.floor(this.limit/2))
}
}
}
null を返します。
}
//展開 HashTable.prototype.resize = function(newLimit){
// 古い配列の内容を保存します var oldStorge = this.storage;
//すべてのプロパティをリセットします this.storage = [];
カウント = 0;
this.limit = 新しい制限;
//古い配列の内容を走査する for(var i =0;i<oldStorge.length;i++){
//対応するバケットを取り出す
var バケット = oldStorge[i];
//バケットが空かどうかを判断します if (bucket == null) {
続く;
}
//データを取り出して再挿入する for(var j =0;j<bucket.length;j++){
var タプル = バケット[j];
this.put(タプル[0],タプル[1]);
}
}
}
HashTable.prototype.isEmpty = function(){
this.count === 0 を返します。
}
ハッシュテーブル.プロトタイプ.サイズ = 関数(){
this.count を返します。
}
}
JavaScript ハッシュテーブル実装の詳細な説明については、これで終わりです。JavaScript ハッシュテーブルに関するより関連性の高いコンテンツについては、123WORDPRESS.COM の過去の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。 以下もご興味があるかもしれません:
|
<<: ウェブページの読み込み速度を上げる25の方法とヒント
>>: CSS における px、em、rem、pt の特徴、違い、変換について詳しく説明します。
推薦する
Prometheus を使用して、MySQL の自動増分主キーの残りの使用可能パーセンテージをカウントします。
最近、本番環境のデータベースがログデータを狂ったように書き込み、主キー値のオーバーフローを引き起こし...
JavaScript操作要素は、ページコンテンツのスタイルを変更する方法を教えます
目次1. 操作要素1.1. 要素コンテンツの変更1.2. innerText と innerHtml...
Docker、Nginx、Jenkins をベースにした自動フロントエンド デプロイメント
目次事前準備展開ターゲットDocker環境構築クラウドサーバーに接続Docker環境をインストールす...
MySQLデータベースインデックスの左端一致原則
目次1. 共同インデックスの説明2. ac はインデックスを使用できますか? 3. 考える4. 最左...
MySQLマスタースレーブデータベース構築方法の詳細な説明
この記事では、MySQL マスター/スレーブ データベースの構築方法について説明します。ご参考までに...
FTP、FTPS、SFTPの違いについて簡単に説明します
目次FTP、FTPS、SFTP の概要FTP FTPS FTPサーバーFTPソフトウェアのアクティブ...
MySQL トランザクション分離レベルと MVCC の詳細な説明
目次トランザクション分離レベル同時トランザクション実行中に発生した問題SQL標準の4つの分離レベルM...
Dockerでk8sをデプロイする方法
K8s k8s はクラスターです。クラスターには複数の名前空間があります。名前空間の下には複数のポッ...
JS における ES6 継承と ES5 継承の違い
目次継承ES5 プロトタイプ継承ES6 クラス継承両者の違いES5プロトタイプ継承の内部実装ES6 ...
効率をN倍に高めるVimクイックリファレンステーブル15個
昨年の前半から開発と娯楽のために Linux を使い始めましたが、今では Windows には戻れま...
TomcatをダウンロードしてLinuxにインストールする詳細な手順
Linux に触れたばかりの方には、この内容が役に立つかもしれません。Linux にしばらく触れてい...
CSSメディアクエリのアスペクト比を小さくする方法
CSS メディア クエリには非常に便利なアスペクト比、aspect-ratio があり、幅と高さを直...
Nginx サービスを使用してサブドメイン環境を構築し、2D マップの読み込みパフォーマンスを向上させる方法を説明します。
1. 背景最近、友人が大規模なマップの読み込みが遅いという問題に遭遇しました。iServer のパ...
Docker共通コマンドの詳しい解説 Study03
目次1. ヘルプコマンド2. ミラーコマンド3. コンテナコマンド1. ヘルプコマンド1. 現在のD...
CSS3でアニメーションを実装する3つの方法
これは、面接者の CSS に関する基本的な知識をテストするものです。 CSSでアニメーションを実装す...