HashMap源碼剖析（上）
文章目錄
- HashMap源碼剖析（上）
-
- 一、HashMap的資料結構
- 二、HashMap的構造
-
- 2.1、HashMap的無參構造
- 2.2、HashMap的其他幾個構造方法
- 三、元素的添加
- 更新内容
-
- hashMap的putVal方法源碼注釋
- 擴容方法源碼
對于每一個Java程式員來說，HashMap你一定不陌生，作為經典面試題，從HashMap上可以考察的知識點太多了。于是乎希望總結一份HashMap的源碼級剖析，來檢驗自己對于Java知識體系的掌握程度
一、HashMap的資料結構
大家或多或少都了解過HashMap
在JDK1.7之前HashMap的結構是數組+連結清單的形式
在JDK1.8之後HashMap的結構就改成了數組+連結清單+紅黑樹的形式
tips:如果大家對紅黑樹不了解的，可以參考我其他有關紅黑樹部落格
二、HashMap的構造
2.1、HashMap的無參構造
通過new HashMap()我們可以很容易的擷取一個HashMap的對象
之後讓我們進入源碼看一看HashMap究竟是如何構造的吧
源碼中HashMap一共有四個構造方法，我們最常用的還是無參的構造
//無參HashMap構造源碼
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
可以看到在構造方法中并沒有建立一個數組來存儲元素，隻是将loadFactor進行指派。
那麼什麼是loadFactor呢？
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
來看源碼注釋：loadFactor是hash table的加載因子。
大家都知道數組是固定長度的，但是HashMap我們建立時并沒有指定其長度，也就意味着理論上HashMap是可以無限增長的（當然看源碼之後會發現有一個最大值的限制），這樣數組的定長和HashMap得到無限長之間就出現了沖突。為了解決這個沖突就需要loadFactor的作用了，他相當于一個門檻值，當數組元素數量超過門檻值時可以對數組進行擴容（後面會詳細說）
那麼在構造HashMap時的預設加載因子是多少呢？
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
源碼告訴我們是0.75。為什麼是0.75呢？其實這個數字可以在Hash碰撞和空間使用率之前尋找一個最好的平衡。
2.2、HashMap的其他幾個構造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
該構造方法傳入一個初始容量後調用了其他的構造方法，又看到了預設加載因子，我們繼續追蹤
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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
我們來到了HashMap的另一個構造方法，這個構造的代碼還比較多，但是也還比較簡單
- 最初先對指定初始容量值進行資料合法性檢驗
- 又看到一個新的常量MAXIMUM_CAPACITY，追入源碼
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
MAXIMUM_CAPACITY規定了HashMap數組的最大長度，采用位運算左移30位
注釋告訴我們HashMap的容量必須是2的幂并且容量要小于MAXIMUM_CAPACITY
大家思考思考為什麼一定需要是2的幂？答案以後揭曉
- 回到HashMap的構造方法，接下來對加載因子進行資料合法性檢驗
- 之後将加載因子指派給HashMap的成員變量
- 之後對容量進行操作并指派給HashMap的一個成員變量，追入tableSizeFor方法檢視源碼
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
源碼将容量轉換為2的幂，對n進行一系列的無符号右移和或運算将cap轉換為2的幂，構造結束
再看最後一個構造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
- 傳入一個Map，将已有的Map放入新建立的HashMap中，方法就不繼續追了，大家可以自己追一下看看，是循環将元素複制到本HashMap中
可以看出除了傳入Map的構造方法外其餘方法都隻是對變量進行了初始化而并沒有實際建立數組，實作了懶加載的效果。
三、元素的添加
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
- 調用putVal方法
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- putVal方法是HashMap的一個核心方法之一了
- 聲明了Node[]數組tab；Node結點p；變量n和i
- 再了解一個成員變量table，HashMap的元素數組
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
- 回到putVal方法，當table為空也就是目前HashMap對象仍為空的時候調用resize()方法（擴容方法，以後會說）先了解為建立一個Node[]數組
- if ((p = tab[i = (n - 1) & hash]) == null) 通過hash值和table長度n進行與操作确定元素要放入的位置并判斷其位置是否為null，如果為空直接建立新結點将元素放入tab[i]位置
- 否則也就是之前的位置上已經有元素，則需要進入else，進行進一步操作
-
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) /* 判斷目前插入位置的原有元素p的hash值和待插入元素hash值是否相同，并判斷是否為同一個key，如果是同一個key，則e = p，之後判斷e!=null，将新的value覆寫掉之前的val，并将舊結點p的value傳回 */ - 如果key不相同或hash與原有元素p不同else if判斷原有結點是否為TreeNode類型，如果是則調用紅黑樹的插入元素方法将新元素插入
- 否則進入else，也就是普通的連結清單結點進入else進行處理，就是普通的連結清單周遊尋找是否有插入位置，并檢查連結清單長度判斷是否需要樹化
- 如果找到一個位置可以放入新結點，則建立新結點存在連結清單的尾部，并判斷是否需要樹化，如果長度超過TREEIFY_THRESHOLD-1，則進行樹化并退出循環，e為null，size++并判斷是否需要擴容，傳回null
- 如果在連結清單中找到一個相同元素則直接break，e不為null，将新value覆寫舊的value并傳回舊的value
-
更新内容
hashMap的putVal方法源碼注釋
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 向map中放入元素
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果此時map的數組還未初始化 或者數組的長度為0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 對map的數組進行擴容
// 找到目前元素要放置的位置 使用((hashTable.length - 1) & hash)确定元素要放入的下标
// 如果該位置目前沒有元素 則直接建立一個新節點放入該下标的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 目前位置已經有元素
else {
Node<K,V> e; K k;
// p 是該位置原有的元素 p元素的hash值與待插入的元素的hash值相同
if (p.hash == hash &&
// p的key和待插入元素的key進行比較 (==比較位址，equals比較key的值)
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 将e指向p
// p.key和待插入的key不相等 判斷p是否是樹節點
else if (p instanceof TreeNode)
// 如果是樹節點 則将p轉為TreeNode節點 并調用putTreeVal()将待插入節點插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// p不是樹節點 隻能是連結清單節點
else {
// 使用binCount記錄連結清單的長度
for (int binCount = 0; ; ++binCount) {
// 使用e指針記錄p.next位置 如果p.next == null 證明找到了連結清單尾部，可以讓節點插入
if ((e = p.next) == null) {
// 建立一個節點 并讓p.next指向新節點
p.next = newNode(hash, key, value, null);
// 判斷連結清單的長度是否已經達到轉換為樹的門檻值标準（-1是因為插入了新節點但是此時bitCount還沒有改變）
// 但此時還不會直接轉為紅黑樹 還需要對hash表的長度進行判斷 （hash表門檻值長度為64）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); // 将hashTable轉為樹
break;
}
// 判斷待插入的節點和否在連結清單中的某個節點(目前周遊到的e節點)相同 如果是 證明需要更新該節點的值 而不是插入新節點 則跳出循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 讓p指向e節點(p.next) 向下一個節點進行循環周遊
p = e;
}
}
// 需要更新e節點的值
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;
}
擴容方法源碼
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 擷取hashtable的舊容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 儲存舊的擴容門檻值
int oldThr = threshold;
int newCap, newThr = 0;
// 對舊容量進行判斷
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量為舊容量的2次幂 并且保證擴容後不大于規定的最大容量 并且不小于預設初始容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 擴容門檻值也擴大為原來的2次幂
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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"})
// 建立一個新的hash表 容量為擴容後的新大小
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 周遊舊hash表中的每一個節點
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 擷取舊畫上表中j下标位置的元素 如果不為null 則進行遷移
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 将舊tab中的值置為null
// 判斷e節點是否還有後繼節點
if (e.next == null)
// 在新的hash表中找到一個位置給節點e
newTab[e.hash & (newCap - 1)] = e;
// 節點e是否是樹節點
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;
// 使用e節點的hash值和舊hash表的容量進行&操作 判斷是使用低指針遷移還是使用高指針遷移
if ((e.hash & oldCap) == 0) {
// 如果低位尾指針等于null 則将loHead指向e節點
if (loTail == null)
loHead = e;
else
loTail.next = e; // 如果loTail不為null(head确定後就不為null了) 則将loTail.next連上新節點
// 讓loTail指向e節點
loTail = e;
}
// 該節點需要使用高位指針進行處理
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将低位指針移動到新hash表的原j位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将高位指針移動到新hash表的j+oldCap位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
/*注意：隻有數組的長度為2的指數次幂才可以應用這個操作 否則擴容後使用hash得到的位置就和擴容後放入的位置不同 就會出錯*/
}
}
}
}
return newTab;
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)