HashMap<K, V>是每個Java程序中快速，通用且無處不在的數據結構。 首先是一些基礎知識。 您可能知道，它使用鍵的hashCode()和equals()方法在存儲桶之間拆分值。 存儲桶（箱）的數量應略高于映射中的條目數，以便每個存儲桶僅保留很少（最好是一個）值。 當按鍵查找時，我們很快確定了存儲桶（使用hashCode()模數number_of_buckets模），并且我們的商品在固定時間可用。

這應該已經為您所了解。 您可能還知道，哈希沖突對HashMap性能具有災難性的影響。 當多個hashCode()值最終出現在同一存儲桶中時，這些值將放置在臨時鏈接列表中。 在最壞的情況下，當所有鍵都映射到同一存儲桶時，會將哈希映射退化為鏈表–從O（1）到O（n）查找時間。 讓我們首先對HashMap在Java 7（1.7.0_40）和Java 8（1.8.0-b132）中的正常情況下的行為進行基準測試。 為了完全控制hashCode()行為，我們定義了自定義Key類：

class Key implements Comparable<Key> {private final int value;Key(int value) {this.value = value;}@Overridepublic int compareTo(Key o) {return Integer.compare(this.value, o.value);}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass())return false;Key key = (Key) o;return value == key.value;}@Overridepublic int hashCode() {return value;} }

Key類行為良好：它覆蓋equals()并提供了體面的hashCode() 。 為了避免過多的GC，我緩存了不可變的Key實例，而不是一遍又一遍地創建它們：

public class Keys {public static final int MAX_KEY = 10_000_000;private static final Key[] KEYS_CACHE = new Key[MAX_KEY];static {for (int i = 0; i < MAX_KEY; ++i) {KEYS_CACHE[i] = new Key(i);}}public static Key of(int value) {return KEYS_CACHE[value];}}

現在我們準備進行一些實驗。 我們的基準測試將使用連續鍵空間簡單地創建不同大小（10的冪，從1到1百萬）的HashMap 。 在基準測試本身中，我們將根據鍵查找值并測量所需的時間，具體取決于HashMap大小：

import com.google.caliper.Param; import com.google.caliper.Runner; import com.google.caliper.SimpleBenchmark;public class MapBenchmark extends SimpleBenchmark {private HashMap<Key, Integer> map;@Paramprivate int mapSize;@Overrideprotected void setUp() throws Exception {map = new HashMap<>(mapSize);for (int i = 0; i < mapSize; ++i) {map.put(Keys.of(i), i);}}public void timeMapGet(int reps) {for (int i = 0; i < reps; i++) {map.get(Keys.of(i % mapSize));}}}

結果確認HashMap.get()確實是O（1）：

有趣的是，在簡單的HashMap.get() Java 8平均比Java 7快20％。 整體性能同樣令人感興趣：即使在HashMap有100萬個條目，一次查找所用的時間也不到10納秒，這意味著我的機器上大約有20個CPU周期^* 。 令人印象深刻！ 但這不是我們要進行基準測試的結果。

假設我們有一個非常差的映射鍵，它總是返回相同的值。 這是最糟糕的情況，完全HashMap使用HashMap ：

class Key implements Comparable<Key> {//...@Overridepublic int hashCode() {return 0;} }

我使用了完全相同的基準來查看它在各種地圖尺寸下的行為（注意這是對數對數比例）：

預計Java 7的結果。 HashMap.get()的成本與HashMap本身的大小成比例地增長。 由于所有條目都在一個巨大的鏈接列表中的同一存儲桶中，因此查找一個條目平均需要遍歷該列表的一半（大小為n）。 因此，O（n）復雜度如圖所示。

但是Java 8的性能要好得多！ 這是一個對數標度，因此我們實際上在談論幾個數量級的更好。 在災難性哈希沖突的情況下，在JDK 8上執行的相同基準會產生O（logn）最壞情況的性能，如將JDK 8單獨以對數線性比例可視化，則可以更好地看到：

即使使用big-O表示法，如此巨大的性能改進背后的原因是什么？ 好，在JEP-180中描述了此優化。 基本上，當存儲桶過大時（當前： TREEIFY_THRESHOLD = 8 ）， HashMap用樹形圖的臨時實現動態替換它。 這樣一來，我們不必感到悲觀的O（n），而獲得更好的O（logn）。 它是如何工作的？ 好吧，以前具有沖突鍵的條目只是簡單地附加到鏈表中，而后又需要遍歷。 現在， HashMap使用哈希碼作為分支變量，將列表提升為二叉樹。 如果兩個散列不同，但最終在同一個存儲桶中，則認為一個散列較大并向右移動。 如果哈希值相等（如本例所示），則HashMap希望鍵是Comparable ，以便它可以建立一些順序。 這不是HashMap密鑰的要求，但顯然是一種好習慣。 如果密鑰不具有可比性，那么在發生大量哈希沖突的情況下，不要指望任何性能提高。

為什么所有這些都那么重要？ 知道我們使用的哈希算法的惡意軟件可能會處理數千個請求，這些請求將導致大量的哈希沖突。 重復訪問此類密鑰將嚴重影響服務器性能，從而有效地導致拒絕服務攻擊。 在JDK 8中，從O（n）到O（logn）的驚人跳躍將阻止這種攻擊媒介，也使性能更具預測性。 我希望這將最終說服您的老板升級。

---

^*在Intel Core i7-3635QM @ 2.4 GHz，8 GiB RAM和SSD驅動器上執行的基準，在64位Windows 8.1和默認JVM設置上運行。

翻譯自: https://www.javacodegeeks.com/2014/04/hashmap-performance-improvements-in-java-8.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Java 8中的HashMap性能改进的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。