使用鏈接列表數組實現哈希表

這個問題一直困擾着我很長一段時間，今天我讀了一篇與哈希表相關的詳細文章。沒有檢查任何實現示例我想從頭開始寫一個哈希表。使用鏈接列表數組實現哈希表

單獨鏈接方法給了我實現散列表的想法。任何有數據結構經驗的人都可能把這個問題當作笑話，但我是一個初學者，並且沒有直接跳過我想討論我的實現效率的代碼。它會是有效的還是其他任何基本的想法都可能比這個更受歡迎？

2012-04-18 Ali

單獨的鏈接效果很好如果你有一個好的散列算法，那麼將會有很少的碰撞，每個鏈都很小。 – twain249 2012-04-18 20:07:27

所以線性探測會更好或不會產生太大的差別？ – Ali 2012-04-18 20:08:25

這兩種方法都存在權衡。在最壞的情況下，單獨的鏈接變成一個'LinkedList'，線性探測需要重新計算哈希，直到你檢查每個單元並且它們都是'O（n）'。「HashTable」是否實現的真正關鍵是所用的散列算法（以及結構的大小），因爲它決定了會出現多少次衝突。 – twain249 2012-04-18 20:13:08

我認爲，對於初學者，您還可以查看boost庫中實現的一些哈希映射的源（或文檔）。它被稱爲unordered_map。 (link is here)

只要你不知道這些實現，並且想要使用散列並且因爲它不在STL中而感到惱火，那麼你很有興趣編寫自己的快速數據存儲。
但是現在實現哈希映射是如此之多以至於C++ 11在它的STL中有unordered_map。你會看到有很多更有趣的東西。

注意：單獨的鏈接被稱爲bucket hash。實際上，boost使用桶散列，請參閱this link。也許你可以看看一些性能比較。那些做perf的人可能會寫出足夠好的實現。

來源

2012-11-23 00:51:57

使用閉合尋址，另一種選擇是使用自平衡二叉搜索樹，例如，紅黑樹/ std :: map或heap樹，用於內部數據結構，或甚至具有不同哈希算法的另一個哈希映射。

使用open addressing，線性探測的另一種替代方法是二次探測和double hashing;也有不常用的策略，如杜鵑散列，跳房子散列等。

實現散列表的關鍵是選擇正確的散列算法，調整策略（加載因子）和衝突解決策略。最佳策略高度依賴於您期望的工作負載類型，因爲每種方法都存在權衡。

來源

2012-11-23 01:33:11

使用鏈接列表數組實現哈希表

回答

相關問題