帶有〜100萬個鍵的HashMap，仍然是恆定時間？

是的。要搜索一個哈希表擁有100萬個項目添加到它，你這樣做：

1）計算，你要尋找的對象的哈希。
2）發現，桶
3）搜索通過桶的項目。

（1）是獨立於哈希映射或數在它的項目的大小。（2）是O（1），假設標準哈希映射實現爲鏈表的數組。
（3）需要與桶中物品數量相關的時間量，該時間量應該近似（散列加入的物品數量）/（桶數量）。這部分將從O（1）開始，但隨着項目數量開始大大超過桶的數量，緩慢增加。

對於幾乎任何目的，哈希地圖也算是對插入和取出O（1），即使有非常大的數據集，只要你以一個足夠大的數桶。

2009-12-23 16:04:32

+1好答案，點（3）很重要 – Paolo 2009-12-23 16:10:21

並且假設散列是均勻分佈的爲您的數據集。 – 2009-12-23 16:19:23

有沒有辦法增加C++中桶的數量，以便每個桶只有1個元素？ – SuperString 2009-12-23 22:30:53

是的，還是固定的時間（攤銷）。

2009-12-23 15:53:41 yfeldblum

是什麼攤銷平均 – SuperString 2009-12-23 15:56:14

理論上...內存分頁可能是一個問題。不太可能，但可能。 – 2009-12-23 15:56:32

攤銷意味着某些單獨的插入可能需要比其他插入更長的時間，但平均時間保持不變。 – 2009-12-23 15:57:00

回答