有沒有人知道這個問題的答案?帶有〜100萬個鍵的HashMap,仍然是恆定時間?
回答
是的。要搜索一個哈希表擁有100萬個項目添加到它,你這樣做:
1)計算,你要尋找的對象的哈希。
2)發現,桶
3)搜索通過桶的項目。
(1)是獨立於哈希映射或數在它的項目的大小。 (2)是O(1),假設標準哈希映射實現爲鏈表的數組。
(3)需要與桶中物品數量相關的時間量,該時間量應該近似(散列加入的物品數量)/(桶數量)。這部分將從O(1)開始,但隨着項目數量開始大大超過桶的數量,緩慢增加。
對於幾乎任何目的,哈希地圖也算是對插入和取出O(1),即使有非常大的數據集,只要你以一個足夠大的數桶。
是的,還是固定的時間(攤銷)。
是什麼攤銷平均 – SuperString 2009-12-23 15:56:14
理論上...內存分頁可能是一個問題。不太可能,但可能。 – 2009-12-23 15:56:32
攤銷意味着某些單獨的插入可能需要比其他插入更長的時間,但平均時間保持不變。 – 2009-12-23 15:57:00
- 1. 爲什麼hashmap查找是O(1)即恆定時間?
- 2. 四元數仍然有萬向鎖
- 3. 恆定時間是什麼意思?
- 4. HashMap的應該是未排序的,但仍然排序根據關鍵
- 5. 喬達LocalDate - 仍然是一個瞬間?
- 6. 100%精確的鍵,值的HashMap
- 7. 每個節點都有恆定時間的C++樹
- 8. 是否arr = [val] * N具有班輪或恆定時間?
- 9. 帶有視圖的Android選項卡,仍然是動態的
- 10. CAFilter仍然是一個私有API嗎?
- 11. asp.net的MVC LINQ的經歷100萬條記錄(proccess時間)
- 12. 是否仍然有效?
- 13. IOrderedQueryable.AsEnumerable()是否仍然有序?
- 14. Sharekit是否仍然有效?
- 15. jquery mobile 1.4,帶有data-inline =「true」的按鈕仍然是全寬
- 16. 帶有display:none的圖像是否仍然發出HTTP請求?
- 17. 所有時間即使在卸載時仍然有效服務
- 18. 值的恆定時間分組
- 19. 在C中的恆定日期時間#
- 20. 100%寬div仍然比應該
- 21. Uploadify卡住了100%,但仍然上傳
- 22. HoloEveryWhere仍然是一個謎
- 23. Java SQL 100萬行
- 24. JavaScript開關語句是線性還是恆定時間?
- 25. HashMap的第一個鍵是空的
- 26. iPhone模擬器的時間差是否仍然在設備上?
- 27. Facebook仍然返回時間戳格式
- 28. 線程仍然需要很長時間
- 29. 內存訪問不是恆定的時間
- 30. 帶鍵入條目的Scala HashMap
+1好答案,點(3)很重要 – Paolo 2009-12-23 16:10:21
並且假設散列是均勻分佈的爲您的數據集。 – 2009-12-23 16:19:23
有沒有辦法增加C++中桶的數量,以便每個桶只有1個元素? – SuperString 2009-12-23 22:30:53