散串列&HashMap、LinkedHashMap原始碼深入解讀
前言
??散串列的英文叫"Hash Table"，我們一般也叫做"哈希表"或者"Hash表"，你一定聽過它，但是你是不是真的理解這種資料結構呢？散串列用的是陣列支持下標隨機訪問資料的特性，所以散串列其實就是陣列的一種擴展，由陣列演化而來，可以說，沒有陣列就沒有散串列，那它具體又是如何實作的呢
??我們知道散串列將元素散落在各個槽中，無法通過添加的順序來遍歷每一個元素，如果我們想要按照元素添加的先后順序遍歷它該如何實作呢？
??LRU是一種快取淘汰演算法，按照最近最少使用的原則淘汰資料，HashMap是一種記憶體資料結構，如果記憶體不夠用了，我們該如何實作基于LRU的演算法來淘汰最近最少使用的資料呢？以下內容將一一為你解答，文章可能比較長，請耐心閱讀
文章目錄
- 散串列&HashMap、LinkedHashMap原始碼深入解讀
- 前言
- 散串列
- 散列函式
- 散列沖突
- 1.開放尋址法
- 2.鏈表法
- HashMap原始碼探索
- 資料域
- 構造方法
- 其他常用方法
- 迭代器
- 序列化與反序列化
- LinkedHashMap原始碼分析
- 屬性欄位
- 構造方法
- 特性方法
- 迭代器
- 序列化
散串列
??散串列具備三個核心要素，key鍵，就是存盤資料的關鍵字，用它來標識一個資料，key通過一個散列函式計算后就得到一個hash值，這個hash值通過取模運算后得到的就是hash表的槽位，我們知道hash表就是一個陣列，槽位就是陣列的某個下標位置，也叫做bucket(桶)，
散列函式
??從上圖中我們可以看到，散列函式在散串列中起著非常關鍵的作用，它是一個函式，我們把它定義成hash(key)，其中key表示元素的鍵值，hash(key)得到的值表示key經過散列函式計算得到的散列值，有了散列值我們就確定元素該放在陣列哪個位置上了，那么該如何構造散列函式呢？設計散列函式一般滿足以下三點：
1.散列函式計算得到的散列值必須是一個非負整數
2.如果key1==key2，那么hash(key1)==hash(key2)
3.如果key!=key2，那么hash(key1)!=hash(key2)
其中第一點很好理解，因為陣列的下標是從0開始的，而且必須是整數，第二點也很好理解，相同的key經過相同的函式得到的值應該是相同的，第三點理解起來可能會有點問題，這個要求看起來是合情合理的，不同key經過相同的函式計算得到的值理應不相等，但是在真實的情況下，想要找到一個不同的key對應的散列值不一樣的散列函式幾乎是不可能的，即便像業界著名的 MD5、SHA、CRC 等hash演算法，也無法完全避免這種散列從突，散列從突是指不同的key經過散列函式后得到的hash值相同，從而導致他們會落在同一個槽位上，而且由于陣列的大小有限，即使兩個不同的hash值，在經過取模運算后也有可能落在同一個槽位上，先看一下HashMap的hash函式實作：
//hash函式，通過key計算hash值
//key是可以為null的
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
散列沖突
??既然散列沖突是無法避免的，那我們該如何解決這種沖突問題呢？常用的散列沖突解決方法有兩類，開放尋址法 和 鏈表法
1.開放尋址法
??開放尋址法的核心思想就是，如果出現了散列沖突，我就重新探測一個空閑的位置，將其插入，先介紹一種比較簡單的探測方法，線性探測
??當我們往散串列中插入資料時，如果某個資料經過散列函式散列之后，存盤位置已經被占用了，我們就從當前位置開始，依次往后查找，看是否有空閑位置，直到找到為止，再將其插入，如下圖所示：
查找的程序跟插入類似，我們先通過散列函式求出要查找元素的鍵值對應的散列值，然后比較對應的陣列下標的元素與要查找的元素是否相等，如果相等，說明就是我們要找的元素；否則就按順序繼續往后查找，如果遍歷到陣列中空閑位置還沒找到，則說明要查找的元素不在散串列中，
??散串列還支持洗掉的操作，但是洗掉的操作有點特別，我們不能單純的把要洗掉的元素設定為空，這是為什么呢？因為在查找的時候，一旦我們找到一個空閑位置的時候，我們就認為散串列中不存在該資料，但是，如果這個空閑位置是我們后來洗掉的，就會導致原來的查找演算法失效，本來存在的資料會被認為不存在，該如何解決呢？我們可以將洗掉的元素特殊標記為keepOn，當查找遇到keepOn的位置的時候并不是停下來，而是繼續往下探測，如下圖所示：
當散串列中插入的資料越來越多時，散列沖突發生的可能性就會越來越大，空閑位置越來越少，線性探測的時間就會越來越久，極端情況下，我們可能要探測整個散串列，所以最壞情況下的時間復雜度為O(n)，同理，在洗掉和查找時，也可能會線性探測整張散串列，才能找到要查找或者洗掉的資料，
??對于開放尋址沖突解決方法，除了線性探測方法之外，還有另外兩種比較經典的探測方法，二次探測和雙重散列，所謂二次探測跟線性探測很像，線性探測每次探測的步長是1，那它探測的下標序列就是hash(key)+0,hash(key)+1,hash(key)+2……而二次探測的步長就變成原來的二次方，也就是說它探測的下標序列就是hash(key)+0,hash(key)+12 ,hash(key)+22 ……所謂雙重散列就是不僅要使用一個散列函式，我們使用一組散列函式hash1(key),hash2(key),hash3(key)……我們先用第一個散列函式，如果計算得到的存盤位置已經被占用，再用第二個散列函式，依次類推，直到找到空閑的存盤位置，
??不管使用哪種探測方法，當散串列中空閑位置不多的時候，散列沖突的概率就會大大提高，為了盡可能保證散串列操作的效率，一般情況下，我們會盡可能保證散串列中有一定比例的空閑槽位，我們用裝載因子來表示空位的多少，其可以用公式表示為：裝載因子=散串列中元素個數/散串列的長度，裝載因子越大，說明空閑位置越少，沖突的概率就會越大，
2.鏈表法
?? 鏈表法是一種更加常用的散列沖突解決辦法，相比開放尋址法，它要簡單很多，如下圖所示，每個槽位(桶)會對應一條鏈表，所有散列值相同的元素我們都放到相同槽位對應的鏈表中，
當插入的時候，我們只要通過散列函式計算出對應的散列槽位，將其插入到對應鏈表中即可，當查找、洗掉一個元素時，我們同樣通過散列函式計算出對應的槽，然后遍歷鏈表查找或者洗掉，
?? 散串列的基本知識就介紹到這里，接下來我們結合上面講的內容來看一下HashMap是如何來實作一個工業級的散串列的，
HashMap原始碼探索
??HashMap在我們的日常開發中經常使用，它是一個k、v結構的集合類，通過key來存盤或者查找對應的value，但它是執行緒不安全的，所以我們一般都是在單執行緒環境中使用，如果多執行緒并發訪問我們就需要手動做并發同步，接下來我們來看一下它的原始碼實作，
資料域
常量欄位
//默認hash表初始容量，必須是2的n次方，2^4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//hash表最大容量，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//樹化的閾值，當鏈表的長度達到該值時轉化成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//退化成鏈表的閾值，當紅黑樹的節點個數達到該值時退化成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//樹化的hash表最小容量，當鏈表的長度達到8、hash表的長度小于該值時，先進行擴容而不是樹化
static final int MIN_TREEIFY_CAPACITY = 64;
物件欄位
//hash表，元素是一個Node型別，
//transient修飾不能參與序列化，序列化時hash表單獨處理
//接下來的原始碼分析中hash表也會叫做陣列
transient Node<K,V>[] table;
//hash表中所有Entry元素集合
transient Set<Map.Entry<K,V>> entrySet;
//哈希表中鍵值對(Entry)的總數
transient int size;
//修改次數,發生洗掉或添加修改結點時次數加一
transient int modCount;
//下一次觸發擴容時的閾值大小
//還有一種情況就是當hash表沒有初始化，那么這個值就表示hash表初始化長度
int threshold;
//負載因子
final float loadFactor;
??HashMap底層基于hash表，即陣列，陣列元素型別是Node，Node就是一個Entry，不僅封裝了key、value欄位還封裝了key的hash值和next指標指向下一個Node(發生了hash從突)，
//具體的Entry，hash表中的元素封裝成entry
static class Node<K,V> implements Map.Entry<K,V> {
//通過hash函式計算得到的key的hash值
final int hash;
//元素的key
final K key;
//元素的value
V value;
//下一個node的地址，指向下一個node
//當槽位發生從突時，next不為空
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//先判斷記憶體地址是否相等
//如果記憶體地址不相等，再判斷key和value是否都相等
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
所以HashMap解決沖突使用了鏈表法，我們知道hash表正常情況下查找的時間復雜度是O(1)，但是鏈表法在極端的情況下，所有Node都發生了hash從突，這時候所有的Node都在一個鏈表上，時間復雜度就退化成了O(N)，如果是在高并發的場景下會導致服務器CPU負載升高，影響整體服務性能，所以HashMap做了優化，當鏈表的長度達到8并且hash表總的元素個數大于等于64時，將鏈表變成一顆紅黑樹，紅黑樹是一棵平衡的二叉搜索樹，查找、修改的時間復雜度為O(LogN)，
簡單介紹一下紅黑樹：
- 根節點是黑色的；
- 每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存盤資料；
- 任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；
- 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；
構造方法
初始化傳入hash表初始容量、負載因子
//建構式傳入初始容量大小、負載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//不能大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負載因子必須大于0且是必須是Number
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor方法回傳一個2的n次方大小的值，并且該值是最接近(大于等于)cap的
//回傳一個2的n次方大小的值，并且該值是最接近(大于等于)cap的
//位運算性能最高，我們來分析一下它的原理
//int是32位，我們假設最高位的index是32，最低位的index是1
//那么對于n，它肯定在某個index位上存在一個1(n!=0)，我們找到這個1所在index的最高位，記做maxIndex
//假設極端的情況，這個1的位置是32，即maxIndex=32，接下來開始運算，1xxxx... ...xxx
//n |= n >>> 1，n >>> 1后31位置上也變成了1，|=運算后32位置、31位置都變成了1，不用管后面位置的值,11xxx...xxx
//n |= n >>> 2，n >>> 2后30、29位置都變成了1，|=運算后32、31、30、29都變成了1，不用管后面的值,1111xxx...xxx
//n |= n >>> 4,1111 1111 XXX...XXX
//n |= n >>> 8,1111 1111 1111 1111 xxx...xxx
//n |= n >>> 16,1111 1111 1111 1111 1111 1111 1111 1111
//好了，現在maxIndex后面的位置都變成了1，如果maxIndex不是32呢，其結果也一樣，都會把maxIndex后面的位置變成1
//最后n+1就會把maxIndex以及它后面的位置都變成0，maxIndex前面的位置變成1，也就是2^maxIndex
//如果cap本身就是2的N次方呢，那回傳的還是cap，如果n是0的話，那么最后n+1就回傳2^0.
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;
}
傳入外部hash表的建構式
//傳入外部map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//將外部map的元素結點node添加到當前map中
putMapEntries(m, false);
}
看一下具體的putMapEntries方法
//外部map的key、value的型別必須和當前map的key、value型別相同，或是其子類
//evict表示是否可以淘汰最近未被使用的元素結點，在LInkedHashMap中用到
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//哈希表初始化
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)
//如果外部hash表元素個數大于擴容閾值則直接觸發擴容操作
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//遍歷外部hash表，將元素添加進當前的hash表，如果存在相同的key則覆寫對應的value
putVal(hash(key), key, value, false, evict);
}
}
}
resize擴容操作
//擴容操作，就是創建新的hash表，長度擴大一倍，hash表初始化也是在這一步完成的
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//原hash表的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果原hash表長度已經到達最大長度上限
//設定擴容閾值為最大正整數
//回傳原先的hash表，不能再擴容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
//原hash表長度大于默認初始容量(16) & 申請新hash表的長度為老hash表的兩倍大小，并且新hash表長度小于最大長度上限
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的擴容閾值=老的閾值*2
//因為oldThr=oldCap*loadFactor
//所以newThr=newCap*loadFactor=2*oldCap*loadFactor=2*oldThr
newThr = oldThr << 1;
}
else if (oldThr > 0)
//hash表沒有初始化，而擴容閾值大于0，那么擴容閾值就用作hash表初始化長度
newCap = oldThr;
else {
//如果原hash表長度、閾值都不大于0，說明hash表還沒有初始化
//取默認的初始化值
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//新的hash表創建好了
table = newTab;
//接下來是核心的資料搬移操作了
if (oldTab != null) {
//遍歷老的hash表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果當前槽位存在結點的話需要將它搬到新的hash表
if ((e = oldTab[j]) != null) {
//原槽位置空
oldTab[j] = null;
//如果該槽位只有一個結點元素，那就直接hash取模(取新的hash表的模)搬移到新的hash表即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果該槽位上的結點型別是TreeNode說明是一顆紅黑樹，需要將整棵樹搬移到新hash表
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;
//等于0的話說明該結點應該放到低位鏈表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//否則該結點應該放到高位鏈表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//低位鏈表在新hash表的下標位置和原hash表一樣都是j
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位鏈表在新hash表中的下標位置是原hash表的位置+原hash表大小
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
再看一下TreeNode的split方法，因為紅黑樹的結點也維護了鏈表的資料結構，所以其原理和上面的鏈表資料的搬移操作差不多
//TreeNode繼承自Node，他的每個結點同時也維護了一個雙向鏈表的資料結構
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//低位鏈表頭結點、尾結點
TreeNode<K,V> loHead = null, loTail = null;
//高位鏈表頭結點、尾結點
TreeNode<K,V> hiHead = null, hiTail = null;
//記錄高低位鏈表的結點個數
int lc = 0, hc = 0;
//遍歷每個結點，因為也是一個雙向鏈表結構，所以可以通過next指標遍歷每一個結點
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//當前結點 & bit等于0的話就添加到低位鏈表，也是一個雙向的鏈表，bit就是原hash表的長度
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
//否則的話就是應該添加到高位鏈表，也是一個雙向鏈表
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//低位鏈表在新hash表的位置index保持和原hash表的位置一致
//如果長度小于等于樹退化的閾值就將此樹退化成鏈表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
//否則就將此鏈表搬移到新的hash表
tab[index] = loHead;
//說明原來的樹被一分為二了，需要重新樹化
if (hiHead != null)
loHead.treeify(tab);
}
}
if (hiHead != null) {
//高位鏈表在新hash表的位置index是原hash表的index+原hash表的長度
//小于等于樹退化的閾值的就退化成一個鏈表
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
//搬移到新的hash表對應的槽位
tab[index + bit] = hiHead;
//說明原來的樹被一分為二了，需要重新樹化
if (loHead != null)
hiHead.treeify(tab);
}
}
}
重點分析一下資料搬移的操作原理，hash表的長度size為2的n次冪即1<<n，那么size-1的低位都是1，所以hash值&(size-1)的范圍就是[0，size-1]，正好均勻落在hash表的每個桶內，當hash表擴容后，長度size為原來的兩倍，即1<<n+1，那么在搬移資料的時候我們只需判斷n位置所在的bit位是0還是1，將資料分為低位和高位，如果是0就是低位，那么它搬移后新的位置index還是和老的hash表的位置一樣，如果是1的話就是高位，那么它搬移后的位置就是原先hash表位置加上原hash表的size，見下圖，其中bit就是原hash表的size：
將原hash表的結點分為低位結點和高位結點兩類結點后，分別重新組合成新的鏈表，再整體搬移到新hash表對應的槽位上
??再來看putMapEntries方法最后一步操作putVal，其中有兩個方法afterNodeAccess和afterNodeInsertion在LinkedHashMap中實作了，后面會分析
//真正添加元素結點的方法，onlyIfAbsent為false的話覆寫已存在的key的value
//evict為false表示正在創建hash表，為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;
//如果hash表長度是0的話說明還沒初始化，初始化在擴容方法resize()里完成
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash取模計算key所在的槽位，判斷該槽位是否存在結點p
//n是2的n次冪，所以n-1的二進制低位都是1，&計算出來的值肯定是介于0到(n-1)之間
if ((p = tab[i = (n - 1) & hash]) == null)
//如果該槽位是空的話就把key，value包裝成node添加到該槽位
tab[i] = newNode(hash, key, value, null);
else {
//否則該槽位上已存在結點p
//判斷p結點與待插入結點的key是否相等,hash值相等的情況下key不一定相等，hash不相等key肯定不相等
//相等的話記錄e，表示存在key相同的結點
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果該槽位上是一顆紅黑樹，則查找紅黑樹中是否存在key相等的結點
//存在的話會回傳該結點并記錄e，不存在的話該新結點就插入紅黑樹中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//否則該槽位就是一個鏈表結構，遍歷鏈表
for (int binCount = 0; ; ++binCount) {
//如果找不到key相等的結點就把新結點插入鏈表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//達到樹化閾值
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//樹化操作，將該鏈表變成紅黑樹
treeifyBin(tab, hash);
break;
}
//鏈表中已經存在key相等結點e，終止回圈
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//存在和待插入元素相同key的結點e
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent引數表示只有在e結點的value不存在的情況下才會替換成新結點的value
//如果是false的話原結點e的value都會被替換成新結點的value
//如果原結點e的value是空的話，替換成新的結點的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//這個方法是在LinkedHashMap中真正實作，用來將該結點e搬移到鏈表最后面
//表示該結點最近被訪問過了，如果此時要回收hash表上的結點的話，該結點就會躲過一劫
//因為回收是從頭結點開始回收的
afterNodeAccess(e);
return oldValue;
}
}
//添加新元素成功了，增加修改次數
++modCount;
if (++size > threshold)
//size加1如果大于擴容閾值的話就擴容
resize();
//這個方法是被LinkedHashMap真正實作
//如果evict是true的話淘汰頭結點(最近最少使用的那個結點)
afterNodeInsertion(evict);
return null;
}
這里如果發生了hash從突，并且鏈表的長度達到了樹化的閾值，則需要轉化成紅黑樹
//將鏈表轉化紅黑樹
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果hash表長度小于最小樹化長度閾值(64)，則先進行擴容而不是樹化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//如果hash取模對應的槽位index存在結點e
//說明此槽位上的鏈表需要樹化
else if ((e = tab[index = (n - 1) & hash]) != null) {
//頭結點、尾結點
TreeNode<K,V> hd = null, tl = null;
do {
//遍歷每一個結點，將他們包裝成TreeNode，TreeNode繼承自Node
//它的內部不僅有next指標，還有prev指標，并且維護了一個和轉化
//前鏈表順序相同的雙向鏈表結構，所以它既是紅黑樹，又是雙向鏈表
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);
}
}
其他常用方法
根據key查找對應的value
//根據key獲取對應的value
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//根據hash值、key獲取對應結點
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果hash表不為空，并且hash取模后對應的槽位上存在結點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//根據hash、key判斷，如果對應槽位上的結點就是要查找的結點，直接回傳該結點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果該槽位存在多個結點
if ((e = first.next) != null) {
//如果結點是TreeNode型別，說明是一顆紅黑樹，通過紅黑樹的搜索方法查找對應的結點并回傳
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//鏈表型別的結點，通過遍歷查找對應的結點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//找不到回傳null
return null;
}
根據key洗掉對應的鍵值對
//根據指定的key洗掉對應的k、v鍵值對
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//根據hash值、key洗掉對應的結點，如果value不為空且matchValue為true，則洗掉的條件還必須是value也相等
//先查到到要洗掉的結點，然后再洗掉，如果沒找到回傳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;
//先判斷hash表不為空，且hash取模后對應的槽位上存在結點
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;
//判斷槽位上的第一個結點是否是要查找的結點，是的話記錄node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//如果第一個結點不是要查找的結點，且該槽位不止一個結點，則繼續探測
//如果TreeNode結點型別就從紅黑樹中查找對應的結點并記錄node
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;
} while ((e = e.next) != null);
}
}
//如果找到了待洗掉的結點node，判斷是否需要比較value的值，并且value也相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是紅黑樹，洗掉node結點
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//p記錄的是node前一個結點，如果node==p則說明
//p是hash槽的第一個結點，洗掉node，node后面的結點變成hash槽第一個結點
else if (node == p)
tab[index] = node.next;
else
//否則從鏈表中洗掉node
p.next = node.next;
//修改次數加1
++modCount;
//size減1
--size;
//這個方法在LinkedHashMap中實作了
//洗掉在鏈表中的node結點
afterNodeRemoval(node);
return node;
}
}
return null;
}
清空hash表
//清空hash表所有槽位上的結點
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
迭代器
常用的key、value、entry迭代器
//key迭代器
final class KeyIterator extends HashIterator
implements Iterator<K> {
//回傳結點的key
public final K next() { return nextNode().key; }
}
//value迭代器
final class ValueIterator extends HashIterator
implements Iterator<V> {
//回傳結點的value
public final V next() { return nextNode().value; }
}
//entry迭代器
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
//回傳整個結點，即Entry
public final Map.Entry<K,V> next() { return nextNode(); }
}
看一下核心的HashIterator
abstract class HashIterator {
//指向下一個回傳的結點
Node<K,V> next; // next entry to return
//當前的結點
Node<K,V> current; // current entry
//更新標志位
int expectedModCount; // for fast-fail
//當前hash表的槽位
int index; // current slot
HashIterator() {
//記錄當前變更次數
expectedModCount = modCount;
//hash表
Node<K,V>[] t = table;
current = next = null;
index = 0;
//找到第一個不為空的槽位的index下標并賦值給next
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
//回傳下一個結點
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
//如果hash表發生了變動則拋例外
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//當前要回傳的結點不存在，說明已經遍歷完了，拋例外
if (e == null)
throw new NoSuchElementException();
//如果下一個結點空，說明當前slot槽位上已經到鏈表尾部了，則繼續遍歷下一個非空
//slot上的結點鏈表，直到最后一個index位置
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
//回傳當前結點
return e;
}
//洗掉遍歷到的當前結點，洗掉以后可以繼續向下迭代不影響后面的結點遍歷
public final void remove() {
Node<K,V> p = current;
//當前結點空拋例外
if (p == null)
throw new IllegalStateException();
//如果hash表結點發生了變動，拋例外
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//當前結點指標清空
current = null;
//當前結點的key
K key = p.key;
//呼叫HashMap中的方法洗掉當前結點
removeNode(hash(key), key, null, false, false);
//洗掉以后modCount會加1，同步到expectedModCount
expectedModCount = modCount;
}
}
序列化與反序列化
先看一下clone方法，該方法是淺克隆，克隆物件的hash表的結點元素和宿主物件是共享的
//回傳一個克隆物件，共享當前hashmap中的key，value
@Override
public Object clone() {
HashMap<K,V> result;
try {
//創建克隆物件
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
//初始化欄位
result.reinitialize();
//將當前物件的key、value添加到克隆物件中
result.putMapEntries(this, false);
return result;
}
深克隆可以通過序列化的方式實作，他的每一個結點元素都單獨做序列化、反序列化，先看一下序列化方法
//序列化方法，ObjectOutputStream#writeObject(obj)會呼叫到此方法
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
//回傳hash表的桶數，也就是hash表的長度
int buckets = capacity();
//將非static、非transient修飾的欄位寫到stream中
s.defaultWriteObject();
//寫入桶大小
s.writeInt(buckets);
//寫入結點個數
s.writeInt(size);
//依次寫入每個entry
internalWriteEntries(s);
}
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
//依次遍歷每一個結點寫入序列化流中
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
反序列化方法
//反序列方法，ObjectInputStream#readObject會呼叫到此方法
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
//將非static、非transient修飾的欄位反序列化到當前物件中
s.defaultReadObject();
//初始化某些欄位，因為接下來要重新構造hash表
reinitialize();
//判斷負載因子是否合法
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
//對應于序列化方法中的s.writeInt(buckets);讀取桶數
s.readInt();
//對應于序列化方法中的s.writeInt(size);讀取結點個數
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// 負載因子的大小范圍在0.25f--4.0f
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
//根據負載因子和結點個數反向計算所需的最小容量
float fc = (float)mappings / lf + 1.0f;
//回傳一個在指定范圍內，并且大小為2的n次方的cap
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
//計算下一次擴容的閾值
float ft = (float)cap * lf;
//擴容閾值范圍檢查并賦值
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
// Check Map.Entry[].class since it's the nearest public type to
// what we're actually creating.
SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);
@SuppressWarnings({"rawtypes","unchecked"})
//新的hash表
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
//依次反序列化每一個key、value，并把他們添加到hash表中
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
LinkedHashMap原始碼分析
??我們知道元素插入hash表是根據hash函式隨機散落在hash表上的，我們無法根據插入的先后順序或訪問的先后順序去遍歷它，那有沒有辦法實作按順序遍歷呢，LinkedHashMap就實作了這種功能，它本質上還是一個hash表，結點還是按照hash值散落在陣列上，但是每個結點內部多了兩個指標before、after用來記錄在它前后的兩個結點，也就是說每個結點還通過鏈表的形式按照添加的先后順序串連了起來，如下圖所示，有了這個順序鏈表之后我們就可以實作一些HashMap無法實作的功能，比如，按照添加順序遍歷訪問，按照FIFO的策略淘汰最先進來的結點，還可以實作LRU的快取淘汰策略，
??因為LinkedHashMap是繼承自HashMap，所以很多基本的方法在上面HashMap中都已經分析了，我們只看LinkedHashMap自己擴展的方法和屬性，因為LinkedHashMap比HashMap多了一層鏈表的資料結構，所以它的屬性和方法都是在維護和操作鏈表，
屬性欄位
??Entry繼承自HashMap.Node，多了兩個欄位用來指向前后結點，accessOrder是組織鏈表順序的方式，true的話按照元素的訪問順序排列，即如果某個結點元素被訪問，就把它搬移到鏈表末尾，頭結點就是最近最少使用的結點，false的話就是按照元素的插入順序組織鏈表，
//繼承自HashMap的Node，多了兩個指標用來將所有結點串起來，實作按順序遍歷
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//頭結點
transient LinkedHashMap.Entry<K,V> head;
//尾結點
transient LinkedHashMap.Entry<K,V> tail;
//組織鏈表時的順序方式
//true 按照元素的訪問順序，false 按照元素的插入順序
final boolean accessOrder;
構造方法
??可以看到構造方法基本都呼叫了父類的方法，除非特別指定，否則就是取元素的插入順序組織鏈表結構
//構造方法，默認按照元素的插入順序維護鏈表結構
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
特性方法
??在繼承HashMap的基礎上，LinkedHashMap有他自己的方法來操作鏈表，先來看一下創建結點的方法，在創建完新的結點后，會自動把它添加到當前鏈表的末尾
//創建新的結點
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//添加到鏈表末尾
linkNodeLast(p);
return p;
}
//創建TreeNode的，TreeNode繼承自Entry
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
//同樣也添加到鏈表尾部
linkNodeLast(p);
return p;
}
afterNodeRemoval方法，該方法在HashMap#removeNode方法最后呼叫，表示洗掉hash表中的結點e之后，該結點在鏈表中還存在，也要將它洗掉
//hash表中洗掉該結點之后的操作
//同樣的將該結點從當前鏈表中洗掉
void afterNodeRemoval(Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
afterNodeInsertion方法，該方法在HashMap#putVal方法最后被呼叫，表示元素e添加到hash表之后可能需要淘汰鏈表上的頭結點，
//將當前結點添加到hash表之后的操作
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//如果evict為true，并且removeEldestEntry方法回傳true，說明可以洗掉鏈表頭結點
//默認情況下removeEldestEntry回傳false，即不會淘汰頭結點
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
afterNodeAccess方法，在HashMap的查詢、更新等操作方法中會呼叫到該方法，會把相應的被訪問到的結點搬到鏈表尾部
//訪問某個結點e之后的操作
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//accessOrder為true，并且當前結點不在鏈表尾部
//則將該結點移到鏈表末尾
//默認情況下是不會搬移的，鏈表的順序按照插入順序
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
所以我們可以通過LinkedHashMap來實作一個基于LRU快取淘汰策略的hash表，只需設定accessOrder為true，并重寫removeEldestEntry允許淘汰最近最少使用的頭結點
迭代器
??該迭代器可以按照元素的順序遍歷訪問，只需按照鏈表順序迭代即可
//迭代器
abstract class LinkedHashIterator {
//下一個結點
LinkedHashMap.Entry<K,V> next;
//當前結點
LinkedHashMap.Entry<K,V> current;
//更新標志
int expectedModCount;
LinkedHashIterator() {
//從頭結點開始遍歷
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
//要回傳的當前結點e
LinkedHashMap.Entry<K,V> e = next;
//如果發生了結點的變動，拋例外
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//當前結點不存在，拋例外
if (e == null)
throw new NoSuchElementException();
//當前結點
current = e;
//下一個結點
next = e.after;
return e;
}
public final void remove() {
//當前結點，即將要被洗掉的結點
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
//發生了變動，拋例外
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
//洗掉當前結點p
removeNode(hash(key), key, null, false, false);
//更新expectedModCount，可以繼續迭代下一個結點
expectedModCount = modCount;
}
}
//key迭代器，回傳結點的key
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
//value迭代器，回傳結點的value
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
//Entry迭代器，回傳整個結點
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
序列化
??LInkedHashMap的序列化、反序列化方法使用了HashMap的相關方法，只不過自己實作了結點的序列化策略，即按照鏈表的順序序列化，這樣反序列化的時候鏈表的順序維持不變
//序列化hash表結點Entry時的操作
//按照結點所在鏈表的順序序列化
//這樣反序列化時的順序也是按照原鏈表的順序
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/153024.html
標籤：其他
上一篇：caesim自動泊車場景搭建
下一篇：Cal3D庫如何用？