HashMap之三问为什么及性能问题
文章目錄
- 一、加載因子為什么是0.75
- 二、為什么要無符號右移16位后做異或運算
- 三、為什么槽位數(shù)必須使用2^n
- 四、JAVA 8 HashMap改進
- 五、HashMap性能問題
寫在前面：無論在工作中和面試的時候都會遇到關(guān)于HashMap問題，這一篇文章我們主要從以下幾個方面講解HashMap。至于分析源碼網(wǎng)上已經(jīng)有很多這樣的文章，所以這里就不在以源碼為中心講述。
HashMap數(shù)據(jù)結(jié)構(gòu)
在JDK1.6，JDK1.7中，HashMap采用位桶+鏈表實現(xiàn)，即使用鏈表處理沖突,同一hash值的鍵值對會被放在同一個位桶里，當桶中元素較多時，通過key值查找的效率較低。
而JDK1.8中，HashMap采用位桶+鏈表+紅黑樹實現(xiàn)，當鏈表長度超過閾值（8）,時，將鏈表轉(zhuǎn)換為紅黑樹，這樣大大減少了查找時間。
一、加載因子為什么是0.75
先說結(jié)果：提高空間利用率和減少查詢成本的折中，選擇0.75作為默認的加載因子，完全是時間和空間成本上尋求的一種折衷選擇。
加載因子解釋：表示Hash表中元素的填滿的程度。加載因子越大，填滿的元素越多,空間利用率越高，但沖突的機會加大了。反之，加載因子越小，填滿的元素越少，沖突的機會減小，但空間浪費多了。沖突的機會越大,則查找的成本越高。反之,查找的成本越小。因此,必須在 "沖突的機會"與"空間利用率"之間尋找一種平衡與折衷。
哈希沖突主要與兩個因素有關(guān)
- 填裝因子，填裝因子是指哈希表中已存入的數(shù)據(jù)元素個數(shù)與哈希地址空間的大小的比值，a=n/m ; a越小，沖突的可能性就越小，相反則沖突可能性較大；但是a越小空間利用率也就越小，a越大，空間利用率越高，為了兼顧哈希沖突和存儲空間利用率，通常將a控制在0.6-0.9之間。
- 與所用的哈希函數(shù)有關(guān)，如果哈希函數(shù)得當，就可以使哈希地址盡可能的均勻分布在哈希地址空間上，從而減少沖突的產(chǎn)生，但一個良好的哈希函數(shù)的得來很大程度上取決于大量的實踐。
如果想繼續(xù)了解如何解決hash沖突請看這篇文章：解決hash沖突的三個方法
以上是對加載因子為什么是0.75的解釋下文將繼續(xù)講解為什么是0.75
HashMap有一個初始容量大小，默認是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16為了減少沖突的概率，當hashMap的數(shù)組長度到了一個臨界值就會觸發(fā)擴容，把所有元素rehash再放到擴容后的容器中，這是一個非常耗時的操作。
而這個臨界值由【加載因子】和當前容器的容量大小來確定：DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR ，即默認情況下是16x0.75=12時，就會觸發(fā)擴容操作。
所以使用hash容器時盡量預(yù)估自己的數(shù)據(jù)量來設(shè)置初始值。具體代碼實現(xiàn)自行去研究HashMap的源碼。
基礎(chǔ)知識補充完畢，回到正題，為什么加載因子要默認是0.75？
hashmap源碼注釋里找到了這一段
Ideally, under random hashCodes, the frequency ofnodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are: 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million注意http://en.wikipedia.org/wiki/Poisson_distribution鏈接中的關(guān)鍵字：Poisson_distribution 中文翻譯為： 泊淞分布
簡單翻譯一下就是在理想情況下,使用隨機哈希碼,節(jié)點出現(xiàn)的頻率在hash桶中遵循泊松分布，同時給出了桶中元素個數(shù)和概率的對照表。
從上面的表中可以看到當桶中元素到達8個的時候，概率已經(jīng)變得非常小，也就是說用0.75作為加載因子，每個碰撞位置的鏈表長度超過８個是幾乎不可能的。
重申一下使用hash容器請盡量指定初始容量，且是2的冪次方。
關(guān)于泊淞分布的知識請看：泊松分布和指數(shù)分布：10分鐘教程
二、為什么要無符號右移16位后做異或運算
HashMap中哈希算法的關(guān)鍵代碼
//重新計算哈希值 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key如果是null 新hashcode是0 否則 計算新的hashcode }//計算數(shù)組槽位static int indexFor(int h, int length) {return h & (length-1); }這段代碼可以看到哈希算法的細節(jié)(h = key.hashCode()) ^ (h >>> 16)
^按位異或運算，只要位不同結(jié)果為1，不然結(jié)果為0；>>> 無符號右移：右邊補0
根據(jù)上面的說明我們做一個簡單演練
h=key.hashcode() 1111 1101 1101 1111 0101 1101 0010 1111 ^ h >>> 16 0000 0000 0000 0000 1111 1101 1101 1111 -------------------------------------------------------- h^(h>>>16) 1111 1101 1101 1111 1010 0000 1111 0000 h=key.hashcode() 1111 1101 1101 1111 0101 1101 0010 1111將h無符號右移16為相當于將高區(qū)16位移動到了低區(qū)的16位，再與原h(huán)ashcode做異或運算，可以將高低位二進制特征混合起來
從上文計算可知高區(qū)的16位與原h(huán)ashcode相比沒有發(fā)生變化，低區(qū)的16位發(fā)生了變化
我們可知通過上面(h = key.hashCode()) ^ (h >>> 16)進行運算可以把高區(qū)與低區(qū)的二進制特征混合到低區(qū)，那么為什么要這么做呢？
我們都知道重新計算出的新哈希值在后面將會參與hashmap中數(shù)組槽位的計算，計算公式：(n - 1) & hash，假如這時數(shù)組槽位有16個，則槽位計算如下：
hash 1111 1101 1101 1111 1010 0000 1111 0000 & 16 -1 0000 0000 0000 0000 0000 0000 0000 1111 -------------------------------------------------------- (16 - 1) & hash 0000 0000 0000 0000 0000 0000 0000 0000如果不了解與運算可以看這篇文章：與運算（&）、或運算（|）、異或運算（^）
而在這里采用異或運算而不采用& ，| 運算的原因是，異或運算能更好的保留各部分的特征，如果采用&運算計算出來的值會向1靠攏，采用|運算計算出來的值會向0靠攏 。
接下來將得到的值與與0xf做&運算 目的是得到后四位的數(shù)值，得到后四位的下標在0~15之間 對應(yīng)的放在哪個桶里面，當然這里存在擴容的問題，根據(jù)實際情況確定桶的個數(shù)。
三、為什么槽位數(shù)必須使用2^n
先說結(jié)果：為了讓哈希后的結(jié)果更加均勻
這個原因我們繼續(xù)用上面的例子來說明
假如槽位數(shù)不是16，而是17，則槽位計算公式變成：(17 - 1) & hash
從上文可以看出，計算結(jié)果將會大大趨同，hashcode參加&運算后被更多位的0屏蔽，計算結(jié)果只剩下兩種0和16，這對于hashmap來說是一種災(zāi)難
2、可以通過位運算e.hash & (newCap - 1)來計算，a % (2^n) 等價于 a & (2^n - 1) ，位運算的運算效率高于算術(shù)運算，原因是算術(shù)運算還是會被轉(zhuǎn)化為位運算。
四、JAVA 8 HashMap改進
java8和java7最大的區(qū)別就是節(jié)點可以擴展到TreeNodes，TreeNode是一個紅黑樹結(jié)構(gòu)，可以存儲更多的信息。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {final int hash; // inherited from Node<K,V>final K key; // inherited from Node<K,V>V value; // inherited from Node<K,V>Node<K,V> next; // inherited from Node<K,V>Entry<K,V> before, after;// inherited from LinkedHashMap.Entry<K,V>TreeNode<K,V> parent;TreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;boolean red;使用紅黑樹的主要優(yōu)點：在許多數(shù)據(jù)都位于內(nèi)部表的同一索引（存儲桶）中的情況下，在樹中進行搜索花費的時間比鏈表時間短。
缺點：樹比鏈接列表占用了更多的空間
通過繼承，內(nèi)部可以同時包含 Node（鏈接列表）和 TreeNode（紅黑樹）。Oracle決定使用以下規(guī)則使用這兩個數(shù)據(jù)結(jié)構(gòu)：
- 如果內(nèi)部表中給定索引（存儲桶）的節(jié)點超過8個，則鏈表轉(zhuǎn)換為一棵紅黑樹
- 如果給定索引（存儲桶） ）內(nèi)部表中的節(jié)點少于6個，樹被轉(zhuǎn)換為鏈表
五、HashMap性能問題
在正常情況下，get()和put()方法的時間復(fù)雜度為O(1）。但是，如果key分布不均，可能put()和get()調(diào)用非常慢。put()和get()的性能取決于將數(shù)據(jù)重新分配到內(nèi)部數(shù)組（存儲桶）的不同索引中。如果key的哈希函數(shù)使用不當，存儲數(shù)據(jù)將會分配不均，調(diào)用put()和get()都會很慢，因為需要遍歷整個列表。
key分布不均HashMap。
key分布均勻HashMap
在分布均勻的HashMap情況下，獲得K將花費3次迭代。兩個HashMap都存儲相同數(shù)量的數(shù)據(jù)，并且具有相同的內(nèi)部數(shù)組大小。
以下示例，創(chuàng)建了一個哈希函數(shù)，該函數(shù)將所有數(shù)據(jù)放入同一存儲桶中，然后添加200萬個元素。
public class Test {public static void main(String[] args) {class MyKey {Integer i;public MyKey(Integer i){this.i =i;}@Overridepublic int hashCode() {return 1;}@Overridepublic boolean equals(Object obj) {…}}Date begin = new Date();Map <MyKey,String> myMap= new HashMap<>(2_500_000,1);for (int i=0;i<2_000_000;i++){myMap.put( new MyKey(i), "test "+i);}Date end = new Date();System.out.println("Duration (ms) "+ (end.getTime()-begin.getTime()));} }在我的核心i5-2500k @ 3.6Ghz上，使用Java 8 需要超過45分鐘（我在45分鐘后停止了該過程）。
現(xiàn)在，如果我運行相同的代碼，但是這次我使用以下哈希函數(shù)
@Overridepublic int hashCode() {int key = 2097152-1;return key+2097152*i; }需要46秒
如果我使用以下哈希函數(shù)運行相同的代碼，則可以提供更好的哈希重新分區(qū)
@Override public int hashCode() { return i; }需要2秒鐘。
使用HashMap時，盡可能使用合適的key，將key散列到盡可能多的存儲桶中。字符串對象是一個很好的key，因為它具有良好的哈希功能。整數(shù)也很好，因為它們的哈希碼是它們自己的值。
如果需要存儲大量數(shù)據(jù)，則應(yīng)為HashMap創(chuàng)建初始容量。
Map默認大小16，加載因子為0.75。第一個到第11個put()非常快，但是第12個（16 * 0.75）將重新創(chuàng)建一個新的內(nèi)部數(shù)組（及其關(guān)聯(lián)的鏈表/樹），其新容量為32。第13個到第23個將很快，但是第24個（32 * 0.75）將從新擴容。在數(shù)量小的情況下，內(nèi)部陣列的完全恢復(fù)速度很快，但在數(shù)量大的情況下，可能需要幾秒鐘到幾分鐘。通過設(shè)置map的大小，可以避免這些自動擴容帶來的代價。
但是有一個缺點：如果您將數(shù)組大小設(shè)置得很高，例如2 ^ 28，而在數(shù)組中僅使用2 ^ 26個存儲桶，則會浪費大量內(nèi)存。
總結(jié)
以上是生活随笔為你收集整理的HashMap之三问为什么及性能问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 详细分析如何在java代码中使用继承和组
- 下一篇： 一篇文章弄懂Java反射基础和反射的应用