一、HashMap主要參數及其含義
這部分內容網上博客有很多，但在此處還是列舉一下：
/**
HashMap的初始容量，這邊我們看到默認是16，可根據自身需求進行指定，如果是一個合適的值可避
免擴容操作帶來的性能損耗
**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* HashMap的最大容量 我們看到相當于Integer整形的最大值
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 加載因子，我個人更喜歡稱之為負載因子 Hash桶內元素個數達到容量*負載因子時進行擴容操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*HashMap的樹化閾值，jdk1.8后引入紅黑樹來優化之前由于鏈表過長帶來性能損耗的問題
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* HashMap的解樹化閾值，jdk1.8通過鏈表高低位巧妙的解決1.7死鎖問題，同時如果長度小于此值則進
行解樹化
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* HashMap的最小樹化容量 其實并不一定是鏈表長度達到8進行擴容，容量如果沒有64 會優先進行擴容
這一點下面會說明
*/
static final int MIN_TREEIFY_CAPACITY = 64;
二、put方法
我們可以看到，put方法其實調用了putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
來看一下putVal方法，這里面比較關鍵，我盡可能一行一行解釋。首先，上面的注解寫明了方法的參數，第一個很好理解，對key做hash之后的hash值，第二個和第三個參數分別是key和value，第四個參數如果為true，則不覆蓋已有的key。這邊類似于redis的setNx命令，如果你用過redis，那么肯定很好理解；最后一個參數我們這邊不做講解，是提供給子類LinkedHashMap使用的。
/**
* 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;
//首先看一下table是否為空，長度是否為0，如果是的話，對hash表進行擴容操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//這里的n是擴容后的hash表長度，（n-1）& hash相當于對hash進行取余操作，只不過位運算
//速度上更快，這里不得不佩服大師的智慧
if ((p = tab[i = (n - 1) & hash]) == null)
//如果數組該位置為空的話，就新建一個node節點直接放在那個位置
tab[i] = newNode(hash, key, value, null);
else {
//以下走的都是數組對應位置不為空的邏輯
Node<K,V> e; K k;
//這里的p是上面if獲取的鏈表對應位置的節點，如果和我們新加入的key相等的話，則將該節點
//保存到 上面聲明的e節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//否則如果p節點是紅黑樹節點的話，就走對應樹節點插入邏輯
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//這個else理解一下，既不是key相等，也不是樹節點，那是什么呢？聰明的你應該能想到
//該位置已有節點，key不相同，且可能為長度大于1的鏈表
else {
//這邊是個死循環，其實目的是為了獲得鏈表長度binCount
for (int binCount = 0; ; ++binCount) {
//如果該位置下一個節點為空，則走此判斷
if ((e = p.next) == null) {
//將當前插入的節點掛在后面
p.next = newNode(hash, key, value, null);
//如果binCount大于樹化的閾值，則走樹化邏輯
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//跳出循環
break;
}
//如果便利鏈表到某個位置，該節點的key和我們插入的key相等，則跳出循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//把e賦值給p方便便利鏈表，這邊很好理解
p = e;
}
}
//這里對應上面的判斷鏈表中已經找到相同key的情況，否則e==null，會插入新節點到鏈表尾
//覆蓋該節點的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
//這里就是上面提到的第三個參數，可以回去看看，當他為否才會覆蓋
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//完事后hash表的長度如果大于擴容閾值，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
接著來看一下hashmap是如何擴容的，上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() {
//保存原始hash表
Node<K,V>[] oldTab = table;
//保存原始表的原始容量，如果原始表為空則為0 否則是原始表的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//保存老擴容閾值
int oldThr = threshold;
int newCap, newThr = 0;
//如果原始容量大于0，走這個邏輯
if (oldCap > 0) {
//如果原始容量大于2的30次方
if (oldCap >= MAXIMUM_CAPACITY) {
//把閾值設置為整形最大值，意思是不再進行擴容
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否則如果原始容量擴大兩倍后仍然小于2的30次方并且原始容量大于等于16，新容量等于老容
//量乘以2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的閾值也變為原來的兩倍，這個很好理解
newThr = oldThr << 1; // double threshold
}
//如果老的擴容閾值閾值大于0，這個判斷一般是hashmap初始化的時候第一次擴容會走
else if (oldThr > 0) // initial capacity was placed in threshold
//把新的容量設置為原始的閾值
newCap = oldThr;
//這里看注釋很好理解，如果我們hashmap初始化把容量設置為0走這個判斷
else {
// zero initial threshold signifies using defaults
//把新的容量設置為16
newCap = DEFAULT_INITIAL_CAPACITY;
//新的閾值設置為16*0.75，等于多少自己算
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//猜一下這個判斷什么時候會走，很明顯上面如果走else分支 newThr絕對不可能等于0，所以只可能
//走上面兩個判斷分支，很顯然第一個if判斷分支內部兩個小分支第一個直接返回第二個給newThr賦
//了值，所以只能是走中間分支，也就是第一次初始化的時候表容量為0，但是擴容閾值不是的情況
if (newThr == 0) {
//計算新的擴容閾值，如果新的容量小于2的30次方并且新的容量乘以負載因子之后小于2的30次
//方，則新的閾值等于新的容量乘以負載因子，否則設置為整數的最大值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//將當前擴容閾值設置為新的閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//用新的表容量初始化一個新的table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//把當前的hash表設置為新的table
table = newTab;
//下面是擴容之后的rehash操作
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//遍歷數組節點，如果當前節點不等于null，則進行下面的遷移操作
if ((e = oldTab[j]) != null) {
//先把節點保存到e，然后把數組該位置設置為null
oldTab[j] = null;
//如果e的下一個節點等于null，也就是當前位置只有一個節點，鏈表長度為1，
//那么進行和新的表容量進行取余運算后放到newTable的對應節點
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果此節點是樹節點，對它進行樹的拆分，我對紅黑樹了解不多，這里不做過多介紹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//這里走的是節點是個長度大于1的鏈表，但是又沒到樹化閾值的情況
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//循環
do {
//獲取e的下一個節點，保存到next
next = e.next;
//如果e的hash值與上oldCap等于0，這里解釋一下，oldCap是一個2的
//冪次方，轉化成二進制只有1位等于1，其他位都是0，所以結果要么為
//0，要么為oldCap
if ((e.hash & oldCap) == 0) {
//等于0，代表低位，如果低位鏈表尾節點等于null，將e賦值給低位
//鏈表頭節點
if (loTail == null)
loHead = e;
//否則將e賦值給尾節點的下一個節點，再將e節點設置為尾節點，這
//是一個標準的尾插法
else
loTail.next = e;
loTail = e;
}
//如果結果不等于0
else {
//邏輯和上面一樣，只是放到高位鏈表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//如果低位尾節點不等于null，將其next設置為null，并且將低位頭節點
//放置到newTable的j位置，也就是說位置是一樣的
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//如果是高位，則放置到j加上oldCap偏移量的位置，比如如果原來容量是16，
//新容量是32，原來j=8，在第九個位置，現在放到8+16=24，的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
關于擴容上面已經寫的較為詳細了，讀者如果有不明白的地方歡迎評論或者私信我。
我接下來要講的是一個比較容易忽略的點，還記得上面分析putVal的樹化操作嗎？來分析一下代碼：注意上面的注釋，把所有鏈表節點都換成樹節點除非表太小，將使用擴容代替。所以網上很多博客都是裝逼的，根本沒提到這個點，所以當你你出去面試，面試官問：樹化的閾值是8，那鏈表長度到8一定會樹化嗎？你看別人的博客，一定會說：對啊，達到8就會樹化，我看過put的代碼。然而很遺憾，你要回去等消息了，因為你根本沒點進來這個方法，關于樹化的條件，我在下面代碼中已經注釋，請自行閱讀。
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//首先第一件事，什么也不干，先判斷tab是否等于null以及tab的長度是否小于64，如果是的話
//會擴容而不是樹化
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);
}
}
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
三、get方法
可以看到他真實調用的是getNode方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
關于第一個判斷，一個是 == ，一個是equals，我們都知道一個是比較地址，一個是內容。所以我們重寫equals的時候建議重寫hashcode，畢竟如果作為key的話就會有點尷尬，不重寫顯然是獲取不到的，因為他首先比較的就是hashcode。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果hash表不等于null且長度大于0，且和key的hash取余之后的節點位置不為null，走里面邏
//輯，否則直接返回null，說明map里沒有
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//上面已經把hash取余后的位置的節點賦值給first節點，首先檢查第一個節點的hash值是不是
//等于傳進來的key的hash值并且，first節點的key等于傳進來的key或者傳進來的key不等于
//null并且內容相等，則直接返回第一個節點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//走到這里說明不是第一個節點，判斷他的下一個節點是否為null
if ((e = first.next) != null) {
// 如果是樹化的節點，則走紅黑樹的遍歷邏輯
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//否則一直循環到鏈表尾，如果找到相同的key則返回該節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//這里有兩種情況，第一種是表為空或者表長度為0，直接返回null，另一種是鏈表遍歷完沒有找到
//對應的key，則返回null
return null;
}
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
