165
重寫hashcode，玩兒壞HashMap
重寫hashcode，玩兒壞HashMap
緣起
提到HashMap，都知道“線程不安全，並發情況下不能用”，除此之外貌似了解的不是很多。
對，我就是其中一員。
這兩天跟兩個開發大神學習了一下，並參考了網上的一些文檔，淺顯整理如下。
關鍵點
1.HashMap的定位是單線程高性能的 key-value 存儲數據結構，多線程請使用ConcurrentHashMap。
2.HashMap性能好壞的關鍵是避免hash衝突，以及衝突很多的情況下，如何更高效。
前提：完美Hash函數不存在
如果讓每個key的hashcode都不一樣，那無疑是最高效的，但實際的情況是不可能的，因為你沒有無限的內存，這種假設不成立。
所以，Java中實現HashMap的hashcode返回值是整形，根據鴿籠理論，當我們的對象超過整形最大值時，這些對象會發生哈希碰撞。
實現：分桶
除了上麵完美Hash函數不存在，通過允許合理的哈希碰撞來節省內存，也是HashMap的考慮，而且很多情況下，Hash值經常集中在幾個特定的值上
所以，看HashMap源碼：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默認是分了M=16個桶來進行分桶存儲。所以，衝突的概率是1/M。
衝突後的實現：分離鏈表
下圖是HashMap的數據結構圖，前麵是桶，後麵是每個桶的鏈表結構。
當桶沒有出現hash衝突時，hashmap查找元素是很快的。但桶hash衝突後，每個桶就變成了單的鏈表。
這種情況隻能順序遍曆每個節點，直到找到想搜索的節點為止，極端情況，會達到最壞時間複雜度。(見下麵：java8優化點)
但這種實現，至少比另一種實現方式：開放尋址的方法要好，理由如下：（摘自網絡）
開放尋址使用連續的空間，因此有著緩存效率的提升。因此當數據量較小時，能夠放到係統緩存中時，開放尋址會表現出比分離鏈接更好的性能。
但是當數據量增長時，它的性能就會越差，因為我們無法期待一個大的數組能夠得到緩存性能優化。
這也是HashMap使用分離鏈表來解決哈希衝突的原因。此外，開放尋址還有一個弱點。我們調用remove()方法會十分頻繁，當我們刪除數據時，一個特定的哈希衝突，可能會幹擾總體的性能，而分離鏈表則沒有這樣的缺點。”
java8優化分離鏈表：引入紅黑樹
除了最壞複雜度之外，如果數據很多，hash值不平均，比如集中在某幾個特定的值上，使用樹會比鏈表有著更快的性能。
所以，java8裏麵使用如下策略進行鏈表or樹結構的轉換。即：當衝突的元素數=8時，鏈表變為樹；當減少到6時，樹切換為鏈表。
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
補充說明：（摘自網絡）
另外，java8裏麵，HashMap使用Node類替代了Entry類，它們的結構大體相同。
但顯著地差別是，Node類具有導出類TreeNode，通過這種繼承關係，一個鏈表很容易被轉換成樹。
衝突還是要解決，動態擴容桶
哈希桶的默認數量是16，最大值是整形最大值。如果桶數量不變，即便上述內容，性能也不會明顯的提升，
所以，HashMap使用下麵方式進行動態擴容。
當桶數量超過當前值 * DEFAULT_LOAD_FACTOR 時，就自動擴容，然後重新插入所有數據。
例如當桶數到達: 初始桶數16*閥值0.75 = 12時，自動擴容到 16*2 = 32個桶。這樣，衝突就立減降低，但重新插入性能也有損耗。
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
通過重寫hashcode，論證上述內容
測試類如下：
package com.taobao.huachuan;
import java.util.HashMap;
import java.util.Map;
/**
* 對比hash衝突和不衝突
* @author sheshijie
*
*/
public class TestHashMap {
public static void main(String[] args) {
Map<TaoPP1, Integer> m1 =new HashMap<TaoPP1, Integer>();
Long start1 = System.currentTimeMillis();
for(int i = 0 ;i<10000;i++)
{
TaoPP1 tp1 = new TaoPP1();
tp1.setAge(i);
tp1.setValue(i);
m1.put(tp1, i);
}
System.out.println("hashcode不衝突的耗時："+(System.currentTimeMillis()-start1) +" size:" + m1.size());
Map<TaoPP2, Integer> m2 =new HashMap<TaoPP2, Integer>();
Long start2 = System.currentTimeMillis();
for(int i = 0 ;i<10000;i++)
{
TaoPP2 tp2 = new TaoPP2();
tp2.setAge(i);
tp2.setValue(i);
m2.put(tp2, i);
}
System.out.println("hashcode衝突的耗時："+(System.currentTimeMillis()-start2) +" size:" + m2.size());
Long start3 = System.currentTimeMillis();
System.out.println("不衝突尋址 "+m1.get(new TaoPP2())+"耗時："+(System.currentTimeMillis()-start3));
Long start4 = System.currentTimeMillis();
System.out.println("衝突尋址 耗時:"+m2.get(new TaoPP2())+"耗時："+(System.currentTimeMillis()-start4));
}
}
重寫hashcode的方法如下：
/**
* 大量hashCode重複
*/
@Override
public int hashCode() {
return (age+value)%16;//反複調整，可以看出差距明顯
}
實際的測試結果為：
hashcode不衝突的耗時：16 size:10000
hashcode衝突的耗時：867 size:10000
果然，差距真的好大。
調整hashCode方法 return (age+value)%1024;
測試結果為：
hashcode不衝突的耗時：31 size:10000
hashcode衝突的耗時：78 size:10000
淺顯的證明了hashcode衝突的多少，是性能的關鍵。
而衝突後查找性能更加緩慢，結果如下：
不衝突尋址 null耗時：0
衝突尋址 耗時:null耗時：9
我是測試，寫錯了不要噴，要愛護我
我是測試，寫錯了不要噴，要愛護我
我是測試，寫錯了不要噴，要愛護我
重要的事情說三遍！
最後更新：2017-10-23 15:34:09