JDK1.8HashMap探索
本文基于JDK1.8版本進行
國際慣例先來個大綱，以下就是按照大綱形式進行分析
- JDK1.8HashMap探索
- 1. 簡介
- 2.1類關系
- 2.2屬性
- 2.3 構造函數
- 2.4核心方法
- 3.思考問題
- 4.總結
1. 簡介
HashMap采用數組+連結清單+紅黑樹實作，當連結清單長度超過門檻值（8）時，将連結清單轉換為紅黑樹，這樣大大減少了查找時間。紅黑樹是JDK1.8版本加入進來的，1.8之前HashMap采用數組+連結清單實作，即使用連結清單處理沖突，同一hash值的節點都存儲在一個連結清單裡。但是當位于一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。
2.1類關系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
從關系圖中我們知道：
HashMap繼承了AbstractMap接口,能夠實作其中的所有可選的Map操作
HashMap實作了Map接口,能夠實作其中的所有可選的Map操作；
HashMap實作了Cloneable接口,能夠使用clone()方法；
HashMap實作了Serializable接口,支援序列化操作
眼尖的朋友可以會發現，為什麼繼承了AbstractMap接口又要實作Map接口呢？
其實跟據java集合架構的創始人Josh Bloch描述：
Josh Bloch承認這是一個失誤，最開始寫java集合架構的時候，他認為這樣寫，在某些地方可能是有價值的，直到他意識到錯了。顯然的，JDK的維護者，後來不認為這個小小的失誤值得去修改。是以就這樣存在下來了。
2.2屬性
/**
* 預設初始容量 - 必須是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = << ; // 為16,其實就是1 * 2的4次方
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = << ;
/**
* 沒有在構造函數中指定時使用的加載因子
*/
static final float DEFAULT_LOAD_FACTOR = f;
/**
* 使用樹而不是清單的容器計數門檻值。
* 将元素添加到至少包含多個節點的元素時，元素将轉換為樹。
* 該值必須大于2，并且應該至少為8，以便與收縮時轉換回普通箱的樹木移除假設相關聯。
*/
static final int TREEIFY_THRESHOLD = ;
/**
* 用于在調整大小操作期間對（拆分）桶進行的桶數門檻值。
* 應該小于TREEIFY_THRESHOLD，并且最多6個與在去除下的收縮檢測吻合。
*/
static final int UNTREEIFY_THRESHOLD = ;
/**
* 桶中可能被樹化的最小容量。
* （否則，如果bin中的節點太多，則調整表的大小。）應該至少為4 * TREEIFY_THRESHOLD以避免調整大小和樹化門檻值之間的沖突。
*/
static final int MIN_TREEIFY_CAPACITY = ;
2.3 構造函數
HashMap(int initialCapacity, float loadFactor)構造函數
/**
* 用指定的初始容量和加載因子的構造函數。
*
* @param 初始容量
* @param 加載因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < )
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//如果指定的初始容量大于最大容量
initialCapacity = MAXIMUM_CAPACITY;//重新指派指定的初始容量
if (loadFactor <= || Float.isNaN(loadFactor))//如果加載因子小于等于0或者未确定
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor(int cap)是傳回大于等于cap的最小的二次幂數值
/**
* 傳回大于等于cap的最小的二次幂數值。
*/
static final int tableSizeFor(int cap) {
int n = cap - ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
return (n < ) ? : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + ;
}
HashMap(int initialCapacity)帶一個參數的構造函數
/**
* 使用指定的初始容量和預設加載因子（0.75）的構造函數
* @param 初始容量
*
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
無參構造函數HashMap()
/**
* 使用預設初始容量（16）和預設加載因子（0.75）的構造函數
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
帶Map參數的構造函數
/**
* 帶Map參數的構造函數
*
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 實作Map.putAll和Map構造函數
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();//儲存m的大小
if (s > ) {
//如果table為空
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)//如果大于臨界值
threshold = tableSizeFor(t);
}
else if (s > threshold)//table不為空并且s的值大于臨界值
resize();//擴容
//将m的元素添加到hashmap集合中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
putVal(hash(key), key, value, false, evict)是将元素添加到HashMap集合中，具體分析在下面2.4中可見
2.4核心方法
因為hash方法在很多方法中都用到用來尋找對象鍵的位置，是以我們需要了解
static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );// 右移16位，忽略符号位，空位都以0補齊 // 如value >>> num -- num 指定要移位值value 移動的位數。
}
hash方法會先擷取對象的hashCode()值，然後在異或上右移16位後的hashCode()值做運算。
（1）put方法
/**
* 将指定的值與此映射中指定的鍵關聯。 如果集合之前包含相比對的映射，則舊值将被替換。
*
* @param key
* @param value
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
會調用putVal（）方法
/**
* 實作Map.put的核心方法
*
* @param hash hash處理過的值
* @param key 鍵
* @param value 值
* @param onlyIfAbsent true，不更改現有值
* @param evict false，處于建立模式。
*/
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) == )//如果table初始化數組結點為空或者長度為0
n = (tab = resize()).length;//進行擴容操作
if ((p = tab[i = (n - ) & hash]) == null)//确定桶中 (n - 1) & hash 位置的元素是否為空
tab[i] = newNode(hash, key, value, null);//新生成結點放入桶中
else {//桶中已存在元素
Node<K,V> e; K k;
if (p.hash == hash &&//比較數組中第一個值的hash值和key是否相等
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//将值指派給e儲存
else if (p instanceof TreeNode)//如果為紅黑樹結構
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//放入鍵值對
else {//如果為鍊式結構
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) {//周遊到尾部時
p.next = newNode(hash, key, value, null);//在尾部插入新結點
if (binCount >= TREEIFY_THRESHOLD - ) // 連結清單長度>于臨界值
treeifyBin(tab, hash);//桶的樹形化處理
break;//跳出循環
}
if (e.hash == hash &&//判斷連結清單中結點的key值與插入的元素的key值是否相等
((k = e.key) == key || (key != null && key.equals(k))))
break;//相等,跳出循環
// 用于周遊桶中的連結清單，與前面的e = p.next組合，可以周遊連結清單
p = e;
}
}
if (e != null) { // 存在比對的結點
V oldValue = e.value;//儲存e的結點值
if (!onlyIfAbsent || oldValue == null)//如果onlyIfAbsent為false或者舊值為空
e.value = value;//儲存新值
afterNodeAccess(e);//通路後回調
return oldValue;//傳回舊值
}
}
//結構性加1
++modCount;
if (++size > threshold)//如果實際大小大于臨界值
resize();//擴容
afterNodeInsertion(evict);//插入後回調
return null;
}
1）先判斷table == null或length == 0，如果滿足則進行resize()擴容操作。
2）根據hash方法判斷桶中 (n - 1) & hash 的位置是否為空，是的話就直接插入。
3）如果桶中 (n - 1) & hash 的位置不為空，比較數組中第一個值的hash值和key是否相等，相等則直接覆寫，
4）如果桶中 (n - 1) & hash 的位置不為空，且數組中第一個值的hash值和key不相等，則判斷是否為紅黑樹結構，是則把鍵值對插入紅黑樹中。
5）如果桶中 (n - 1) & hash 的位置不為空，且數組中第一個值的hash值和key不相等，不為紅黑樹結構，則一定為連結清單結構，周遊連結清單且在尾部加入新結點，同時判斷連結清單長度是否大于8，大于就執行treeifyBin(tab, hash)方法，轉化為紅黑樹提高效率。如果連結清單中存在的結點值與插入的元素的key值相等，則直接覆寫。
6）插入成功後如果實際大小大于臨界值threshold，進行擴容操作
7）擴容方法：每次擴容大小為原來的2倍，并且桶中的元素位置不變或者偏移到原來2倍的位置
/**
* 初始化或拓展數組大小。
* 如果為空，則根據門檻值中儲存的初始容量目标進行配置設定。
* 否則，使用二次幂次擴充，每個桶的元素必須保持相同的索引，或者在新表中以兩個偏移量的幂移動。
*
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//儲存table數組
int oldCap = (oldTab == null) ? : oldTab.length;//儲存table的容量
int oldThr = threshold;//儲存臨界值
int newCap, newThr = ;//初始化新的數組結點大小,臨界值
if (oldCap > ) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果table數組大小大于最大容量
threshold = Integer.MAX_VALUE;//重新指派臨界值
return oldTab;
}
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//如果舊容量翻倍後小于最大容量,并且舊容量>=預設初始容量
newThr = oldThr << ; // 臨界值擴容為2倍
}
else if (oldThr > ) //如果之前臨界值>0
newCap = oldThr;//臨界值指派給新數組初始化容量
else {
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"})
//初始化newTab數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//更新預設數組結點
if (oldTab != null) {//如果舊結點數組不為空
//周遊舊哈希表的每個桶，将舊哈希表中的桶複制到新的哈希表中
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//周遊判斷如果結點不為空
oldTab[j] = null;//置空結點
if (e.next == null)//如果結點後繼為空,也就是隻有一個結點
newTab[e.hash & (newCap - )] = e;//将e放入newTab中e.hash & (newCap - 1)的位置
else if (e instanceof TreeNode)//判斷是否是紅黑樹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//将結點樹分離
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;//把新結點加到周遊到的結點後繼上
if ((e.hash & oldCap) == ) {//如果hash值桉位與上舊容量值為0
if (loTail == null)//如果低位結點為0
loHead = e;//指派低位頭結點
else
loTail.next = e;//指派後繼
loTail = e;//指派低位結點
}
else {//如果hash值桉位與上舊容量值不為0
if (hiTail == null)//如果hi低位結點為空
hiHead = e;//指派hi頭結點
else
hiTail.next = e;//指派hi低位後繼
hiTail = e;//指派hi低位結點
}
} while ((e = next) != null);
if (loTail != null) {//如果lo低位不為空
loTail.next = null;//置空後繼
newTab[j] = loHead;//指派新結點值
}
if (hiTail != null) {//如果hi低位不為空
hiTail.next = null;//置空後繼
newTab[j + oldCap] = hiHead;//指派新結點值
}
}
}
}
}
return newTab;
}
8）比較重要的是桶的樹形化操作，需要滿足數組的大小大于64時，才會轉化為紅黑樹，否則會進行擴容操作。
/**
* 用索引替換桶中的所有連結節點，除非表太小，。
*/
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)//如果tab為空或者tab數組的長度小于被樹化的最小容量64
resize();//擴容
else if ((e = tab[index = (n - ) & hash]) != null) {//如果根據hash尋址的項不為空(e 為連結清單中的第一個結點)
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);
}
}
（2）get（Object key）方法
/**
* 傳回指定鍵映射到的值，
* 如果不包含傳回null。
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
其實裡面調用了getNode(hash(key), key)方法
/**
* 實作Map.get和相關方法
*
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > &&//tab不為空并且長度大于0并且根據hash尋址的項也不為空
(first = tab[(n - ) & hash]) != null) {
if (first.hash == hash && // always check first node,桶中第一個元素相等
((k = first.key) == key || (key != null && key.equals(k))))
return first;//傳回
if ((e = first.next) != null) {//如果桶中還有其他的值
if (first instanceof TreeNode)//如果為紅黑樹
return ((TreeNode<K,V>)first).getTreeNode(hash, key);//在紅黑樹中查找結點
do {//在連結清單中查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
getNode的時候如果2個鍵的hashcode相同了，則會判斷key是否相等，相等傳回值，否則繼續在連結清單或者紅黑樹中查找對應值
（3）remove（Object key）方法
/**
* 如果存在，則從該映射中删除指定鍵的映射。
*
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
裡面調用了removeNode方法
/**
* 實作Map.remove和相關的方法
* @param hash hash for key
* @param key the key
* @param value value比對如果matchValue，否則忽略
* @param matchValue 如果為true，則僅在值相等時删除
* @param movable 如果在移除時不移動其他節點
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > &&//如果tab不為空,長度大于0,并且根據hash尋址的項也不為空
(p = tab[index = (n - ) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&//如果桶中第一個元素相等
((k = p.key) == key || (key != null && key.equals(k))))
node = p;//儲存第一個元素
else if ((e = p.next) != null) {//如果桶中還有其他元素
if (p instanceof TreeNode)//如果是紅黑樹
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//在紅黑樹中查找該結點
else {
do {//在連結清單中查找該結點
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)//如果為紅黑樹,在紅黑樹中移除該結點
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//如果桶中第一個元素是要删除的結點
tab[index] = node.next;//删除該結點
else//如果是連結清單結構
p.next = node.next;//用連結清單的方式删除結點
//結構性加1
++modCount;
//大小減1
--size;
//删除後回調
afterNodeRemoval(node);
return node;
}
}
return null;
}
3.思考問題
-
為什麼加載因子是0.75？
這個是在時間和空間成本上尋求一種折中。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數 HashMap類的操作中，包括 get 和 put 操作，都反映了這一點）。在設定初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少rehash操作次數。如果初始容量大于最大條目數除以加載因子，則不會發生rehash 操作。
-
HashMap中如何解決Hash碰撞？
鍊位址法
-
如果兩個鍵的hashcode相同，如何擷取值對象？
它們會儲存在同一個桶位置的連結清單中。鍵對象的equals()方法用來找到鍵值對。
-
如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
會進行擴容操作
-
為什麼String, Interger這樣的wrapper類适合作為鍵？
因為他們是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了，放入和取出時的hashCode()一樣，就能友善的從HashMap取值。
當然還有很多的問題，暫時就想到這些，有其他的歡迎大家交流補充。
4.總結
HashMap的工作原理
HashMap基于hashing原理，通過put()和get()方法儲存和擷取對象。
當擷取對象時，很關鍵的通過equals()來找到對應的鍵值對，避免了不同鍵産生相同hashcode的情況，當我們将鍵值對傳遞給put方法時，它會調用KEY的hashCode()方法計算hashcode,然後找到桶的位置來存儲對象。HashMap采用鍊位址法解決碰撞問題，如果發生碰撞，就存儲該對象在連結清單的下一節點處。
注意，HashMap實作不是同步的。如果多個線程同時通路一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。（結構上的修改是指添加或删除一個或多個映射關系的任何操作；僅改變與執行個體已經包含的鍵關聯的值不是結構上的修改。）這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在建立時完成這一操作，以防止對映射進行意外的非同步通路，
如：
Map m = Collections.synchronizedMap(new HashMap(…));