它是O（1）哈希映射retreival？

Question

我有這樣一個HashMap：

Map<TestBean,String> 

其中TestBean是包含幾串一個POJO類，說str1，str2。兩個testBean這個對象obj1和obj2被說成是等於如果任

obj1.str1=obj2.str1 || obj1.str2==obj2.str1 

所以，當我從這個地圖檢索值，它仍然是一個O（1）檢索？

Answer 1

它應該是O(1)只要哈希碼實現合理均勻 - 在最壞的情況下（如果所有內容都被哈希到同一個桶中），它可能是O(N)。

麻煩的是，對於這個特定的例子，你恰恰是最糟糕的情況 - 給定你的任一或相等條件，我看不到一個明智的方式來實現合約，即相同的對象必須具有相同的散列碼其他而不是簡單地爲每個對象返回相同的代碼。

其實，我不認爲你甚至可以有一個明確的在這種情況下equals()，作爲你的條件既不是對稱的也不是傳遞

a1(str1 = "A", str2 = "B") 
a2(str1 = "B", str2 = "C") 
a3(str1 = "C", str2 = "D") 

• 不是對稱的：a1.equals(a2)但!a2.equals(a1)
• 不可傳遞：a1.equals(a2)和a2.equals(a3)，但!a1.equals(a3)。

Answer 2

攤銷時間複雜度爲O(1)。這個取決於hashcode函數的實現。如果碰撞很多，則會增加複雜性。

因此，基本上它是O(1)在最佳情況下，它會關閉O(n)，因爲您的hashcode產生更多的衝突。如果您的hashcode函數在所有情況下都會返回相同的數字，那麼您的地圖將變爲鏈接列表，因此您可以使用O(n)。