首頁猿問 HashMap獲取/放置復(fù)雜性

HashMap獲取/放置復(fù)雜性

Java 算法與數(shù)據(jù)結(jié)構(gòu)

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

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

查看完整描述

3 回答

有只小跳蛙

TA貢獻(xiàn)1824條經(jīng)驗獲得超8個贊

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

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

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

是的，如果你沒有足夠的內(nèi)存做散列表，你就會有麻煩.但不管你用什么數(shù)據(jù)結(jié)構(gòu)，這都是真的。

反對回復(fù) 2019-07-05

猛跑小豬

TA貢獻(xiàn)1858條經(jīng)驗獲得超8個贊

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

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

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

反對回復(fù) 2019-07-05