本文都是基于JDK1.8，不去對比JDK1.7或者JDK1.6
JDK1.8中hashMap的組成
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//默認初始容量区丑，是HashMap的最小容量為16挠轴，容量就是數(shù)組的大小也就是變量茧彤，transient Node<K,V>[] table常侦。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量，該數(shù)組最大值為2^31次方坠宴。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認的加載因子洋魂，如果構造的時候不傳則為0.75，用于擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一個位置里存放的節(jié)點轉化成樹的閾值，也就是8副砍，比如數(shù)組里有一個node衔肢，這個node鏈表的長度達到8才會轉化為紅黑樹。
static final int TREEIFY_THRESHOLD = 8;
//當一個反樹化的閾值豁翎，當這個node長度減少到該值就會從樹轉化成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//滿足節(jié)點變成樹的另一個條件角骤，就是存放node的數(shù)組長度要達到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具體存放數(shù)據(jù)的數(shù)組
transient Node<K,V>[] table;
//entrySet，一個存放k-v緩沖區(qū)
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少個鍵值對
transient int size;
//對map的修改次數(shù)
transient int modCount;
//閾值 表示當前HashMap能夠承受的最多的鍵值對數(shù)量心剥，一旦超過這個數(shù)量HashMap就會進行擴容
int threshold;
//加載因子
final float loadFactor;
}
在JDK 1.8中邦尊，HashMap的底層數(shù)據(jù)結構是“數(shù)組+鏈表+紅黑樹”，即在鏈表的長度超過閾值8時轉化為紅黑樹結構优烧，這樣大大減少了查找時間蝉揍。
首先我們先回顧一下數(shù)組和鏈表
數(shù)組的特點：它的存儲區(qū)間是連續(xù)的，占用內存嚴重畦娄，空間復雜也很大又沾，時間復雜為O(1)。
優(yōu)點：是隨機讀取效率很高熙卡，因為數(shù)組是連續(xù)的（隨機訪問性強杖刷，查找速度快）。
缺點：插入和刪除數(shù)據(jù)效率低驳癌，由于插入數(shù)據(jù)的時候插入位置后面的數(shù)據(jù)在內存中要往后移動滑燃，且大小固定不易動態(tài)擴展。鏈表的特點：區(qū)間離散颓鲜，占用內存寬松不瓶，空間復雜度小，時間復雜度O(N)灾杰。
優(yōu)點：插入刪除速度快，內存利用率高熙参，沒有大小固定艳吠，擴展靈活。
缺點：不能隨機查找孽椰，每次都是從第一個開始遍歷（查詢效率低）昭娩。
有沒有一種數(shù)據(jù)結構，查詢效率高并且插入刪除的效率也高呢黍匾？
哈希表就是這樣一種數(shù)據(jù)結構栏渺，哈希表是基于哈希函數(shù)建立的一種查找表，hash函數(shù)就是根據(jù)key計算出應該存儲地址的位置（地址index=H（key））锐涯，它其實就是將數(shù)組和鏈表兩種數(shù)據(jù)結構相結合磕诊，簡單的說就是每個元素都是鏈表的數(shù)組。
在JDK1.8中，對HashMap的底層實現(xiàn)進行了優(yōu)化霎终，數(shù)據(jù)結構的存儲由數(shù)組+鏈表的方式滞磺，變化為數(shù)組+鏈表+紅黑樹的存儲方式，當鏈表長度超過閾值（8）時莱褒，將鏈表轉換為紅黑樹击困，在性能上進一步得到提升。下圖表示了JDK1.8的HashMap數(shù)據(jù)結構广凸。
接下來分析一下JDK1.8的源碼中涉及到的數(shù)據(jù)結構阅茶，也解釋一下為什么鏈表長度為8時要轉換為紅黑樹的問題？
在HashMap的源碼注釋中其實已經說明其實現(xiàn)結構谅海。
/*
* Implementation notes.
*
* This map usually acts as a binned (bucketed) hash table, but
* when bins get too large, they are transformed into bins of
* TreeNodes, each structured similarly to those in
* java.util.TreeMap.
* 說是map通常當做binned（存儲桶）的哈希表脸哀，但是當bin太大時，它們將轉換為TreeNodes的bin胁赢，每個bin的結構與java.util.TreeMap中的相似企蹭。
數(shù)組
transient Node<K,V>[] table;
鏈表
數(shù)組元素Node<K,V>實現(xiàn)了Entry接口,Node是單向鏈表，它實現(xiàn)了Map.Entry接口
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
紅黑樹
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
JDK1.8使用紅黑樹的改進
在java jdk8中對HashMap的源碼進行了優(yōu)化智末。在jdk8中谅摄，HashMap處理“碰撞”增加了紅黑樹這種數(shù)據(jù)結構，當碰撞結點較少時系馆，采用鏈表存儲送漠，當較大時（>8個），采用紅黑樹由蘑。
我們都知道闽寡，鏈表的時間復雜度是O(n)，紅黑樹的時間復雜度O(logn)尼酿，很顯然爷狈，紅黑樹的復雜度是優(yōu)于鏈表的。
那為什么hashmap不直接使用紅黑樹呢裳擎？
從時間復雜度來分析涎永，紅黑樹的平均查找長度是log(n)，如果長度為8鹿响，平均查找長度為log(8)=3羡微，鏈表的平均查找長度為n/2，當長度為8時惶我，平均查找長度為8/2=4妈倔，這才有轉換成樹的必要；鏈表長度如果是小于等于6绸贡，6/2=3盯蝴，而log(6)=2.6毅哗，雖然速度也很快的，但是轉化為樹結構和生成樹的時間并不會太短结洼。
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes 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
從具體源碼中來分析：源碼中的注釋寫的很清楚黎做，因為樹節(jié)點所占空間是普通節(jié)點的兩倍松忍，所以只有當節(jié)點足夠多的時候蒸殿，才會使用樹節(jié)點。也就是說鸣峭，節(jié)點少的時候宏所，盡管時間復雜度上，紅黑樹比鏈表好一點摊溶，但是紅黑樹所占空間比較大爬骤，綜合考慮，認為只能在節(jié)點太多的時候莫换，紅黑樹占空間大這一劣勢不太明顯的時候霞玄，才會舍棄鏈表，使用紅黑樹拉岁，說白了就是trade-off坷剧，空間和時間的權衡。
那為什么達到閾值8才會選擇使用紅黑樹呢喊暖？
當hashCode離散性很好的時候惫企，樹型bin用到的概率非常小，因為數(shù)據(jù)均勻分布在每個bin中陵叽，幾乎不會有bin中鏈表長度會達到閾值狞尔。但是在隨機hashCode下，離散性可能會變差巩掺，然而JDK又不能阻止用戶實現(xiàn)這種不好的hash算法偏序，因此就可能導致不均勻的數(shù)據(jù)分布。不過理想情況下隨機hashCode算法下所有bin中節(jié)點的分布頻率會遵循泊松分布胖替，而且根據(jù)統(tǒng)計禽车，一個bin中鏈表長度達到8個元素的概率為0.00000006，幾乎是不可能事件刊殉。所以選擇閾值是8，是根據(jù)概率統(tǒng)計決定的州胳。而且此時鏈表的性能已經很差了记焊。所以在這種比較罕見和極端的情況下，才會把鏈表轉變?yōu)榧t黑樹栓撞。因為鏈表轉換為紅黑樹也是需要消耗性能的遍膜，特殊情況特殊處理碗硬，為了挽回性能，權衡之下瓢颅，才使用紅黑樹來提高性能恩尾。也就是說在大部分情況下，hashmap還是使用的鏈表挽懦，如果是理想的均勻分布翰意，節(jié)點數(shù)不到8，hashmap就會自動擴容信柿，看下面鏈表轉為紅黑樹的方法的源碼就可以：
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
* 除非hash表太屑脚肌（在這種情況下將調整大小）渔嚷，否則將替換給定哈希值的索引處bin中所有鏈接的節(jié)點进鸠。
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
在該方法中，有這樣一個判斷形病，數(shù)組長度小于MIN_TREEIFY_CAPACITY客年，就會擴容，而不是直接轉變?yōu)榧t黑樹漠吻，因此可不是什么鏈表長度為8就變?yōu)榧t黑樹量瓜，還有別的條件。
//滿足節(jié)點變成樹的另一個條件侥猩，就是存放node的數(shù)組長度要達到64
static final int MIN_TREEIFY_CAPACITY = 64;
因此在通常情況下榔至，鏈表長度很難達到8，但是特殊情況下鏈表長度為8欺劳，哈希表容量又很大唧取，造成鏈表性能很差的時候，就會采用紅黑樹提高性能划提，這就是為什么鏈表長度為8時要轉換為紅黑樹的原因枫弟。那我們紅黑樹退化為鏈表的情況又是怎么樣的呢？下面將介紹HashMap中的擴容問題鹏往。
HashMap構造函數(shù)
HashMap的構造方法有4種淡诗，主要涉及到的參數(shù)有，指定初始容量伊履，指定填充比和用來初始化的Map
//構造函數(shù)1(帶有初始容量和加載因子的有參構造函數(shù))
public HashMap(int initialCapacity, float loadFactor) {
//指定的初始容量非負
if (initialCapacity < 0)
throw new IllegalArgumentException(Illegal initial capacity: +
initialCapacity);
//如果指定的初始容量大于最大容量,置為最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充比為正
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(Illegal load factor: +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//新的擴容臨界值
}
//構造函數(shù)2(只帶有初始容量的構造函數(shù))
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//構造函數(shù)3(無參構造函數(shù))
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//構造函數(shù)4(用m的元素初始化散列映射)
public HashMap(Map<!--? extends K, ? extends V--> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
HashMap存取原理
（1）HashMap中put()
put()實現(xiàn)原理
1韩容，判斷鍵值對數(shù)組tab[]是否為空或為null，否則以默認大小resize()唐瀑；
2群凶，根據(jù)鍵值key計算hash值得到插入的數(shù)組索引i，如果tab[i]==null哄辣，直接新建節(jié)點添加请梢，否則轉入3
3赠尾，判斷當前數(shù)組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個節(jié)點類型即可),分別處理
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*如果table的在（n-1）&hash的值是空，就新建一個節(jié)點插入在該位置*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/*表示有沖突,開始處理沖突*/
else {
Node<K,V> e;
K k;
/*檢查第一個Node毅弧，p是不是要找的值*/
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
/*指針為空就掛在后面*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果沖突的節(jié)點數(shù)已經達到8個气嫁，看是否需要改變沖突節(jié)點的存儲結構，
//treeifyBin首先判斷當前hashMap的長度够坐，如果不足64寸宵，只進行
//resize，擴容table咆霜，如果達到64邓馒，那么將沖突的存儲結構為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/*如果有相同的key值就結束遍歷*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/*就是鏈表上有相同的key值*/
if (e != null) { // existing mapping for key，就是key的Value存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;//返回存在的Value值
}
}
++modCount;
/*如果當前大小大于門限蛾坯，門限原本是初始容量*0.75*/
if (++size > threshold)
resize();//擴容兩倍
afterNodeInsertion(evict);
return null;
}
（2）HashMap中get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;//Entry對象數(shù)組
Node<K,V> first,e; //在tab數(shù)組中經過散列的第一個位置
int n;
K k;
/*找到插入的第一個Node光酣，方法是hash值和n-1相與，tab[(n - 1) & hash]*/
//也就是說在一條鏈上的hash值相同的
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
/*檢查第一個Node是不是要找的Node*/
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))//判斷條件是hash值要相同脉课，key值要相同
return first;
/*檢查first后面的node*/
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
/*遍歷后面的鏈表救军，找到key值和hash值都相同的Node*/
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
}
get(key)方法時獲取key的hash值，計算hash&(n-1)得到在鏈表數(shù)組中的位置first=tab[hash&(n-1)],先判斷first的key是否與參數(shù)key相等倘零，不等就遍歷后面的鏈表找到相同的key值返回對應的Value值即可唱遭。
HasMap的擴容機制resize();
前面多次提到的負載因子：源碼中有個公式為threshold = loadFactor * 容量。HashMap和HashSet都允許你指定負載因子的構造器呈驶，表示當負載情況達到負載因子水平的時候拷泽，容器會自動擴容，HashMap默認使用的負載因子值為0.75f（當容量達到四分之三進行再散列（擴容））袖瞻。當負載因子越大的時候能夠容納的鍵值對就越多但是查找的代價也會越高司致。所以如果你知道將要在HashMap中存儲多少數(shù)據(jù)，那么你可以創(chuàng)建一個具有恰當大小的初始容量這可以減少擴容時候的開銷聋迎。但是大多數(shù)情況下0.75在時間跟空間代價上達到了平衡所以不建議修改脂矫。
resize() 函數(shù)會在兩種情況下被調用：
(1) HashMap new 出來后還沒有 put 元素進去，沒有真正分配存儲空間被初始化霉晕，調用 resize() 函數(shù)進行初始化庭再；
(2) 原 table 中的元素個數(shù)達到了 capacity * loadFactor 這個上限，需要擴容牺堰。此時調用 resize()拄轻，new 一個兩倍長度的新 Node 數(shù)組，進行rehash伟葫，并將容器指針（table）指向新數(shù)組恨搓。
邊也可以引申到一個問題HashMap是先插入還是先擴容：HashMap初始化后首次插入數(shù)據(jù)時，先發(fā)生resize擴容再插入數(shù)據(jù)扒俯，之后每當插入的數(shù)據(jù)個數(shù)達到threshold時就會發(fā)生resize奶卓，此時是先插入數(shù)據(jù)再resize。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/*如果舊表的長度不是空*/
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*把新表的長度設置為舊表長度的兩倍撼玄，newCap=2*oldCap*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/*把新表的門限設置為舊表門限的兩倍夺姑，newThr=oldThr*2*/
newThr = oldThr << 1; // double threshold
}
/*如果舊表的長度的是0，就是說第一次初始化表*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//新表長度乘以加載因子
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
/*下面開始構造新表掌猛，初始化表中的數(shù)據(jù)*/
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//把新表賦值給table
if (oldTab != null) {//原表不是空要把原表中數(shù)據(jù)移動到新表中
/*遍歷原來的舊表*/
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//說明這個node沒有鏈表直接放在新表的e.hash & (newCap - 1)位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
/*如果e后邊有鏈表,到這里表示e后面帶著個單鏈表盏浙，需要遍歷單鏈表，將每個結點重*/
else { // preserve order保證順序
新計算在新表的位置荔茬，并進行搬運
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;//記錄下一個結點
//新表是舊表的兩倍容量废膘，實例上就把單鏈表拆分為兩隊，
//e.hash&oldCap為偶數(shù)一隊慕蔚，e.hash&oldCap為奇數(shù)一對
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {//lo隊不為null丐黄，放在新表原位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//hi隊不為null，放在新表j+oldCap位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
