注意：HashMap的源碼本文僅分析JDK1.7，1.8版本的請參考： JDK1.8版本HashMap
JDK1.7版本HashMap
1 結構圖
HashMap由數組（本文後續以table表示）+ 連結清單構成。其本意是用table來存儲一個鍵值對（本文後續以Entry表示），然後可以通過key取hash值同時對數組長度取模，散列分布到數組每個下标下的時候，那取值時間複雜度将為O(1)，在最理想的情況下，就是數組一個下标上隻存一個Entry值。
但是天不如人願，并不存在一個如此優秀的Hash函數，讓每個Entry的key一定能散列分布在數組每個下标下，總是會出現如下情況：不同的key值，取hash值并取模後，數組下标值一樣，那這個時候就出現了Hash沖突。解決Hash沖突方法有挺多種的，而HashMap采用連結清單來解決，意思是，假如出現Hash沖突後，則在該下标下，形成一個單連結清單，存儲不同的Entry，那麼在查詢操作的時候，就需要對連結清單進行周遊，同時調用HashMap的key的equals方法，判斷其是否相等，相等則傳回該Entry，這也就是HashMap為什麼要求key對象一定要實作hashCode方法和equals方法的原因。
2 繼承關系
我們來看下HashMap的繼承關系圖：
左邊實作的Cloneable接口和Serializable接口是為了實作克隆和序列化功能，非本文重點關注對象，請忽略。HashMap主要繼承父類AbstractMap，而父類實作了Map接口。
2.1 Map接口
下面是Map接口提供的方法：
可以看到Map還有一個内部接口Entry，Entry就是代表鍵值對，一個key和一個vale值。
2.2 AbstractMap抽象類（非重點父類，請稍微浏覽即可）
AbstractMap對于HashMap的作用，僅僅是提供了keySet 和values 變量。而其他的Map方法都在HashMap中重寫了一遍。是以請看淡AbstractMap抽象父類。
AbstractMap.java（省略了其實作的方法）：
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
...
public abstract Set<Entry<K,V>> entrySet();
以上兩個方法是AbstractMap未實作Map接口的方法。其它方法，AbstractMap基本都實作了。
2.3 HashMap類
HashMap雖然繼承了AbstractMap類，但實際上，它基本上重寫了AbstractMap類實作Map接口的方法，換句話說，他表面上繼承AbstractMap，但暗地裡把它實作的方法都重寫了一遍，絲毫不留情面。其隻使用了父類的兩個成員變量keySet和values
2.3.1 字段
/**
* 預設初始化容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量值
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 預設負載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 空table
*/
static final Entry<?, ?>[] EMPTY_TABLE = {};
/**
* table，用來存放鍵值對，鍵值對可以單個值，也可以是一個連結清單
*/
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
/**
* 大小
*/
transient int size;
/**
* 門檻值，擴容的主要判斷條件之一
*/
int threshold;
/**
* 負載因子
*/
final float loadFactor;
/**
* 結構更改次數的統計，增、删都會加1。也是快速失敗的觸發依據，後面HashIterator會介紹如何使用該值
*/
transient int modCount;
/**
* 預設備選hash門檻值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* 注意、注意、注意：
* 這兩個成員變量來自父類AbstractMap，由于其為default類型，在不同包将通路不到，是以在此聲明，以此代替
* 由于keySet、value在父類中的keySet()、values()、clone()方法中用到，而HashMap這幾個方法全部重寫了，是以不會影響使用
*/
transient volatile Set<K> keySet = null;
transient volatile Collection<V> values = null;
2.3.2 構造器
最重要的構造器：
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);
// 初始化負載因子和門檻值
// 注意：門檻值在這裡并非穩定值，在put方法進行初始化後，會等于數組長度*負載因子的值
this.loadFactor = loadFactor;
threshold = initialCapacity;
// init是空實作，忽略
init();
}
接收容量的構造器：
// 接收容量的構造器，并将負載因子設定為預設的0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
最常用的構造器，無參構造：
// 用得最多的構造器，預設容量16、負載因子0.75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
接收一個map的構造器：
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
2.3.3 get(Object key)方法的實作原理
// 取值
public V get(Object key) {
// 由于HashMap支援一個null值，因為key為null的時候，作特殊處理
// null的值固定在table[0]下
if (key == null)
return getForNullKey(); // 代碼1
// 取entry
Entry<K, V> entry = getEntry(key); // 代碼2
return null == entry ? null : entry.getValue();
}
由于HashMap支援key=null，而對于key=null的情況，由代碼1進行特殊處理，下面是其對應邏輯：
// 取key=null的值
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
周遊table[0]下标下的值，由于key=null的特殊值，固定會放在table[0]下。假如table[0]下的結點，有key為null的，則将該值傳回。
當key不為null時，由代碼2取key對應的Entry，下面看看getEntry的實作邏輯：
// 擷取鍵值對
final Entry<K, V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 計算key的hash值
int hash = (key == null) ? 0 : hash(key);
// 周遊某個下标下的連結清單（如果是連結清單的話）
for (Entry<K, V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果key的hash相同 && （key相同或者key的equals方法的值相同）則傳回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
該方法分兩步，首先根據key，計算該key對應的下标值。
第二步，周遊下标對應的連結清單，然後分别判斷其hash值是否相等且（key相同或者key的equals方法相等）則将該值傳回。
2.3.4 put(K key, V value)方法的實作原理
// 添加值
public V put(K key, V value) {
// 如果table為空，則根據門檻值初始化table的值。
// 由于HashMap是延遲初始化的，構造器隻給table指派為EMPTY_TABLE
if (table == EMPTY_TABLE) {
inflateTable(threshold); // 代碼3
}
// 特殊處理key=null的情況
if (key == null)
return putForNullKey(value); // 代碼4
// 計算hash值
int hash = hash(key); // 代碼5
// 根據hash值與table長度，取模（實際為與操作）得到下标值
int i = indexFor(hash, table.length); // 代碼6
// 判斷在目前下标下的連結清單有沒有相同key值的Entry，有則覆寫，并将舊值傳回
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 假如沒有相同key值，則将為HashMap增加一個新值
// 由于結構發生改變，是以modCount需要+1
modCount++;
// 添加新的Entry值
addEntry(hash, key, value, i); // 代碼7
return null;
}
從上面構造器可以發現，HashMap是延遲初始化的，最開始的時候，給table指派了一個EMPTY_TABLE，但真正将值設定進來的時候，才去申請capacity對應的空間。
代碼3，當table==EMPTY_TABLE的時候，将執行初始化操作，下面代碼看看其如何初始化的：
// 初始化table的值
private void inflateTable(int toSize) {
// 将容量控制為2的n次方
int capacity = roundUpToPowerOf2(toSize);
// 門檻值載不大于MAXIMUM_CAPACITY+1的情況下，值等于capacity*loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 根據容量，建立Entry數組
table = new Entry[capacity];
// 初始化hash種子，可能會對hashSeed字段指派，hashSeed可能會影響hash(Object key)方法的計算，下面會講述
initHashSeedAsNeeded(capacity);
}
回到put方法的代碼，在完成table值的初始化後，往下執行到代碼4，會對key==null的情況進行特殊處理：
// 特殊處理key=null的值，将其放在table[0]下
private V putForNullKey(V value) {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 添加鍵值對
addEntry(0, null, value, 0);
return null;
}
如果key！=null的時候，計算key對象的hash值，并取模得到key對應table的下标值，下面統一對于代碼代碼5和代碼6進行分析：
代碼5：
// 對key值作hash運算
final int hash(Object k) {
// hashSeed在大部分情況下是0，當容量超過2147483647後，可能會變為一個随機hashSeed（該情況不做分析）
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
// h為0的時候，下面異或操作結果将是 右邊操作數的值，則下面相當于h = k.hashCode()
h ^= k.hashCode();
// 以下代碼使用了擾動計算，異或了高位+低位的值，避免高位沒有參與計算，導緻在與table-1做與運算的時候，無法散列在各個下标值下
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
在hashSeed不為0的時候且key為String類型的時候，可能會調用Hashing.stringHash32進行特殊處理，來的到hash值。
以上情況不滿足的時候，将key的hashCode指派給h，然後通過異或h的多個比特位進行計算。這裡用了擾動計算，将hashCode的每個值都用到計算中，以支援散列分布。
代碼6：
// 擷取目前key下落在table哪個下标，用與運算，等效取模，但性能比取模快
static int indexFor(int h, int length) {
// 首先，length要求為2的n次方，2的n次方-1的時候，得到一個二進制是全1的值
// 當h的值去與操作一個全1的值，等效于對 %length
// 那為什麼不用取模操作，而要與操作呢？因為與操作效率比取模操作速度快很多
return h & (length - 1);
}
回到put方法，在計算取得下标值後，将判斷目前添加的鍵值對key是否已存在，開始周遊儲存在該下标下的連結清單，當結點的hash值相等且（key相同或者key的equals方法相等）則覆寫該值，并将舊值傳回。
如果以上情況都不滿足，則說明目前添加的Entry既不是key==null，又不是key存在的情況。那麼開始新增一個鍵值對，然後傳回null。該操作将可能觸發擴容。
代碼7：
// 添加新的鍵值對
void addEntry(int hash, K key, V value, int bucketIndex) {
// 判斷目前容器大小是否大于等于門檻值 && 目前table下标的值存在值，将進行擴容操作
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴容為目前table長度的兩倍
resize(2 * table.length); // 代碼8
// 重新計算擴容後，目前key将位于table的哪個下标
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 建立鍵值對
createEntry(hash, key, value, bucketIndex);
}
代碼8的擴容方法，在下面講述，将解析其為什麼在多線程環境下會形成環路。
2.3.5 resize()方法原理及多線程環境下環路的形成原因
// 擴容方法，多線程不安全，其他方法也是多線程不安全，但是resize問題比較嚴重
// 可能形成環形連結清單，造成死循環，CPU100%
void resize(int newCapacity) {
// 暫存舊的table
Entry[] oldTable = table;
// 暫存舊table長度
int oldCapacity = oldTable.length;
// 假如舊的table長度等于最大容量，将不做擴容操作
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 根據新容量，建立新table
Entry[] newTable = new Entry[newCapacity];
// 執行table上面值得轉移，将oldTable上面的值轉移到newTable，會重新hash并取模來判斷新的下标值
// 多線程環境下，下面方法可能會産生環形連結清單，造成死循環
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将newTable 替換為table
table = newTable;
// 重新計算門檻值 ，控制門檻值不能超過MAXIMUM_CAPACITY+1
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
在進行newCapacity（新容量）的合法值校驗完成後，建立一個新的Entry數組，然後開始調用transfer進行元素的轉移，意思就是把舊數組上面的元素值，進行重新hash并取模，确定其在新數組的下标，我們來看看其如何實作：
// 轉移值
void transfer(Entry[] newTable, boolean rehash) {
// 擷取新的容量
int newCapacity = newTable.length;
// 周遊table的Entry
for (Entry<K, V> e : table) {
// 周遊連結清單（如果是連結清單的話）
while (null != e) {
// 假如線程A取到next，然後時間片用完，CPU切換到線程B繼續執行連結清單值轉移操作，并執行完畢
// 那麼線程A有了CPU時間片後，繼續執行，此時再觸發轉移值操作，很容易會形成環形連結清單，造成死循環
Entry<K, V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根據hash值取模，得到在新table的下标值
int i = indexFor(e.hash, newCapacity);
// 采用頭插法，将目前節點下一個節點指向newTable目前下标的值
e.next = newTable[i];
// 将目前節點作為newTable的頭結點
newTable[i] = e;
// 将下一個節點指派給下一輪循環的結點，繼續往下執行循環
e = next;
}
}
}
這裡注意一點是，newTable是作為方法參數傳遞進來，每個線程都會建立一個新的newTable，其值是線程私有，而線程不安全的變量，其實是table裡面的Entry。具體如何成環路的場景分析，請參考下面的示例圖。
圖檔位址： https://www.processon.com/diagraming/5e06f27ce4b0125e2924abba
2.3.5 keySet()方法的實作原理
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
上述代碼為keySet實作原理，很簡單，就是在keySet為null的時候，new了一個KeySet對象，那下面我們看看KeySet對象：
private final class KeySet extends AbstractSet<K> {
// 實作Set的疊代方法
public Iterator<K> iterator() {
return newKeyIterator();
}
// 大小值跟HashMap大小一緻
public int size() {
return size;
}
// 調用HashMap的containsKey方法
public boolean contains(Object o) {
return containsKey(o);
}
// 調用HashMap的removeEntryForKey方法
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
// 調用HashMap的clear方法
public void clear() {
HashMap.this.clear();
}
}
由上述代碼看出，其具體實作，全都依賴于HashMap。這裡可能有個困惑的點，就是我們看到一個Set對象，就會想當然覺得裡面的元素都是存儲在Set對象裡面，其實不然。KeySet對象的值，如元素的值，集合大小等資訊，其實都是用着HashMap的成員域。如果你擷取到KeySet對象後，調用了remove方法，實際上會改變該key對應在HashMap中的Entry。
我們分析一下iterator方法：
public Iterator<K> iterator() {
// 調用疊代器方法時，會建立一個新的Key疊代器
return newKeyIterator();
}
調用HashMap的方法newKeyIterator建立一個KeyIterator對象。
Iterator<K> newKeyIterator() {
// 每次調用都會建立一個新的KeyIterator
return new KeyIterator();
}
KeyIterator 類：
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
其next方法是調用父類HashIterator的nextEntry方法擷取一個Entry，然後再擷取Entry的key，這跟ValueIterator的實作是對應的。
下面我們看看nextEntry方法的具體實作：
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // 需要傳回的下一個Entry
int expectedModCount; // 快速失敗的判斷依據，如果該值不等于HashMap的modCount，将抛出ConcurrentModificationException
int index; // 目前疊代下标
Entry<K,V> current; // 目前Entry
HashIterator() {
// 将HashMap結構修改次數儲存一個副本，下面疊代的時候，如果兩個值不相等，将抛出并發修改異常（其實不太準确，下面案例分析）ConcurrentModificationException
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
// 周遊table，直到定位到table不為null的值
while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
// 判斷在執行疊代器期間，HashMap有沒有對結構進行修改
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
從HashIterator的代碼我們可以看出，在其成員域中維護了
3 源碼
下面是源碼，篇幅較長，上文已将重要方法都講解了，如果沒有興趣，可以不看。篇幅長，是以可能會比較卡！
package hashmap1_7;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.util.*;
/**
* JDK1.7版本，加入個人一些了解、注釋
* 當使用該類的時候，記得要把項目的JDK版本切換為1.7，否則會報錯
* copy form jdk1.7
* @author wzj
* 2019/12/28
*/
public class HashMap<K, V>
extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {
/**
* 預設初始化容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量值
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 預設負載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 空table
*/
static final Entry<?, ?>[] EMPTY_TABLE = {};
/**
* table，用來存放鍵值對，鍵值對可以單個值，也可以是一個連結清單
*/
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
/**
* 大小
*/
transient int size;
/**
* 門檻值，擴容的主要判斷條件之一
*/
int threshold;
/**
* 負載因子
*/
final float loadFactor;
/**
* 結構更改次數的統計，增、删都會加1。也是快速失敗的觸發依據，後面HashIterator會介紹如何使用該值
*/
transient int modCount;
/**
* 預設備選hash門檻值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* 注意、注意、注意：
* 這兩個成員變量來自父類AbstractMap，由于其為default類型，在不同包将通路不到，是以在此聲明，以此代替
* 由于keySet、value在父類中的keySet()、values()、clone()方法中用到，而HashMap這幾個方法全部重寫了，是以不會影響使用
*/
transient volatile Set<K> keySet = null;
transient volatile Collection<V> values = null;
private static class Holder {
/**
* 備選hash門檻值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
// 從系統擷取門檻值的配置，一般沒有配置
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
// 給門檻值指派
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// 對門檻值合法性進行校驗
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch (IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
// 最終給備選門檻值設定值
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
/**
* hash種子
*/
transient int hashSeed = 0;
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);
// 初始化負載因子和門檻值
// 注意：門檻值在這裡并非穩定值，在put方法進行初始化後，會等于數組長度*負載因子的值
this.loadFactor = loadFactor;
threshold = initialCapacity;
// init是空實作，忽略
init();
}
// 接收容量的構造器，并将負載因子設定為預設的0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 用得最多的構造器，預設容量16、負載因子0.75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 接收一個map的構造器
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
// 根據傳入的值，得到一個接近的2的n次方數
private static int roundUpToPowerOf2(int number) {
// 以下操作分三步
// 1、判斷是否超過容量最大值，超過則取容量最大值
// 2、判斷是否小于最小值，小于則取最小值1
// 3、當上述情況不符合，則說明值在正常範圍
// 讓該值-1再乘以2，然後調用Integer的highestOneBit方法，向下取一個最近的2的n次方值
// 如：1取1(2^0)、 2-3取2(2^1)、 4-7取4(2^2) 、8-15取8(2^3) 、16-31取16(2^4)
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 初始化table的值
private void inflateTable(int toSize) {
// 将容量控制為2的n次方
int capacity = roundUpToPowerOf2(toSize);
// 門檻值載不大于MAXIMUM_CAPACITY+1的情況下，值等于capacity*loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 根據容量，建立Entry數組
table = new Entry[capacity];
// 初始化hash種子，可能會對hashSeed字段指派，hashSeed可能會影響hash(Object key)方法的計算，下面會講述
initHashSeedAsNeeded(capacity);
}
void init() {
}
// 初始化哈希掩碼值。我們将初始化推遲到真正需要的時候。
final boolean initHashSeedAsNeeded(int capacity) {
// 第一次進入該方法，currentAltHashing一直為false
boolean currentAltHashing = hashSeed != 0;
// 隻有等到容量值超過2147483647，則會觸發給hashSeed指派
// sun.misc.VM.isBooted為虛拟機啟動後一直為true && 容量大于最大值
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
// 假如useAltHashing為true，則将hashSeed設定為随機産生的HashSeed
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
// 對key值作hash運算
final int hash(Object k) {
// hashSeed在大部分情況下是0，當容量超過2147483647後，可能會變為一個随機hashSeed（該情況不做分析）
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
// h為0的時候，下面異或操作結果将是 右邊操作數的值，則下面相當于h = k.hashCode()
h ^= k.hashCode();
// 以下代碼使用了擾動計算，異或了高位+低位的值，避免高位沒有參與計算，導緻在與table-1做與運算的時候，無法散列在各個下标值下
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 擷取目前key下落在table哪個下标，用與運算，等效取模，但性能比取模快
static int indexFor(int h, int length) {
// 首先，length要求為2的n次方，2的n次方-1的時候，得到一個二進制是全1的值
// 當h的值去與操作一個全1的值，等效于對 %length
// 那為什麼不用取模操作，而要與操作呢？因為與操作效率比取模操作速度快很多
return h & (length - 1);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// 取值
public V get(Object key) {
// 由于HashMap支援一個null值，因為key為null的時候，作特殊處理
// null的值固定在table[0]下
if (key == null)
return getForNullKey();
// 取entry
Entry<K, V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
// 取key=null的值
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
// 擷取鍵值對
final Entry<K, V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 計算key的hash值
int hash = (key == null) ? 0 : hash(key);
// 周遊某個下标下的連結清單（如果是連結清單的話）
for (Entry<K, V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果key相同且值相同，則傳回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
// 添加值
public V put(K key, V value) {
// 如果table為空，則根據門檻值初始化table的值。
// 由于HashMap是延遲初始化的，構造器隻給table指派為EMPTY_TABLE
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 特殊處理key=null的情況
if (key == null)
return putForNullKey(value);
// 計算hash值
int hash = hash(key);
// 根據hash值與table長度，取模（實際為與操作）得到下标值
int i = indexFor(hash, table.length);
// 判斷在目前下标下的連結清單有沒有相同key值的Entry，有則覆寫，并将舊值傳回
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 假如沒有相同key值，則将為HashMap增加一個新值
// 由于結構發生改變，是以modCount需要+1
modCount++;
// 添加新的Entry值
addEntry(hash, key, value, i);
return null;
}
// 特殊處理key=null的值，将其放在table[0]下
private V putForNullKey(V value) {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
// 擴容方法，多線程不安全，其他方法也是多線程不安全，但是resize問題比較嚴重
// 可能形成環形連結清單，造成死循環，CPU100%
void resize(int newCapacity) {
// 暫存舊的table
Entry[] oldTable = table;
// 暫存舊table長度
int oldCapacity = oldTable.length;
// 假如舊的table長度等于最大容量，将不做擴容操作
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 根據新容量，建立新table
Entry[] newTable = new Entry[newCapacity];
// 執行table上面值得轉移，将oldTable上面的值轉移到newTable，會重新hash并取模來判斷新的下标值
// 多線程環境下，下面方法可能會産生環形連結清單，造成死循環
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将newTable 替換為table
table = newTable;
// 重新計算門檻值 ，控制門檻值不能超過MAXIMUM_CAPACITY+1
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 轉移值
void transfer(Entry[] newTable, boolean rehash) {
// 擷取新的容量
int newCapacity = newTable.length;
// 周遊table的Entry
for (Entry<K, V> e : table) {
// 周遊連結清單（如果是連結清單的話）
while (null != e) {
// 假如線程A取到next，然後時間片用完，CPU切換到線程B繼續執行連結清單值轉移操作，并執行完畢
// 那麼線程A有了CPU時間片後，繼續執行，此時再觸發轉移值操作，很容易會形成環形連結清單，造成死循環
Entry<K, V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根據hash值取模，得到在新table的下标值
int i = indexFor(e.hash, newCapacity);
// 采用頭插法，将目前節點下一個節點指向newTable目前下标的值
e.next = newTable[i];
// 将目前節點作為newTable的頭結點
newTable[i] = e;
// 将下一個節點指派給下一輪循環的結點，繼續往下執行循環
e = next;
}
}
}
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
if (table == EMPTY_TABLE) {
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
}
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
// 移除key方法
public V remove(Object key) {
// 移除key對應的Entry
Entry<K, V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
// 移除key對應的Entry
final Entry<K, V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
// 根據hash值和table長度取模，計算目前key所在table的下标
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
// 擷取下标所在頭結點
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
// 周遊連結清單
while (e != null) {
Entry<K, V> next = e.next;
Object k;
// 假如hash值相等 && key的equals方法也相同，則将執行移除
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
// 結構變化自增
modCount++;
// 大小減1
size--;
// 判斷目前key是否為頭結點，如果是，需要将next做為新的頭結點，放在table[i]下
// 為什麼說prev==e就是key為頭結點呢，因為prev==e隻有在第一次判斷的時候才會相等，下面的prev=e和e=next會改變其值了
if (prev == e)
table[i] = next;
// 目前key對應的值非頭結點，則将目前結點的next指派給上個結點的next，因為準備删除目前結點
else
prev.next = next;
// 空方法，忽略
e.recordRemoval(this);
return e;
}
// 給下一輪循環的結點指派，向下周遊結點
prev = e;
e = next;
}
return e;
}
final Entry<K, V> removeMapping(Object o) {
if (size == 0 || !(o instanceof Map.Entry))
return null;
Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while (e != null) {
Entry<K, V> next = e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
if (e.value == null)
return true;
return false;
}
public Object clone() {
HashMap<K, V> result = null;
try {
result = (HashMap<K, V>) super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
// 鍵值對，其在維護key和value的同時，還會維護next（下一個Entry）和hash（key的hash值）
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap<K, V> m) {
}
void recordRemoval(HashMap<K, V> m) {
}
}
// 添加新的鍵值對
void addEntry(int hash, K key, V value, int bucketIndex) {
// 判斷目前容器大小是否大于等于門檻值 && 目前table下标的值存在值，将進行擴容操作
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴容為目前table長度的兩倍
resize(2 * table.length);
// 重新計算擴容後，目前key将位于table的哪個下标
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 建立鍵值對
createEntry(hash, key, value, bucketIndex);
}
// 建立鍵值對
void createEntry(int hash, K key, V value, int bucketIndex) {
// 擷取指定下标的元素，作為新結點的next，然後将新結點作為table[index]的頭結點
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 大小+1
size++;
}
// Hash疊代器，KeyIterator和ValueIterator的父類
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K, V> next; // 需要傳回的下一個Entry
int expectedModCount; // 快速失敗的判斷依據，如果該值不等于HashMap的modCount，将抛出ConcurrentModificationException
int index; // 目前疊代下标
Entry<K, V> current; // 目前Entry
HashIterator() {
// 将HashMap結構修改次數儲存一個副本，下面疊代的時候，如果兩個值不相等
// 将抛出并發修改異常（其實不太準确，下面案例分析）ConcurrentModificationException
expectedModCount = modCount;
if (size > 0) {
// 周遊table，直到定位到table不為null的值
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null) ;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K, V> nextEntry() {
// 判斷在執行疊代器期間，HashMap有沒有對結構進行修改
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K, V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
public Map.Entry<K, V> next() {
return nextEntry();
}
}
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
// 鍵值對集合
private transient Set<Map.Entry<K, V>> entrySet = null;
// 擷取key集合
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
// key集合類，特點：其成員本身不儲存元素值，而是在每次疊代的時候，去取HashMap的table上的值
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
// 擷取值得集合
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
// value集合類，特點：其成員本身不儲存元素值，而是在每次疊代的時候，去取HashMap的table上的值
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
public Set<Map.Entry<K, V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K, V>> entrySet0() {
Set<Map.Entry<K, V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
// 鍵值對集合類
private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
public Iterator<Map.Entry<K, V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K, V> e = (Map.Entry<K, V>) o;
Entry<K, V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
// 序列化
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
if (table == EMPTY_TABLE) {
s.writeInt(roundUpToPowerOf2(threshold));
} else {
s.writeInt(table.length);
}
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {
for (Map.Entry<K, V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
// 反序列化
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// set other fields that need values
table = (Entry<K, V>[]) EMPTY_TABLE;
// Read in number of buckets
s.readInt(); // ignored.
// Read number of mappings
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
// capacity chosen by number of mappings and desired load (if >= 0.25)
int capacity = (int) Math.min(
mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
// allocate the bucket array;
if (mappings > 0) {
inflateTable(capacity);
} else {
threshold = capacity;
}
init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the hashmap1_7.HashMap
for (int i = 0; i < mappings; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// 傳回容量
int capacity() {
return table.length;
}
// 傳回負載因子
float loadFactor() {
return loadFactor;
}
}
https://gitee.com/lao-dubbo/source-code