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