爲什麼哈希表佔用比其他數據結構更多的內存？

我一直在閱讀有關hash tables，字典等的所有文獻和視頻，我已經看到了哈希表具有空間/時間權衡屬性。爲什麼哈希表佔用比其他數據結構更多的內存？

我在努力理解爲什麼哈希表佔用比總數元素（值）數量相同的數組或列表更多的空間？它是否與實際存儲散列鍵有關？

據我所知，在基本術語中，一個哈希表需要一個關鍵標識符（比如某個字符串），通過一些哈希函數傳遞給數組或其他數據結構。除了在數組或表格中存儲對象（值）的顯而易見的內存使用外，爲什麼哈希表佔用更多空間？我覺得我失去了一些顯而易見的東西...

2014-03-19 rex

就像你說的，這都是關於查找時間和空間之間的折衷。基礎數據結構所具有的空間（桶）數量越大，散列函數所能存儲每個項目的位置數越多，因此碰撞的可能性（因此比常量性能更差）降低了。然而，更多的水桶顯然意味着需要更多的空間。項是被稱爲負載因子料斗數量的數量的比率，並且更詳細地在這一問題解釋：What is the significance of load factor in HashMap?

在minimal perfect hash function的情況下，就可以實現O（1）性能存儲n個桶中的n個項目（加載因子爲1）。

來源

2014-03-19 10:26:17 mtripp100

對不起，我認爲我有點厚，但在最糟的情況下（空間）說，每桶存儲1項。是不是有效像一個數組，因此與數組相同的大小，而不是更多？ – rex

是的，在理想的情況下，每個桶只能存儲1個項目，所以N個項目映射到N個桶。然而，在實踐中，這種情況幾乎從未如此，因爲隨着存儲桶數量的增加，任何明智的散列表實現都將「增長」底層數據結構，以包括更多存儲桶以最小化兩個項目散列到相同的可能性空間。如果空間比時間更重要，哈希表可能不是你想要的。 – mtripp100

但所有桶中的物品總數仍然是N，那麼爲什麼這會佔用比N個物品更多的空間？ – rex

爲什麼哈希表佔用比其他數據結構更多的內存？

回答

相關問題