Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参考文献「Cracking thecoding Interview」by Gayle Laakmann McDowell
辞書、ハッシュ マップ、ハッシュ テーブルについて聞いたことがあるかどうかにかかわらず、それらはすべて本質的に同じです。このブログでは、わかりやすくするために、このデータ構造をハッシュ テーブルとして参照します。
ハッシュテーブルとは何かを定義することから始めましょう。ハッシュ テーブルは、非常に効率的な検索を行うために、キーと値のペアの形式でキーを値にマッピングするデータ構造です。実装するには複数の方法があります。
リンクリストの配列とハッシュ関数を使用して、ハッシュテーブルを実装できます。ハッシュ関数とは何かをさらに詳しく見てみましょう。
ハッシュ関数とは何ですか? ハッシュ関数は、ハッシュ テーブルの重要なコンポーネントです。これは、入力 (または「キー」) を受け取り、固定サイズのバイト文字列を通常は整数の形式で返す、通常は関数の形式のアルゴリズムです。出力はハッシュ コード、または単にハッシュと呼ばれます。
ハッシュ テーブルのコンテキストにおけるハッシュ関数の主な目的は、ハッシュ コードをバケット/スロットの配列の有効なインデックスにマッピングし、そこから目的の値を見つけることです。この場合、これらのバケット/スロットはリンクされたリストになります。優れたハッシュ関数の特徴:
チェーンとして知られる一般的な手法です。このアプローチにはいくつかの利点があります:
ハッシュ コード(通常は int または long) を計算します。キーの数は無限で、整数の数は有限である可能性があるため、2 つの異なるキーが同じハッシュ コードを持つ可能性があります。
モジュラス演算子を使用することです。 (例: hash(key) % array.length))。このメソッドを使用すると、2 つの異なるハッシュ コードが同じインデックスにマッピングされる可能性があります。
かかります O(1).
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:
The heart of any hash table is its hash function. A good hash function should:
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
Two primary methods for handling collisions are:
Chaining: Each table position stores a linked list of collided items. Simple to implement but can lead to slower lookups if chains become long.
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.
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).
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:
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; } }
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 サイトの他の関連記事を参照してください。