Java hashmap真的是O（1）嗎？我已經(jīng)看到了一些關(guān)于SO re Java hashmaps及其O(1)查找時(shí)間的有趣聲明。有人可以解釋為什么會這樣嗎？除非這些哈希圖與我買的任何哈希算法有很大的不同，否則必須始終存在包含沖突的數(shù)據(jù)集。在這種情況下，查找將是O(n)而不是O(1)。有人可以解釋他們是否是 O（1），如果是，他們?nèi)绾螌?shí)現(xiàn)這一目標(biāo)？
3 回答
BIG陽
TA貢獻(xiàn)1859條經(jīng)驗(yàn) 獲得超6個(gè)贊
HashMap的一個(gè)特殊功能是，與平衡樹不同，它的行為是概率性的。在這些情況下，通常最有助于談?wù)撟顗那闆r事件發(fā)生概率的復(fù)雜性。對于哈希映射，當(dāng)然是關(guān)于地圖恰好是多么充分的碰撞的情況。碰撞很容易估計(jì)。
p collision = n / capacity
因此，即使是適度數(shù)量的元素的哈希映射也很可能經(jīng)歷至少一次沖突。Big O表示法允許我們做一些更引人注目的事情。觀察任何任意固定常數(shù)k。
O（n）= O（k * n）
我們可以使用此功能來提高哈希映射的性能。我們可以考慮最多2次碰撞的概率。
p collision x 2 =（n / capacity）2
這要低得多。由于處理一次額外碰撞的成本與Big O性能無關(guān)，我們已經(jīng)找到了一種在不實(shí)際更改算法的情況下提高性能的方法！我們可以將此概括為
p collision xk =（n / capacity）k
而現(xiàn)在我們可以忽略一些任意數(shù)量的碰撞，最終導(dǎo)致碰撞的可能性微乎其微。通過選擇正確的k，您可以將概率提高到任意微小的水平，所有這些都不會改變算法的實(shí)際實(shí)現(xiàn)。
我們通過說哈希映射具有高概率的 O（1）訪問來討論這個(gè)問題
繁星點(diǎn)點(diǎn)滴滴
TA貢獻(xiàn)1803條經(jīng)驗(yàn) 獲得超3個(gè)贊
您似乎將最壞情況行為與平均情況（預(yù)期）運(yùn)行時(shí)混淆。對于哈希表，前者確實(shí)是O（n）（即不使用完美的哈希），但這在實(shí)踐中很少有用。
任何可靠的哈希表實(shí)現(xiàn)，加上一半體面的哈希，在非常小的方差范圍內(nèi)，在預(yù)期的情況下具有非常小的因子（實(shí)際上是2）的O（1）的檢索性能。
至尊寶的傳說
TA貢獻(xiàn)1789條經(jīng)驗(yàn) 獲得超10個(gè)贊
在Java中，HashMap通過使用hashCode來定位存儲桶。每個(gè)存儲桶都是駐留在該存儲桶中的項(xiàng)目列表。掃描項(xiàng)目，使用等于進(jìn)行比較。添加項(xiàng)目時(shí)，一旦達(dá)到某個(gè)負(fù)載百分比，就會調(diào)整HashMap的大小。
因此，有時(shí)它必須與一些項(xiàng)目進(jìn)行比較，但通常它比O（n）更接近O（1）。出于實(shí)用目的，這就是您應(yīng)該知道的全部內(nèi)容。
添加回答
舉報(bào)
0/150
提交
取消