適用於X個元素的HashMap？

Question

對於散列圖適合的元素範圍是多少？

我明白一切都是常量時間，導致將是一個大的內存消耗唯一的問題，但我很想知道是什麼程度的太多了？

Answer 1

任何數量範圍內。

唯一的問題肯定不是內存消耗。內存消耗在元素數量上通常是線性的，這並不是特別糟糕。

如果有大量的散列衝突（元素散列爲相同的值），這將是一個重大的問題，因爲你不得不尋找與該散列值的所有元素來找到正確的一個。存儲具有相同散列值的元素（稱爲「單獨鏈接」）的流行方法是使用鏈接列表，並且在鏈接列表中搜索速度慢。

無論是否哈希表將執行以及取決於：

• 散列元素的分佈（這會影響散列衝突的數目），這是依賴於實際的元件和散列函數
• 哈希表（多少元素在哈希表中相對於它的大小）的負載因數。如果這太高，即使分配得當，也會有大量的散列衝突。