負載因子和重新哈希

負載因子衡量雜湊表的填充程度。如果超過載入因子，則增加雜湊表大小並將條目重新載入到新的更大的雜湊表中。這稱為重新哈希。負載因子 l (lambda) 衡量雜湊表的填充程度。是
數量的比例 元素與雜湊表的大小，即 l = n / N，其中 n 表示元素的數量，N 表示雜湊表中位置的數量。

請注意，如果雜湊表為空，則 l 為零。對於開放尋址方案，l 介於 0 和 1 之間；如果雜湊表已滿，則 l 為 1。對於單獨的連結方案，l 可以是任何值。

隨著 l 的增加，碰撞的機率也會增加。研究表明，對於開放尋址方案，您應將負載因子保持在 0.5 以下，對於單獨連結方案，應將負載因子維持在 0.9 以下。

將負載因子保持在一定閾值以下對於雜湊的效能非常重要。在 Java API 中 java.util.HashMap 類別的實作中，使用閾值 0.75。每當負載因子超過閾值時，您就需要增加哈希表的大小，並將映射中的所有條目重新哈希到一個新的更大的哈希表中。請注意，您需要更改雜湊函數，因為哈希表大小已更改。為了減少重新散列的可能性，因為它的成本很高，您應該至少將散列表大小增加一倍。即使定期重新散列，散列也是映射的有效實作。

以上是負載因子和重新哈希的詳細內容。更多資訊請關注PHP中文網其他相關文章！