假設理解大O表示法。 JavaScript 中有範例。資料參考 Gayle Laakmann McDowell 的《破解編碼面試》
無論你聽過字典、雜湊圖或雜湊表，它們本質上都是一樣的。在本部落格中，為了簡單起見，我們將將此資料結構引用為雜湊表。
我們先來定義什麼是雜湊表。雜湊表是一種資料結構，它以鍵值對的形式將鍵映射到值，以實現高效查找。有多種方法可以實現它。
使用鍊錶數組和雜湊函數我們可以實作一個雜湊表。讓我們更深入地了解什麼是哈希函數。
雜湊函數是雜湊表的重要組成部分。它是一種演算法，通常採用函數的形式，接受輸入（或“鍵”）並傳回固定大小的位元組字串（通常採用整數的形式）。輸出稱為雜湊碼或簡稱雜湊。
散列函數的主要目的是將散列碼對應到桶/槽數組的有效索引，從中可以找到所需的值。在我們的例子中，這些桶子/槽將是連結列表。
好的雜湊函數的特徵：
在雜湊表實作中使用鍊錶數組是一種常見技術，稱為chaining。這種方法有幾個優點：
在此範例中，鍵 1 和 2 雜湊到索引 0，而鍵 4、5 和 6 全部雜湊到索引 2。
現在我們已經很好地理解了哈希函數以及為什麼要使用鍊式存儲，讓我們來看看將鍵值對插入哈希表的流程：
插入鍵（任何值）時，我們先計算鍵的雜湊碼（通常是int或long）。兩個不同的鍵可能具有相同的雜湊碼，因為可能有無限的鍵和有限的整數。
將雜湊碼對應到陣列中的索引。將雜湊碼對應到陣列的常用方法是使用模運算子。 （例如，hash(key) % array.length)）。使用此方法，兩個不同的雜湊碼可能會對應到同一個索引。
在索引處，有一個鍵和值的鍊錶。將鍵值對儲存在此索引處。當鍵具有相同的雜湊碼或雜湊碼映射到相同的索引時，就會發生衝突。
在雜湊表實作中存取鍵值對非常有效率。只需根據鍵計算雜湊碼，然後根據雜湊碼計算索引，最後在鍊錶中搜尋具有該鍵的值即可。
假設實現良好，存取鍵值對（插入和刪除也是如此），需要
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中文網其他相關文章！
