ハッシュ テーブル : 衝突、サイズ変更、ハッシュ

WBOY
リリース: 2024-08-17 08:50:02
オリジナル
541 人が閲覧しました

Hash Tables : Collisions, Resizing, Hashing

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参考文献「Cracking thecoding Interview」by Gayle Laakmann McDowell

ハッシュテーブルを理解する

辞書、ハッシュ マップ、ハッシュ テーブルについて聞いたことがあるかどうかにかかわらず、それらはすべて本質的に同じです。このブログでは、わかりやすくするために、このデータ構造をハッシュ テーブルとして参照します。

ハッシュテーブルとは何かを定義することから始めましょう。ハッシュ テーブルは、非常に効率的な検索を行うために、キーと値のペアの形式でキーを値にマッピングするデータ構造です。実装するには複数の方法があります。


ハッシュ テーブルの主要なコンポーネント

リンクリストの配列ハッシュ関数を使用して、ハッシュテーブルを実装できます。ハッシュ関数とは何かをさらに詳しく見てみましょう。

ハッシュ関数とは何ですか?

ハッシュ関数は、ハッシュ テーブルの重要なコンポーネントです。これは、入力 (または「キー」) を受け取り、固定サイズのバイト文字列を通常は整数の形式で返す、通常は関数の形式のアルゴリズムです。出力は

ハッシュ コード、または単にハッシュと呼ばれます。

ハッシュ テーブルのコンテキストにおけるハッシュ関数の主な目的は、ハッシュ コードをバケット/スロットの配列の有効なインデックスにマッピングし、そこから目的の値を見つけることです。この場合、これらのバケット/スロットはリンクされたリストになります。

優れたハッシュ関数の特徴:

  • 決定的: 特定の入力に対して、常に同じハッシュ出力を生成する必要があります。
  • 均一分布: 予想される入力を出力範囲全体で可能な限り均等にマッピングする必要があります。
  • 効率的: 計算が速いはずです。
  • 雪崩効果: 入力の小さな変更により、ハッシュ出力が大幅に異なります。
リンクされたリストの配列を使用する理由

ハッシュ テーブルの実装におけるリンク リストの配列の使用は、

チェーンとして知られる一般的な手法です。このアプローチにはいくつかの利点があります:

  1. 衝突処理: リンク リストの配列を使用する主な理由は、衝突を効率的に処理するためです。 2 つのキーをハッシュして同じインデックスにマッピングする場合、新しいキーと値のペアをそのインデックスのリンク リストに追加するだけです。
  2. スペース効率: ハッシュ テーブルに、基になる配列のサイズよりも多くの項目を格納できるようになります。各配列スロットは、リンクされたリストを通じて複数の項目を保持できます。
  3. リーリー
この例では、キー 1 と 2 はインデックス 0 にハッシュされ、キー 4、5、および 6 はすべてインデックス 2 にハッシュされます。


キーと値のペアの挿入

ハッシュ関数とチェーンを使用する理由をよく理解したところで、キーと値のペアをハッシュ テーブルに挿入するフローを見てみましょう:

  1. キー (任意の値) を挿入するときは、まずキーの

    ハッシュ コード(通常は int または long) を計算します。キーの数は無限で、整数の数は有限である可能性があるため、2 つの異なるキーが同じハッシュ コードを持つ可能性があります。

  2. ハッシュ コードを配列内のインデックスにマッピングします。ハッシュ コードを配列にマッピングする一般的な方法は、

    モジュラス演算子を使用することです。 (例: hash(key) % array.length))。このメソッドを使用すると、2 つの異なるハッシュ コードが同じインデックスにマッピングされる可能性があります。

  3. インデックスには、キーと値のリンクされたリストがあります。キーと値のペアをこのインデックスに保存します。キーに同じハッシュ コードがある場合、またはハッシュ コードが同じインデックスにマップされている場合、衝突が発生します。

キーと値のペアへのアクセス

ハッシュ テーブルの実装では、キーと値のペアへのアクセスが非常に効率的になります。単純にキーからハッシュ コードを計算し、次にハッシュ コードからインデックスを計算し、最後にこのキーを持つ値のリンク リストを検索します。

適切な実装を想定すると、キーと値のペアにアクセスするには (挿入と削除も)、

かかります O ( 1 ) O(1) O(1).


What Makes a Hash Table Implementation "Good"?

A well-implemented hash table should balance efficiency, space utilization, and collision handling. Here are the key factors that contribute to a good hash table implementation:

A Good Hash Function

The heart of any hash table is its hash function. A good hash function should:

  • Be quick to compute
  • Minimize collisions

Optimal Load Factor

Theload factoris the ratio of filled slots to total slots in the hash table. Maintaining an appropriate load factor is crucial:

