帶有內存限制的系統的散列表

我已經閱讀了散列表的各種變體，但我不清楚哪一個更適合系統內存不足（我們有內存限制限制）。
線性/二次探測適用於稀疏表格。
我認爲在這方面Double hash與Quadratic相同。
外部鏈接沒有羣集問題。
我查過的大多數教科書似乎都假設一個額外的空間將始終可用，但實際上在我看到的大多數示例實現中，因爲哈希表從未減半，因此佔用的空間比真正需要的要多得多。
那麼當我們想要最大限度地利用內存時，哈希表的哪個變體是最有效的？帶有內存限制的系統的散列表

更新：
所以我的問題不僅是關於桶的大小。我的理解是，桶的大小和負載下的性能是重要的。因爲如果桶的大小很小，但表格在50％的負載下會降低，那麼這意味着我們需要經常調整大小。

來源

2015-05-28 Jim

你有沒有考慮一個哈希表以外的數據結構？ –

@MarkRanson：可以使用什麼其他數據結構在恆定時間內進行搜索？ – Jim

我沒有意識到。然而，哈希表不一定會給你恆定的時間，因爲它會降低。你沒有回過頭來給我們一個大局，所以沒有辦法知道備選方案可能如何。 –

請參閱this variant的Cukoo Hashing。

這將需要更多的散列函數，但它是有道理的 - 您需要爲節省內存支付一些東西。

來源

2015-05-28 18:55:31

這是更有效的方式嗎？它確保在高數據負載下有良好的性能嗎？ – Jim

我相信鏈接解釋它。我的答案試圖解決你的問題的具體問題，而不是關於這個主題的教程。 –

但是你在談論表中桶的大小。如果表格調整大小，那麼優勢在哪裏？我的問題是，如果你的建議解決了這兩個問題。如果它調整了50％的負載，那麼我不確定我是否看到與其他變體的區別 – Jim

帶有內存限制的系統的散列表

回答

相關問題