如何表現了100萬個Hashtable和100項哈希表

Question

我知道有可與哈希表中的性能問題之間有所不同，但怎麼能100萬項的哈希表可以更快然後用100項的哈希表？

Answer 1

這取決於使用的哈希算法的效率。

如果在小地圖多次碰撞並沒有在較大的一個，然後較大的一個會更快。

閱讀HashMap的javadoc瞭解初始容量和負載因子，並閱讀有關的散列碼（與Object.hashCode()開始）。 （Hashtable是一個古老的遺蹟，don't use it。）

Answer 2

這一切都取決於碰撞的次數：如果哈希表中沒有100萬個物品的碰撞，它將比100個物品和100個物品碰撞。

如果沒有碰撞查找將O（1）只使用哈希鍵和模數（見完美hash）。在衝突的情況下（假設哈希表數組和鏈表鏈碰撞），你必須通過所有這些順序走，直到找到問題的項目，其中有100％的碰撞率最壞的情況（想定的散列函數即）將是O（n）。