前言
HashMap可以說是我們日常開發(fā)中特別經常使用到的對象映射關系集合類了摩桶，本文將結合JDK1.8源碼從線程安全烁试、數(shù)據(jù)結構犀暑、初始化驯击、擴容、增刪改查母怜、特性總結等幾個部分去分析HashMap
線程安全
HashMap是非線程安全的余耽，不支持并發(fā)缚柏。我們可以從它的數(shù)據(jù)迭代器中可以得知苹熏，當產生線程安全問題時會拋出拋出ConcurrentModificationException異常。內部是通過一個modCount變量記錄集合的變化币喧，在擴容與刪除及清空等操作都會將modCount自增轨域，以此來標記集合的改變。
如何實現(xiàn)線程安全
1.通過Colletions.synchronizedMap獲取線程安全的Map對象
2.使用并發(fā)庫下的ConcurrentMap
數(shù)據(jù)結構
哈希表（數(shù)據(jù)+單鏈表）杀餐，結合了兩者的優(yōu)勢干发，采用拉鏈法解決哈希沖突。哈希沖突的常用解決方法包括拉鏈法和開發(fā)地址法史翘，由于使用了鏈表鏈接沖突元素枉长，那么證明它自然采用的是拉鏈法
image.png
初始化
提供了四個重載構造方法，除了默認的無參構造器外還可以指定初始容量以及初始集合內容以及同時指定容量與加載因子琼讽。無參構造器僅僅指定擴容因子為默認值0.75必峰；指定集合時澤通過entrySet遍歷將每個item指定putVal進行添加；容量指的是數(shù)組長度length的大小
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) { ... }
public HashMap(int initialCapacity, float loadFactor) { ... }
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 表為null 進行初始化
if (table == null) { // pre-size
// 計算新的擴容閥值
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY); // 擴容閥值越界判斷
if (t > threshold) // 閥值初始化钻蹬，首次的時候閥值=容量
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
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);
}
}
}
// 初始化容量吼蚁，移位操作比符號運算效率更高
// 此處tableSizeFor最后返回的有效位都是1，最后n+1恒為2的n次冪问欠。先注意下肝匆，后面會提到。也就是說最后容量result總是>=cap
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
擴容
HashMap的擴容主要步驟如下：更新閥值 -> 構建新的哈希桶 -> 將元素移動到新哈希桶中顺献，正常情況下每次擴容后為原容量2旗国，使得容量總是為2的n次冪。實際的擴容操作注整，首先是根據(jù)三種情況進行能曾。第一種情況是此次擴容屬于首次擴容嫁怀，如果舊閥值大于0（使用了兩個有參構造器），則新容量即為舊閥值借浊。第二種情況是此次擴容屬于首次擴容塘淑，該HashMap使用無參構造器進行初始化，那么新容量為默認值16蚂斤，閥值為160.75存捺。第三種情況，此處擴容非首次擴容曙蒸，那么新容量為舊容量2捌治，新閥值為舊閥值2
// 擴容函數(shù)
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) { // 舊容量大于0，屬于非首次擴容情況
if (oldCap >= MAXIMUM_CAPACITY) { // 越界保護
threshold = Integer.MAX_VALUE;
return oldTab; // 無法繼續(xù)擴容
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 新閥值為舊閥值*2
}
// 首次擴容纽窟，且初始化時指定了閥值
else if (oldThr > 0) // initial capacity was placed in threshold
// 由于初始化的閥值通過tableSizeFor獲得肖油，因此最后的結果也是2的n次冪
newCap = oldThr; // 新容量直接等于初始化的閥值
// 首次擴容，切初始化時使用的默認無參構造器
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // 新容量為默認容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新閥值為默認容量*默認加載因子臂港，即16*0.75
}
// 指定新閥值為新容量*加載因子
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 以下開始進行數(shù)據(jù)遷移
if (oldTab != null) {
// 遍歷節(jié)點森枪，注意哈希表結構。如果存在哈希碰撞的情況审孽，某個節(jié)點可能還有鏈表節(jié)點县袱。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 臨時存儲目標節(jié)點
oldTab[j] = null; // 舊表對應位置元素置空，方便gc
// next為null表示該節(jié)點沒有hash碰撞找到下標賦值佑力，采用hash & (newCap - 1)式散，使用&與操作來代替%取模操作，提高效率打颤。為了使&能夠達到更加均勻的分布暴拄，減少hash碰撞，因此newCap的取值總是2的n次方
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; // 放到新表
// 如果發(fā)生過哈希碰撞 ,而且是節(jié)點數(shù)超過8個编饺，轉化成了紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 如果發(fā)生過哈希碰撞乖篷，節(jié)點數(shù)未超過8個
// 存在碰撞的話，那么對于的鏈表上的節(jié)點有兩種可能
// 第一種反肋，hash與新容量取模后小于舊容量那伐，即值與hash與舊容量取模一樣（低位）
// 第二種，hash與新容量取模后大于舊容量石蔗，即值為hash與舊容量取模 + 舊容量（高位）
else { // preserve order
// 低位鏈表頭尾節(jié)點
Node<K,V> loHead = null, loTail = null;
// 高位鏈表頭尾節(jié)點
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next; // 操作節(jié)點
do {
next = e.next; // 操作節(jié)點賦值
// 通過hash與舊容量的與操作是否為0（高效）（注意是oldCap而不是olcCap-1）
// 判斷與新容量取模后的值是否大于舊容量
if ((e.hash & oldCap) == 0) {
// 結果==0表示處于低位
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 結果!=0表示處于高位
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null); // while循環(huán)罕邀，處理鏈表上所有節(jié)點
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; // 放到新表中
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; // 放到新表中
}
}
}
}
}
return newTab;
}
Hash處理
獲取key的Hash值時不是直接返回其hashCode方法的值，而是通過“擾動函數(shù)”進行處理后返回养距。hashCode()是int類型诉探，取值范圍是40多億，只要哈希函數(shù)映射的比較均勻松散棍厌，碰撞幾率是很小的肾胯。但是由于HashMap的哈希桶長度要遠遠小于hashCode()竖席，因為一般采用取余的方式獲取key對應的桶下標，在HashMap中采用與操作來實現(xiàn)取余敬肚，如果直接使用hashCode()會忽略高位毕荐，導致碰撞幾率增大。擾動函數(shù)就是為了解決hash碰撞的艳馒。它會綜合hash值高位和低位的特征憎亚，并存放在低位，因此在與運算時弄慰，相當于高低位一起參與了運算第美，以減少hash碰撞的概率
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
增改操作
若數(shù)組為空則進行擴容，獲取index下標陆爽，若對應位置上沒有元素則直接賦值什往，若有元素先判斷是否key一致（hash與equals均一致），一致則進行覆蓋慌闭。不一致則表示發(fā)生碰撞别威，而HashMap采用拉鏈法解決碰撞，在對應鏈表上需要是否有key一致的元素贡必，有則覆蓋兔港，沒有則在末尾插入節(jié)點庸毫。（會修改modCount變量）最后仔拟，按需擴容。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// JDK 1.8 新增方法飒赃，若對應key的value之前存在利花，則不覆蓋
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
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;
// index位置沒有元素，直接賦值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// index上元素key與目標key一致
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 紅黑樹（當鏈表節(jié)點數(shù)大于8载佳，轉為紅黑樹）
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 鏈表節(jié)點數(shù)小于8
for (int binCount = 0; ; ++binCount) {
// 到末尾節(jié)點炒事，仍沒有找到key一致的節(jié)點
// 將此元素插入到該鏈表末尾
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 當鏈表節(jié)點數(shù)大于8，轉為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 鏈表中存在key一致的節(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 上述過程找到了key一致的元素蔫慧，修改value
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 是否覆蓋value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);// 回調
return null;
}
// 為LinkedHashMap提供的回調函數(shù)
void afterNodeAccess(Node<K,V> p) { } // 訪問（查）
void afterNodeInsertion(boolean evict) { } // 插入（增）
void afterNodeRemoval(Node<K,V> p) { } // 移除（刪）
刪操作
根據(jù)key為條件或者以key-value為條件挠乳。首先找到key一致元素（鏈表頭，或者鏈表中）姑躲，然后從數(shù)組或鏈表中剔除睡扬。修改modCount與size
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
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) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 通過index找到key相同的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 發(fā)生碰撞，在對應鏈表中尋找
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; // P為被刪除前一個（當目標即為第一個時p==node）
} 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) // 鏈表首個元素卖怜，數(shù)組位置指向其next
tab[index] = node.next;
else
p.next = node.next; // p.next跨過目標元素
++modCount;
--size;
afterNodeRemoval(node); // 刪除回調
return node;
}
}
return null;
}
查：通過hash去查找元素value
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
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) > 0 &&
(first = tab[(n - 1) & 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 {
// key一致（hash相等，equals成立）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null; // 沒找到
}
// 雙層for：數(shù)字 + 鏈表
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
無序性
從HashIterator類中我們可以看出元素的遍歷是從哈希桶從低到高阐枣，鏈表從前到后
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
......
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
特性總結
HashMap采用數(shù)組+單鏈表結構马靠，key與value均可為null
（在JDK1.7中專門有個HashMapEntry對象用于存儲key為null的元素奄抽，而JDK1.8中則是針對key==null的情況返回hash為0來進行實現(xiàn)）
HashMap中的高效運算：（1）通過&來進行取模，hash&(cap - 1)（2）在舊元素拷貝到新的哈希桶中甩鳄，通過&進行高低位判斷逞度，hash&oldCap
HashMap中的碰撞優(yōu)化：（1）哈希桶的容量總是為2的n次方，為了讓hash結果分布均勻妙啃，減少hash碰撞（2）擾動函數(shù)：避免取模時只關注hashCode低位第晰，減少hash碰撞，讓高低位同時參數(shù)hash計算彬祖。hash = (h = key.hashCode()) ^ h >>> 16
image.gif
HashMap與HashTable的區(qū)別
HashTable是線程安全的茁瘦，且不允許key、value是null
HashTable默認容量是11
HashTable是直接使用key的hashCode()作為hash值
HashTable取哈希桶下標是直接用模運算%.（因為其默認容量也不是2的n次方储笑，所以也無法用位運算替代模運算）
擴容時甜熔，新容量是原來的2倍+1。int newCapacity = (oldCapacity << 1) + 1
