最近忙于各種事情，只能陸陸續(xù)續(xù)也看了一些東西，Java的HashMap應該算比較基礎的東西，也是最近在看<<Redis設計與實現(xiàn)>>，其中也有HashMap的數(shù)據(jù)結構，又回去看了一下Java本身實現(xiàn)，這篇也就再記錄一下。
Java數(shù)據(jù)結構中定義了Map接口，該接口有四個常用實現(xiàn)類：HashMap，?Hashtable，LinkedHashMap和TreeMap。
針對上面四個常用類簡單的介紹一下：
1. Hashtable: 從下面的Java doc就可以看出，其本身是線程安全的，但是并發(fā)性不如concurrent中的ConcurrentHashMap，而不需要線程安全時候，也推薦使用HashMap，故可以算是一個遺留類，不推薦使用。
2. LinkedHashMap：它是HashMap的一個子類，保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的。
3. TreeMap：TreeMap實現(xiàn)SortedMap接口，能夠把它保存的記錄根據(jù)鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator遍歷TreeMap時，得到的記錄是排過序的。如果使用排序的映射，建議使用TreeMap。
4. HashMap：它根據(jù)鍵的hashCode值存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。HashMap非線程安全，可能會導致數(shù)據(jù)的不一致。如果需要滿足線程安全，可以使用之前提及的ConcurrentHashMap（不建議用Hashtable）。
本篇主要簡單介紹的就是HashMap的實現(xiàn)，也是由于HashMap是最最常用的一個，可以滿足大部分場景。自己工作了一年時間，基本也只用過HashMap= =
內部結構
HashMap內部的數(shù)據(jù)結構，就是最經(jīng)典的數(shù)組+鏈表實現(xiàn)的哈希桶（JDK 1.7之前)，從1.8之后，鏈表節(jié)點數(shù)量滿足一定條件后，會自動轉換成紅黑樹的數(shù)據(jù)結構，進一步提高查詢效率。簡單來說，HashMap的結構就是一個指針數(shù)組。
圖中的黑點則是存放Key-Value的Node，其數(shù)據(jù)結構如下：
其中 hash是用來定位數(shù)組索引位置， next是鏈表的下一個node。
字段
Map.put("key", "value")
在不考慮擴容的情況下，put操作會首先計算key的hash值，并通過取高位運算 + 取模運算兩步，就能計算出該key在哈希桶的位置了。
當兩個key定位在了同一個位置，則表示發(fā)生了Hash碰撞。因此，良好的Hash算法，能夠盡量減少Hash碰撞，提高Map的存取效率。然而，即使很好的Hash算法，如果哈希桶的size很?。ㄏ啾扔贜ode數(shù)量），無論怎么計算，總是在這幾個位置，也會出現(xiàn)很多碰撞。因此，解決碰撞，不僅需要良好的Hash算法，還需要一個良好的擴容機制。
要討論擴容機制，就先看一下HashMap中的幾個字段(附默認值)：
從上面幾個字段可以看出，當put操作，使得size > threshold時，HashMap就會發(fā)生擴容。 并且從Java 動doc可以看出，Hash桶的大小一定是2的n次方。（正是這個限制，使得HashMap在擴容和計算key位置的運算效率提升了很多）
實現(xiàn)
Hash算法的實現(xiàn)，其實只有下面三行代碼:
int hashcode = key.hashCode(); // 獲取hashcode
int hashInt = hashcode ^??(hashcode >>> 16 ); // 高位運算
int index = hashInt & (length - 1) // 取模運算，?lenght是數(shù)組大小
第二步通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質量來考慮的，這么做可以在數(shù)組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。
第三步也是非常巧妙，因為Lenght是2的n次方，因此length - 1 永遠是n個1，其實相當于對hashInt做了一次取模，但是效率極高。
下面是JDK 1.8的put代碼實現(xiàn):
line 627-628: table為空則創(chuàng)建.
line 629-630: 計算index，并且check null， 如果為null， 直接創(chuàng)建一個index;
line 633-635: 如果需要put的key和該位置原來的key一樣，則直接覆蓋value， 否則進行下面的追加操作
line 676-637: 紅黑樹操作，追加Node到紅黑樹
line 638-650: 鏈表操作，追加node到鏈表，并且判斷是否需要轉化為紅黑樹。
line 661-662: 判斷是否需要擴容
擴容機制
擴容機制里的算法相對也比較復雜，HashMap的線程不安全性，也正是由于擴容時，鏈表操作可能導致的Infinite Loop引起。因此下一篇再具體舉例說明吧。順便可以一起把redis的HashMap resize機制一起說一下，基本都是大同小異。
總結
本篇就從源碼角度，簡單講解HashMap的基本數(shù)據(jù)結構和關鍵操做的實現(xiàn)，以及簡單介紹了擴容機制，由于JDK1.8以后的紅黑樹，導致擴容的代碼更加復雜，但是擴容的算法相對于1.8之前，也有了不少優(yōu)化，不過之后也不會深入算法方便，主要還是會介紹擴容的流程和原理。同事會結合redis的哈希表實現(xiàn)。
