前言
HashMap可以說是我們?nèi)粘ｉ_發(fā)中特別經(jīng)常使用到的對象映射關(guān)系集合類了，本文將結(jié)合JDK1.8源碼從線程安全、數(shù)據(jù)結(jié)構(gòu)、初始化、擴容、增刪改查、特性總結(jié)等幾個部分去分析HashMap
線程安全
HashMap是非線程安全的，不支持并發(fā)。我們可以從它的數(shù)據(jù)迭代器中可以得知，當產(chǎn)生線程安全問題時會拋出拋出ConcurrentModificationException異常。內(nèi)部是通過一個modCount變量記錄集合的變化，在擴容與刪除及清空等操作都會將modCount自增，以此來標記集合的改變。
如何實現(xiàn)線程安全
1.通過Colletions.synchronizedMap獲取線程安全的Map對象
2.使用并發(fā)庫下的ConcurrentMap
數(shù)據(jù)結(jié)構(gòu)
哈希表（數(shù)據(jù)+單鏈表），結(jié)合了兩者的優(yōu)勢，采用拉鏈法解決哈希沖突。哈希沖突的常用解決方法包括拉鏈法和開發(fā)地址法，由于使用了鏈表鏈接沖突元素，那么證明它自然采用的是拉鏈法
image.png
初始化
提供了四個重載構(gòu)造方法，除了默認的無參構(gòu)造器外還可以指定初始容量以及初始集合內(nèi)容以及同時指定容量與加載因子。無參構(gòu)造器僅僅指定擴容因子為默認值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的擴容主要步驟如下：更新閥值 -> 構(gòu)建新的哈希桶 -> 將元素移動到新哈希桶中，正常情況下每次擴容后為原容量2，使得容量總是為2的n次冪。實際的擴容操作，首先是根據(jù)三種情況進行。第一種情況是此次擴容屬于首次擴容，如果舊閥值大于0（使用了兩個有參構(gòu)造器），則新容量即為舊閥值。第二種情況是此次擴容屬于首次擴容，該HashMap使用無參構(gòu)造器進行初始化，那么新容量為默認值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獲得，因此最后的結(jié)果也是2的n次冪
newCap = oldThr; // 新容量直接等于初始化的閥值
// 首次擴容，切初始化時使用的默認無參構(gòu)造器
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é)構(gòu)。如果存在哈希碰撞的情況，某個節(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個，轉(zhuǎn)化成了紅黑樹
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) {
// 結(jié)果==0表示處于低位
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 結(jié)果!=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，轉(zhuǎn)為紅黑樹）
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，轉(zhuǎn)為紅黑樹
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);// 回調(diào)
return null;
}
// 為LinkedHashMap提供的回調(diào)函數(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); // 刪除回調(diào)
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;
}
特性總結(jié)
HashMap采用數(shù)組+單鏈表結(jié)構(gòu)，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結(jié)果分布均勻，減少hash碰撞（2）擾動函數(shù)：避免取模時只關(guān)注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