A typicalsweet spotis between 0.6 and 0.75

  • Too low (< 0.5): Wastes space
  • Too high (> 0.8): Increases collision risk

Collision Resolution Techniques

Two primary methods for handling collisions are:

  1. Chaining: Each table position stores a linked list of collided items. Simple to implement but can lead to slower lookups if chains become long.

  2. Open Addressing: If a collision occurs, look for the next available slot. Keeps all data in the table but requires careful implementation to avoid clustering of stored data.

Note that chaining and open-addressing cannot coexist easily. Logically, it would not make sense to look for the next available slot but store collided items at a specific index.

Dynamic Resizing

As the number of elements grows, the hash table should resize to maintain performance:

Typically, the table size is doubled when the load factor exceeds a threshold. All elements need to be rehashed into the new, larger table.

This operation is expensive but infrequent, keeping the amortized time complexity at O(1).


JavaScript Implementation

This implementation will utilize resizing and chaining for collision resolution. We will assume that our keys are integers.

For the hash function + mapping, we will keep it very simple and simply perform the following given a key:

k e y % a r r a y c a p a c i t y key \hspace{0.2cm} \% \hspace{0.2cm} array \hspace{0.1cm} capacity key%arraycapacity

Classical OOP

class HashNode { constructor(key, value) { this.key = key; this.value = value; this.next = null; } } class HashTable { constructor(capacity = 16) { this.capacity = capacity; this.size = 0; this.buckets = new Array(this.capacity).fill(null); this.threshold = 0.75; } hash(key) { return key % this.capacity; } insert(key, value) { const index = this.hash(key); if (!this.buckets[index]) { this.buckets[index] = new HashNode(key, value); this.size++; } else { let currentNode = this.buckets[index]; while (currentNode.next) { if (currentNode.key === key) { currentNode.value = value; return; } currentNode = currentNode.next; } if (currentNode.key === key) { currentNode.value = value; } else { currentNode.next = new HashNode(key, value); this.size++; } } if (this.size / this.capacity >= this.threshold) { this.resize(); } } get(key) { const index = this.hash(key); let currentNode = this.buckets[index]; while (currentNode) { if (currentNode.key === key) { return currentNode.value; } currentNode = currentNode.next; } return undefined; } remove(key) { const index = this.hash(key); if (!this.buckets[index]) { return false; } if (this.buckets[index].key === key) { this.buckets[index] = this.buckets[index].next; this.size--; return true; } let currentNode = this.buckets[index]; while (currentNode.next) { if (currentNode.next.key === key) { currentNode.next = currentNode.next.next; this.size--; return true; } currentNode = currentNode.next; } return false; } resize() { const newCapacity = this.capacity * 2; const newBuckets = new Array(newCapacity).fill(null); this.buckets.forEach(head => { while (head) { const newIndex = head.key % newCapacity; const next = head.next; head.next = newBuckets[newIndex]; newBuckets[newIndex] = head; head = next; } }); this.buckets = newBuckets; this.capacity = newCapacity; } getSize() { return this.size; } getCapacity() { return this.capacity; } }
ログイン後にコピー

Functional OOP

function createHashTable(initialCapacity = 16) { let capacity = initialCapacity; let size = 0; let buckets = new Array(capacity).fill(null); const threshold = 0.75; function hash(key) { return key % capacity; } function resize() { const newCapacity = capacity * 2; const newBuckets = new Array(newCapacity).fill(null); buckets.forEach(function(head) { while (head) { const newIndex = head.key % newCapacity; const next = head.next; head.next = newBuckets[newIndex]; newBuckets[newIndex] = head; head = next; } }); buckets = newBuckets; capacity = newCapacity; } return { insert: function(key, value) { const index = hash(key); const newNode = { key, value, next: null }; if (!buckets[index]) { buckets[index] = newNode; size++; } else { let currentNode = buckets[index]; while (currentNode.next) { if (currentNode.key === key) { currentNode.value = value; return; } currentNode = currentNode.next; } if (currentNode.key === key) { currentNode.value = value; } else { currentNode.next = newNode; size++; } } if (size / capacity >= threshold) { resize(); } }, get: function(key) { const index = hash(key); let currentNode = buckets[index]; while (currentNode) { if (currentNode.key === key) { return currentNode.value; } currentNode = currentNode.next; } return undefined; }, remove: function(key) { const index = hash(key); if (!buckets[index]) { return false; } if (buckets[index].key === key) { buckets[index] = buckets[index].next; size--; return true; } let currentNode = buckets[index]; while (currentNode.next) { if (currentNode.next.key === key) { currentNode.next = currentNode.next.next; size--; return true; } currentNode = currentNode.next; } return false; }, getSize: function() { return size; }, getCapacity: function() { return capacity; } }; }
ログイン後にコピー

以上がハッシュ テーブル : 衝突、サイズ変更、ハッシュの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:dev.to
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!