性能測試網站（詳解關於hashmap的一些性能測試）

目錄0.前言1.準備工作。1.1模擬哈希沖突1.2 java的基準測試。2.測試初始化長度3.模擬一百萬個元素put，get的差異。4.模擬無紅黑樹情況下get效率4.1 將random擴大，哈希沖突嚴重性大大減小，模擬大多數哈希沖突導致的哈希鏈長度均小於8，無法擴展為紅黑樹，隻能遍歷數組。4.1.1 ArrayList不同長度下get效率的基準測試4.2 jdk1.8版本，哈希沖突嚴重下的get效率測試4.3 將jdk版本降為1.7，在哈希沖突依然嚴重的情況下，get效率如何？5.總結0.前言本文主要討論哈希沖突下的一些性能測試。為什麼要寫這篇文章，不是為瞭KPI不是為瞭水字數。hashmap是廣大JAVA程序員最為耳熟能詳，使用最廣泛的集合框架。它是大廠面試必問，著名八股經必備。在小公司呢？這些年也面過不少人，對於3，5年以上的程序員，問到hashmap也僅限於要求知道底層是數組+鏈表，知道怎麼放進去，知道有哈希沖突這麼一回事即可，可依然免不瞭裝備的嫌疑。可hashmap背後的思想，在緩存，在數據傾斜，在負載均衡等分佈式大數據領域都能廣泛看到其身影。瞭解其背後的思想不僅僅隻是為瞭一個hashmap.更重要的是，hashmap不像jvm底層原理那麼遙遠，不像並發編程那麼宏大，它隻需要通勤路上十分鐘就可搞定基本原理，有什麼理由不呢？所以本文試著從相對少見的一個微小角度來重新審視一下hashmap.1.準備工作。1.1模擬哈希沖突新建兩個class,一個正常重寫equals和hashcode方法，一個故意在hashcode方法裡返回一定范圍內的隨機數，模擬哈希沖突，以及控制哈希沖突的程序。不沖突的類@Setter
public class KeyTest2 {
private String name;

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

KeyTest2 keyTest = (KeyTest2) o;

return name != null ? name.equals(keyTest.name) : keyTest.name == null;
}

@Override
public int hashCode() {
return name != null ? name.hashCode() : 0;
}
}
沖突的類@Setter
@NoArgsConstructor
public class KeyTest {
private String name;

private Random random;

public KeyTest(Random random){
this.random = random;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

KeyTest keyTest = (KeyTest) o;

return name != null ? name.equals(keyTest.name) : keyTest.name == null;
}

@Override
public int hashCode() {
// return name != null ? name.hashCode() : 0;
return random.nextInt(1000);
}
}
眾所周知，hashmap在做put的時候，先根據key求hashcode，找到數組下標位置，如果該位置有元素，再比較equals，如果返回true,則替換該元素並返回被替換的元素;否則就是哈希沖突瞭，即hashcode相同但equals返回false。哈希沖突的時候在沖突的數組處形成數組，長度達到8以後變成紅黑樹。1.2 java的基準測試。這裡使用JMH進行基準測試.JMH是Java Microbenchmark Harness的簡稱，一般用於代碼的性能調優，精度甚至可以達到納秒級別，適用於 java 以及其他基於 JVM 的語言。和 Apache JMeter 不同，JMH 測試的對象可以是任一方法，顆粒度更小，而不僅限於rest api.jdk9以上的版本自帶瞭JMH，如果是jdk8可以使用maven引入依賴。點擊查看JMH依賴2.測試初始化長度點擊查看初始化長度基本測試代碼測試結果圖對測試結果圖例做一個簡單的說明：以上基準測試，會得到一個json格式的結果。然後將該結果上傳到官方網站，會得到一個上述圖片的結果。橫坐標，紅色駐圖代表有沖突，淺藍色駐圖無沖突。眾坐標，ops/ns代表平均每次操作花費的時間，單位為納秒,1秒=1000000000納秒，這樣更精準。下同。簡單說，駐圖越高代表性能越低。我測瞭兩次，分別是無哈希沖突和有哈希沖突的，這裡隻貼一種結果。測試結果表明，hashmap定義時有初始化對比無初始化，有大約4%到12%的性能損耗。足夠的初始化長度下，有哈希沖突的測試結果：足夠的初始化長度下，沒有哈希沖突的測試結果：3.模擬一百萬個元素put，get的差異。眾所周知，hashmap在頻繁做resize時，性能損耗非常嚴重。以上是沒初始化長度，無沖突和有沖突的情況下，前者性能是後者性能的53倍。那麼在初始化長度的情況下呢？HashMap map = new HashMap(1000000);
同樣的代碼下，得到的測試結果以上是有初始化長度，無沖突和有沖突的情況下，前者性能是後者性能的58倍。大差不差，不管有無初始化長度，無沖突的效率都是有沖突效率的50倍以上。說明，這是哈希沖突帶來的性能損耗。4.模擬無紅黑樹情況下get效率4.1 將random擴大，哈希沖突嚴重性大大減小，模擬大多數哈希沖突導致的哈希鏈長度均小於8，無法擴展為紅黑樹，隻能遍歷數組。將KeyTest的hashcode方法改為：@Override
public int hashCode() {
// return name != null ? name.hashCode() : 0;
return random.nextInt(130000);
}
這樣1000000/130000 < 8,這樣大多數的哈希鏈將不會擴展為紅黑樹。測試結果為：測試結果說明，**有沖突的效率反而比無沖突的效率要高**，差不多高出80%左右。這其實有點違反常識，我們通常講，hashmap要盡量避免哈希沖突，哈希沖突的情況下寫入和讀取性能都會受到很大的影響。但是上面的測試結果表明，大數據量相對比較大的時候，適當的哈希沖突(<8)反而讀取效率更高。個人猜測是，適當的哈希沖突，數組長度大為減少。為瞭證明以上猜想，直接對ArrayList進行基準測試。4.1.1 ArrayList不同長度下get效率的基準測試模擬一個哈希沖突非常嚴重下，底層數組長度較小的list，和哈希沖突不嚴重情況下，底層數組較大的list，再隨機測試Get的效率如何。點擊查看測試代碼測試結果如下：可以看到，這裡不能(有誤，待重測)間接證實瞭以上的猜想。當然這裡的代碼可能並不嚴謹，也歡迎大傢一起討論。4.2 jdk1.8版本，哈希沖突嚴重下的get效率測試測試結果說明：在jdk8,無沖突效率是有有沖突的3倍左右。4.3 將jdk版本降為1.7，在哈希沖突依然嚴重的情況下，get效率如何？測試結果說明：在jdk7,無沖突效率是有有沖突的12倍左右。結合4.1和4.2的測試對比，說明jdk1.8紅黑樹的優化效率確實提升很大。5.總結1.初始化的時候指定長度，長度要考慮到負載因子0.75.初始化的影響受到哈希沖突的影響，沒有那麼大(相對於倍數而言)，但也不小。2.哈希沖突嚴重時，put性能急劇下降。（幾十倍級）3.相同元素個數的前提下，在哈希沖突時，get效率反而更高。4.相比之前的版本，哈希沖突嚴重時，jdk8紅黑樹對get效率有非常大的提升。測試代碼和測試結果在 這裡蒼茫之天涯，乃吾輩之所愛也；浩瀚之程序，亦吾之所愛也，然則何時而愛耶？必曰：先天下之憂而憂，後天下之愛而愛也！