Java - HashMap.get（）調用的代價是多少？

HashMap.get（）調用的代價是多少？有問題的地圖包含數百個映射，我正在調用每秒60-1200次之間的任何地方的.get（）。Java - HashMap.get（）調用的代價是多少？

2013-07-27 Terra

所以......嘗試一下，看看它是否符合你的需求。請參閱：過早優化。具體而言，如果不知道密鑰是什麼，以及它如何散列，這個問題就不會被回答。這就是說...除非你使用自己的類作爲具有*可怕*哈希函數的密鑰，否則這實際上是一個微不足道的請求，每個請求都將無法接近1ms。 –

HashMap.get（）是O（1）。它的原始性能取決於密鑰的hashCode（）和equals（）方法對合理密鑰的工作方式，但每秒1200次，完全不成問題。衡量它。 –

問題的關鍵是實際上是一個字符串 - 我假設他們有非常有效的hashCodes（）方法。 – Terra

HashMap.get()平均爲O(1)，這意味着它是相當有效的。這個效率可能會略微下降，這取決於HashMap中元素的數量，但仍然應該非常高效。

如果你想取得良好的業績，你要注意其正確地實現你的鑰匙的hashCode方法，使物體被整個地圖的水桶均勻分佈。

這與HashMap的工作原理有關 - 簡單一點。

Java中的每個對象都有一個hashCode()和equals()方法。當你給HashMap賦值時，它會計算它所屬的bucket。這是根據傳遞給put(key,value)方法的key完成的。 HashMap使用密鑰的hashCode()方法返回的值。如果你只有鍵返回不同的哈希碼（如果你有無數個桶），HashMap可以精確地告訴哪個鍵+值對存在於哪個桶中，但事實並非如此。

可能有多個鍵返回相同的哈希碼（導致將它們放在同一個桶中），因此，當HashMap找到正確的桶時，使用多個元素時，它將迭代所有鍵並使用equals()查找一個，這是要求。鬥中的元素越少，檢查速度越快。

因此hashCode()實現越好，越少碰撞，性能越好。當然，你放入HashMap的元素越多，發生碰撞的可能性就越大。

來源

2013-07-27 21:39:14 lpiepiora

它依賴於保存在hashMap中的對象的hashCode函數。 – shevchyk

「效率可能會略有下降，這取決於元素的數量」。我會爭辯。請解釋你的意思是 – shevchyk

...以及有問題的桶數。如果桶的數量遠小於元素的數量，那麼HashMap的典型實現會偶爾重新調整大小以重新獲得效率，並且該（罕見）操作的成本相當高。通過將預期大小傳遞給HashMap構造函數，可以避免該操作並使其運行時非常接近'O（1）'。 –

它取決於你有多少次碰撞（碰撞可以將其效率從O（1）推到O（N））以及你的hash-set/map/table包含的任何對象的hashCode（）方法的實現。

你應該寫一個簡單的基準來測試它是否需要太長時間。 Denial of Service with String hashCode()

long start = System.currentTimeMillis() 

...Process hashmap gets here 

long time = System.currentTimeMillis()-start; 
System.out.println("Took "+time+"ms");

來源

2013-07-27 21:38:23

它取決於地圖中元素的數量及其散列碼分佈。如果哈希碼是均勻分佈的，則獲取元素的複雜度爲O（1）。

在一個相當現代化的機器上，數百個HashMap中的元素不應該是一個大問題，如果只有少數散列碼衝突，它應該是毫秒（或更少）的問題。只需確定即可。

來源

2013-07-27 21:38:54 MRalwasser

Like most hash table implementations，HashSet的工作在不斷時間（O（1））添加，刪除和包含操作假設你的對象有一個乖巧的散列函數。這意味着不管散列集的大小如何，它都需要大致相同的時間。

出於上述目的，「良好行爲」的散列函數總是在給定相同輸入對象的恆定時間內計算相同散列函數，並針對不同對象計算不同散列值（減少「散列衝突「）。

粗略地說，哈希映射通過非常快速地計算哈希碼來工作，並且只檢查包含相關元素的哈希桶。因爲計算哈希代碼應該是恆定的時間（並且在實踐中非常快），並且訪問一個桶應該是恆定的時間（並且在實踐中非常快），HashMap是在那裏最高效的地圖實現之一。

來源

2013-07-27 21:43:43

Java - HashMap.get（）調用的代價是多少？

回答

相關問題