動態調整數據結構

Question

爲什麼我們只根據負載因子動態調整哈希表大小？ 如果我們選擇在均勻分佈哈希策略中檢測到碰撞時選擇以幾何形式增加表格大小，那麼是否存在任何可能的影響。

Answer 1

假設哈希函數是好的，負載因子大概是碰撞的概率，所以這兩個想法並不相距太遠。

使用負載因子是因爲它容易計算，而且它在實際的碰撞中不是統計上有噪聲的。

另一個原因是遍歷表中所有元素的代價。仍然需要檢查一個空桶，因此加載因子中的括號也是列舉所有存儲元素時性能最差的方括號。

當使用它們調整工作臺尺寸時，碰撞模式中的自然噪聲是一個問題。我們絕不希望完全遵循您提出的政策。即使在25％的負載率下，我們也會以概率1 /（4G）等方式增長（比如說G> 1）每個插入表的概率爲1/4，然後再如何決定何時收縮桌子？當然不是每次都沒有碰撞！

所以事實上，我們必須在「窗口」中計算衝突與插入的比較，並在比率超過高閾值和低閾值時進行調整。該窗口必須相當大才能以良好的概率過濾出噪聲。這需要存儲和計算開銷來維護。這可能是不值得的，至少對於大多數時間使用的小桌子來說。

儘管如此，在諸如數據庫中表格很大並且有很多操作的設置中，實際統計信息用於優化性能。我不確定散列表大小是否包含在實際軟件中的優化中，但這是可能的。我可以想象的最可能的原因是不願接受散列函數失敗的小風險。