爲什麼hashmap查找是O（1）即恆定時間？

如果我們從Java的角度來看，那麼我們可以說hashmap查找需要一定的時間。但是內部實現呢？它仍然需要搜索特定的存儲桶（針對哪個密鑰的哈希碼匹配）以尋找不同的匹配鍵。那麼爲什麼我們說hashmap查找需要一定的時間？請解釋。爲什麼hashmap查找是O（1）即恆定時間？

來源

2013-03-18 genonymous

可能的重複[可以哈希表真的是O（1）]（http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1） – Boann 2014-10-03 17:51:34

在使用散列函數的適當假設下，我們可以說散列表查找需要的時間爲 O（1）。這意味着的平均值爲，哈希表執行查找所做的工作量至多是一些常量。直觀地說，如果你有一個「好的」散列函數，你會期望元素會在整個散列表中或多或少地均勻分佈，這意味着每個存儲桶中元素的數量將接近元素的數量除以桶的數量。如果哈希表的實現保持這個數字很低（比如說，每次元素與桶的比率超過某個常量時增加更多的桶），那麼完成的預期工作量就會成爲一些基線工作量來選擇哪個桶應該被掃描，然後做「不要太多」的工作來看看那裏的元素，因爲在期望的情況下，那個桶中只有恆定數量的元素。

這並不意味着哈希表有保證 O（1）的行爲。實際上，在最糟糕的情況下，散列方案將會退化，所有元素都將在一個桶中結束，在最壞的情況下查找需要時間Θ（n）。這就是爲什麼設計好的散列函數很重要。

有關更多信息，您可能需要閱讀算法教科書以查看哈希表爲何如此有效地支持查找的正式推導。這通常包含在算法和數據結構的典型大學課程的一部分中，並且在線有許多優秀的資源。

希望這有助於！

來源

2013-03-18 04:37:03 templatetypedef

感謝您的簡單和明確的答案。它整齊地回答我的問題。 – genonymous 2013-03-18 06:02:24

您的答案正確無誤以獲取該值。但是桶位置呢？我們知道每個關鍵字（假設哈希函數太好，會爲每個關鍵字生成不同的哈希值），將創建一個定位存儲區的表，即鏈表（直到java 7）。我的問題是，如果1000K桶中有1000K不同的鍵值，hashmap如何確保它能夠爲o（1）甚至查找桶位置？希望我清楚的問題。謝謝。 – Sam 2015-11-20 05:48:03

@Sam存儲桶通常以數組的形式存儲（或者是一個原始數組或者一些像ArrayList一樣的包裝器，它支持高效的隨機訪問）。這樣，在計算了散列函數之後，可以在時間O（1）（獨立於桶的數量） – templatetypedef 2017-03-15 17:21:51

的關鍵是在文檔這樣的說法：

如果很多映射關係將被存放在一個HashMap實例，具有足夠大的容量創建它將使映射不是讓更有效地存儲它根據需要執行自動重新散列以增長表格。

和

加載因子是哈希表是如何充分允許獲得之前它的容量自動增加的措施。當哈希表中的條目數量超過負載因子和當前容量的乘積時，散列表就會被重新映射（即重建內部數據結構），以便散列表大約是存儲桶數量的兩倍。如果超過客座率

http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html

內部桶結構實際上將被重建，允許攤餘成本的得到和把是O（1）。

注意，如果內部結構重建時，引入了性能損失很可能是O（N），因此相當多的得到和把可以接近澳攤銷費用之前，需要（1）。因此，請適當規劃初始容量和負載率，以免浪費空間，也不會引發內部結構的可避免重建。

來源

2013-03-18 04:37:14

用於超級鏈接並適當突出顯示的文本 – genonymous 2013-03-18 06:03:33

要跟進templatetypedef的意見，以及：

恆定的時間實現一個哈希表可能是一個HashMap，通過它可以實現表示在水桶中是否存在特定元素的布爾數組列表。但是，如果你正在爲你的hashmap實現一個鏈表，最糟糕的情況是你需要瀏覽每個bucket並且必須遍歷列表的末尾。

來源

2016-11-16 20:54:19

爲什麼hashmap查找是O（1）即恆定時間？

回答

相關問題