首頁猿問 HashMap獲取/放置復雜性

HashMap獲取/放置復雜性

Java 算法與數據結構

慕妹3146593 2019-07-05 14:32:56

HashMap獲取/放置復雜性我們習慣這樣說HashMap get/put操作為O(1)。但是，它取決于哈希實現。默認對象哈希實際上是JVM堆中的內部地址。我們確定它足夠好聲稱get/put是O(1)嗎？可用內存是另一個問題。正如我從javadocs了解到的，HashMap load factor應該是0.75。如果JVM和load factor超過極限了？所以，看起來O(1)沒有得到保證。這有意義嗎還是我遺漏了什么？

查看完整描述

3 回答

有只小跳蛙

TA貢獻1824條經驗獲得超8個贊

這取決于許多事情。它是通常O(1)，有一個很好的散列，它本身就是固定時間.但是你可能會有一個需要很長時間才能計算出來的散列，和如果哈希映射中有多個返回相同哈希代碼的項，get將不得不對它們進行迭代調用equals在他們每個人身上找到一個匹配的。

在最壞的情況下，HashMap由于在同一個散列桶中遍歷所有條目(例如，如果它們都具有相同的哈希代碼)，因此具有O(N)查找。幸運的是，根據我的經驗，在現實生活中，這種最壞的情況并不經常出現。所以不，O(1)當然不能保證-但是當您考慮使用哪種算法和數據結構時，通常應該這樣做。

在JDK 8中，HashMap已經進行了調整，以便如果可以比較鍵來排序，那么任何人口稠密的桶都被實現為一棵樹，因此即使有大量具有相同哈希碼的條目，復雜度也是O(Logn)。當然，如果您有一個平等和順序不同的鍵類型，這可能會導致問題。

是的，如果你沒有足夠的內存做散列表，你就會有麻煩.但不管你用什么數據結構，這都是真的。

反對回復 2019-07-05

猛跑小豬

TA貢獻1858條經驗獲得超8個贊

我不確定默認的hashcode是地址-不久前我讀了OpenJDK的哈希代碼生成源代碼，我記得它有點復雜。也許，這還不能保證良好的發行。但是，這在某種程度上是沒有意義的，因為在hashmap中用作鍵的類很少使用默認的hashcode-它們提供自己的實現，這應該是很好的。

最重要的是，您可能不知道的是(同樣，這是基于讀取源代碼-不能保證)的是，HashMap在使用它之前先攪拌散列，將整個單詞的熵混合到底部位中，這是除了最大的hashmap之外，所有人都需要它的地方。這有助于處理那些自己不這么做的散列，盡管我想不出任何常見的情況。

最后，當表被重載時，它會退化為一組并行鏈表-性能變成O(N)。具體來說，通過鏈接的數量平均為負載系數的一半。

反對回復 2019-07-05

元芳怎么了

TA貢獻1798條經驗獲得超7個贊

已經有人提到，hashmap是O(n/m)平均而言，如果n是項目數和m是大小。也有人提到，原則上，整件事可能會變成一個單獨的鏈表。O(n)查詢時間。(這都假定計算哈希值是常數時間)。

然而，很少有人提到的是，至少有可能1-1/n(因此，對于1000件物品，這是99.9%的機會)最大的水桶將不會超過O(logn)！因此，匹配二進制搜索樹的平均復雜度。(常數是好的，更緊的界限是(log n)*(m/n) + O(1)).

這個理論界限所需要的就是使用一個相當好的散列函數(參見Wikipedia：通用散列..它可以很簡單a*x>>m)。當然，給你哈希值的人不知道你是如何選擇隨機常量的。

TL；DR：在極高的概率下，hashmap的最壞情況獲取/放置的復雜性是O(logn).

反對回復 2019-07-05

3 回答
0 關注
556 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

HashMap獲取/放置復雜性

HashMap獲取/放置復雜性

3 回答

添加回答