HashMap概述
??HashMap是基于哈希表的Map接口的非同步實現(xiàn)（Hashtable跟HashMap很像，唯一的區(qū)別是Hashtalbe中的方法是線程安全的，也就是同步的）。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
HashMap 的數(shù)據(jù)結(jié)構(gòu)
??在JDK1.6，JDK1.7中，HashMap采用位桶(數(shù)組)+鏈表實現(xiàn)，即使用鏈表處理沖突，同一hash值的鏈表都存儲在一個鏈表里。但是當位于一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。
??而JDK1.8中，HashMap采用位桶+鏈表+紅黑樹實現(xiàn)，當鏈表長度超過閾值（8）時，將鏈表轉(zhuǎn)換為紅黑樹，這樣大大減少了查找時間
-
散列表（Hash table，也叫哈希表）
//表，第一次使用時初始化（而非實例化集合時進行初始化），并根據(jù)需要調(diào)整大小。當分配時，長度總是2的冪。(在某些操作中，我們還允許長度為零，以允許當前不需要的引導機制。） transient Node<K,V>[] table;
-
鏈表
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; …… }
-
黑紅樹
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; …… } -
什么情況下轉(zhuǎn)成鏈表,什么情況轉(zhuǎn)成黑紅樹
- 桶的樹化閾值：即 鏈表轉(zhuǎn)成紅黑樹的閾值，在存儲數(shù)據(jù)時，當鏈表長度 > 該值時，則將鏈表轉(zhuǎn)換成紅黑樹
static final int TREEIFY_THRESHOLD = 8
- 桶的鏈表還原閾值：即 紅黑樹轉(zhuǎn)為鏈表的閾值，當在擴容（resize（））時（此時
HashMap的數(shù)據(jù)存儲位置會重新計算），在重新計算存儲位置后，當原有的紅黑樹內(nèi)數(shù)量 < 6時，則將 紅黑樹轉(zhuǎn)換成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
- 最小樹形化容量閾值：即 當哈希表中的容量 > 該值時，才允許樹形化鏈表,否則，若桶內(nèi)元素太多時，則直接擴容，而不是樹形化, 為了避免進行擴容、樹形化選擇的沖突，這個值不能小于
4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
Hash沖突
描述 : 如果兩個不同對象的hashCode相同，這種現(xiàn)象稱為hash沖突。
解決辦法 :
HashMap在處理沖突時使用鏈表存儲相同索引的元素
從Java 8開始,在處理頻繁沖突時將使用紅黑樹來代替鏈表，當同一hash桶中的元素數(shù)量超過特定的值便會由鏈表切換到紅黑樹樹
當從鏈表切換到平衡樹時，HashMap迭代的順序?qū)淖?。不過這并不會造成什么問題，因為HashMap并沒有對迭代的順序提供任何保證.
使用HashMap之所以會產(chǎn)生沖突是因為使用了鍵對象的hashCode()方法，而equals()和hashCode()方法不保證不同對象的hashCode是不同的。需要記住的是，相同對象的hashCode一定是相同的，但相同的hashCode不一定是相同的對象
-
這種方法被稱為鏈地址法 除此之外還有開放尋址法,再哈希法,建立公共溢出區(qū)
開放定址法: 當關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應(yīng)元素存入其中。這種方法有一個通用的再散列函數(shù)形式
-
再哈希法: 這種方法是同時構(gòu)造多個不同的哈希函數(shù):
? Hi=RH1（key） i=1，2，…，k
? 當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。
鏈地址法: 這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。
建立公共溢出區(qū): 將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。
詳細分析
1. HashMap的創(chuàng)建
/********************************************HashMap中重要的常量******************/
// aka 16 默認桶大小為2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認的負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//閾值最小值=8
static final int TREEIFY_THRESHOLD = 8;
// 在哈希表擴容時，如果發(fā)現(xiàn)鏈表長度小于 6，則會由樹重新退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹形化容量閾值：即 當哈希表中的容量 > 該值時，才允許樹形化鏈表
static final int MIN_TREEIFY_CAPACITY = 64;
//閾值 = 負載因子 * 容量(不填容量時默認為16)
int threshold;
//表示當前HashMap包含的鍵值對數(shù)量
transient int size;
//表示當前HashMap修改次數(shù)
transient int modCount：
//構(gòu)建一個空的HashMap 默認容量為16 加載因子為0.75 默認臨界值為16*0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//傳遞初始容量
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;
//計算得到能容納最多鍵值對的個數(shù) 默認等于初始值16
//但是該方法返回值是的大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù) 如
this.threshold = tableSizeFor(initialCapacity);
}
//傳入一個map 相當于添加一個節(jié)點
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
//下面括號里會算出來一個容量，使得size剛好不大于閾值。
//但這樣會算出小數(shù)來，但作為容量就必須向上取整，所以這里要加1
float ft = ((float)s / loadFactor) + 1.0F;
//如果小于最大容量，就進行截斷；否則就賦值為最大容量
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//但在算出來的容量t > 閾值(threshold)時，才會用t計算出新容量，
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果當前容量大于下一個需要調(diào)整的容量
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);
}
}
}
/**
* 根據(jù)容量參數(shù)，返回一個2的n次冪的table長度。
*/
private static final int tableSizeFor(int c) {
int n = c - 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;
}
//右移一位相當于 n/2^1 n =4 101 | 10 = 111 =十進制 7
2. get()
public V get(Object key) {
Node<K, V> e;
//返回值是指定鍵映射到的值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
///如果表不是空的，并且要查找索引處有值，就判斷位于第一個的key是否是要查找的key
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 {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
實現(xiàn)思路:
- 判斷表或key是否是null，如果是直接返回null
- 判斷索引處第一個key與傳入key是否相等，如果相等直接返回
- 如果不相等，判斷鏈表是否是紅黑二叉樹，如果是，直接從樹中取值
- 如果不是樹，就遍歷鏈表查找
3. put()
//這里需要注意的是 如果值已經(jīng)存在了 這里要替換成新的值
public V put(K key, V value)
//參數(shù) 4 false表示不改變現(xiàn)有的值
//參數(shù)5 false 表示創(chuàng)建模式
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab; //數(shù)組(或者桶)
Node<K, V> p;//節(jié)點
int n, i;
//判斷Hashmap是否為空,如果沒有數(shù)據(jù)就先進行數(shù)組的擴充
if ((tab = table) == null || (n = tab.length) == 0)
//獲取擴充后的數(shù)組長度
n = (tab = resize()).length;
// 如果計算出來的索引位置之前沒有放過數(shù)據(jù)，就直接放入 根據(jù)hash值和數(shù)組長度進行取模運算后，得到鏈表的首節(jié)點
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//處理Hash沖突,即計算出來的位置之前有插入數(shù)據(jù)
else {
Node<K, V> e;
K k;//key
//1. p原有的節(jié)點 和當前傳過來的hash值比對,k來接收原來索引位置的hash值
if (p.hash == hash &&
// key的地址或key的equals()只要有一個相等就認為key重復了
((k = p.key) == key || (key != null && key.equals(k))))
//替換原有的節(jié)點
e = p;
//2. 如果原來的節(jié)點是紅黑樹
else if (p instanceof TreeNode)
//黑紅樹的節(jié)點替換
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
//如果二個節(jié)點的hash值相同但是key值不相同,則會進行下列處理
for (int binCount = 0; ; ++binCount) {
//把e節(jié)點指向hashmap的第一個節(jié)點 p在這里的值是(p = tab[i = (n - 1) & hash])
if ((e = p.next) == null) {
//把當前hashmap的下一個節(jié)點賦值給當前節(jié)點
p.next = newNode(hash, key, value, null);
//如果添加新的節(jié)點后 源數(shù)組的長度大于等于8 binCount從0開始的
if (binCount >= TREEIFY_THRESHOLD - 1)
//鏈表的樹化
treeifyBin(tab, hash);
break;
}
//判斷索引每個元素的key是否與要插入的key相同，如果相同就直接覆蓋
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是null，說明沒有迭代到最后就跳出了循環(huán)，說明鏈表中有相同的key，
//因此只需要將value覆蓋，并將oldValue返回即可
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//空方法留給LinkedHashMap來實現(xiàn)
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果當前HashMap的容量超過threshold則進行擴容
if (++size > threshold)
resize();
//空方法留給LinkedHashMap來實現(xiàn)
afterNodeInsertion(evict);
return null;
}
思路如下：
- table[]是否為空.判斷table[i]處是否插入過值
- 判斷鏈表長度是否大于等于8，如果大于就轉(zhuǎn)換為紅黑二叉樹鏈表的樹化，并插入樹中 向二叉樹中添加hash值相同的節(jié)點
- 判斷key是否和原有key相同，如果相同就覆蓋原有key的value，并返回原有value確定hash值
- 如果key不相同，就插入一個key，記錄結(jié)構(gòu)變化一次 擴充機制
1. 鏈表的樹化
final void treeifyBin(Node<K, V>[] tab, int hash) {
int n, index;
Node<K, V> e;
//鏈表的長度檢測 MIN_TREEIFY_CAPACITY=64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//長度不夠就擴充
resize();
//根據(jù)hash值和數(shù)組長度進行取模運算后，得到鏈表的首節(jié)點
else if ((e = tab[index = (n - 1) & hash]) != null) {
//首節(jié)點,尾結(jié)點
TreeNode<K, V> hd = null, tl = null;
do {
// 將該節(jié)點轉(zhuǎn)換為樹節(jié)
TreeNode<K, V> p = replacementTreeNode(e, null);
// 如果尾節(jié)點為空，說明還沒有根節(jié)點
if (tl == null)
//首節(jié)點指向P
hd = p;
else {
//首節(jié)點的前一個節(jié)點指樹的向尾結(jié)點
p.prev = tl;
//樹尾結(jié)點的下一個節(jié)點指向p
tl.next = p;
}
//把當前節(jié)點設(shè)置為尾結(jié)點或者說根節(jié)點
tl = p;
//繼續(xù)遍歷鏈表
} while ((e = e.next) != null);
//到目前為止 也只是把Node對象轉(zhuǎn)換成了TreeNode對象，把單向鏈表轉(zhuǎn)換成了雙向鏈表,把轉(zhuǎn)換后的雙向鏈表，替換原來位置上的單向鏈表
if ((tab[index] = hd) != null)
//treeify方法是TreeNode類的一個實例方法，通過TreeNode對象調(diào)用，實現(xiàn)該對象打頭的鏈表轉(zhuǎn)換為樹結(jié)構(gòu)。
hd.treeify(tab);
}
//鏈表樹化
TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
2. 向二叉樹中添加節(jié)點
final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
//標識是否已經(jīng)遍歷過一次樹，未必是從根節(jié)點遍歷的，但是遍歷路徑上一定已經(jīng)包含了后續(xù)需要比對的所有節(jié)點
boolean searched = false;
//父節(jié)點不為空那么查找根節(jié)點，為空那么自身就是根節(jié)點
TreeNode<K, V> root = (parent != null) ? root() : this;
//從根節(jié)點開始遍歷，沒有終止條件，只能從內(nèi)部退出
for (TreeNode<K, V> p = root; ; ) {
int dir, ph;
K pk;
// 如果當前節(jié)點hash 大于 指定key的hash值
if ((ph = p.hash) > h)
dir = -1;// 要添加的元素應(yīng)該放置在當前節(jié)點的左側(cè)
else if (ph < h)
dir = 1;//要添加的元素應(yīng)該放置在當前節(jié)點的右側(cè)
//如果當前節(jié)點的鍵對象和指定key對象相同
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 走到這一步說明 當前節(jié)點的hash值和指定key的hash值是相等的，但是equals不等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//指定key沒有實現(xiàn)comparable接口或者實現(xiàn)了comparable接口并且和當前節(jié)點的鍵對象比較之后相等（僅限第一次循環(huán)）
/*
* searched 標識是否已經(jīng)對比過當前節(jié)點的左右子節(jié)點了
* 如果還沒有遍歷過，那么就遞歸遍歷對比，看是否能夠得到那個鍵對象equals相等的的節(jié)點
* 如果得到了鍵的equals相等的的節(jié)點就返回
* 如果還是沒有鍵的equals相等的節(jié)點，那說明應(yīng)該創(chuàng)建一個新節(jié)點了
*/
if (!searched) {
TreeNode<K, V> q, ch;
searched = true;// 標識已經(jīng)遍歷過一次了
/* 紅黑樹也是二叉樹，所以只要沿著左右兩側(cè)遍歷尋找就可以了
* 這是個短路運算，如果先從左側(cè)就已經(jīng)找到了，右側(cè)就不需要遍歷了
* find 方法內(nèi)部還會有遞歸調(diào)用。參見：find方法解析
*/
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//走到這里就說明，遍歷了所有子節(jié)點也沒有找到和當前鍵equals相等的節(jié)點
dir = tieBreakOrder(k, pk);
}
TreeNode<K, V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 如果恰好要添加的方向上的子節(jié)點為空，此時節(jié)點p已經(jīng)指向了這個空的子節(jié)點
Node<K, V> xpn = xp.next;// 獲取當前節(jié)點的next節(jié)點
TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);// 創(chuàng)建一個新的樹節(jié)點
if (dir <= 0)
xp.left = x;// 左子樹指向到這個新的樹節(jié)點
else
xp.right = x;
xp.next = x;// 鏈表中的next節(jié)點指向到這個新的樹節(jié)點
x.parent = x.prev = xp;// 這個新的樹節(jié)點的父節(jié)點、前節(jié)點均設(shè)置為 當前的樹節(jié)點
if (xpn != null)// 如果原來的next節(jié)點不為空
((TreeNode<K, V>) xpn).prev = x;// 那么原來的next節(jié)點的前節(jié)點指向到新的樹節(jié)點
moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根節(jié)點置頂
return null;// 返回空，意味著產(chǎn)生了一個新節(jié)點
}
}
}
3 .確定哈希桶數(shù)據(jù)索引位置
static final int hash(Object key) {
int h;
// h = key.hashCode() 為第一步 取hashCode值
// h ^ (h >>> 16) 為第二步 高位參與運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二：
static int indexFor(int h, int length) { //jdk1.7的源碼，jdk1.8沒有這個方法，但是實現(xiàn)原理一樣的
return h & (length-1); //第三步 取模運算
}
3.擴容機制
HashMap的擴容分為三種情況
- 使用默認構(gòu)造方法初始化
HashMap。從前文可以知道HashMap在一開始初始化的時候會返回一個空的table，并且thershold為0。因此第一次擴容的容量為默認值DEFAULT_INITIAL_CAPACITY也就是16。同時threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。int threshold; //= 負載因子 * 默認容量 - 指定初始容量的構(gòu)造方法初始化
HashMap。那么從下面源碼可以看到初始容量會等于threshold，接著threshold =當前的容量（threshold） * DEFAULT_LOAD_FACTOR。int threshold;//=負載因子*當前容量 -
HashMap不是第一次擴容。如果HashMap已經(jīng)擴容過的話，那么每次table的容量以及threshold量為原有的兩倍。
//put方法中
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;//table為null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //默認構(gòu)造器下為0
int newCap, newThr = 0;
if (oldCap > 0) { //之前有擴容過
//當前table容量大于最大值得時候 返回當前table
if (oldCap >= MAXIMUM_CAPACITY) {
//容量為整形最大值
threshold = Integer.MAX_VALUE;
return oldTab;
//table的容量乘以2，threshold的值也乘以2
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
//使用帶有初始容量的構(gòu)造器時，table容量為初始化得到的threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//默認構(gòu)造器下進行擴容
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //16
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //12
}
//使用帶有初始容量的構(gòu)造器在此處進行擴容
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ù)組賦值給table
//對新擴容后的table進行賦值
if (oldTab != null) {
////通過原容量遍歷原數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//判斷node上是否有鏈表
if (e.next == null)
//無鏈表，確定元素存放位置，
//擴容前的元素地址為 (oldCap - 1) & e.hash ,所以這里的新的地址只有兩種可能，
//一是地址不變，二是變?yōu)?老位置+oldCap
newTab[e.hash & (newCap - 1)] = 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;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
LinkedHashMap
概述
LinkedHashMap通過維護一個運行于所有條目的雙向鏈表，并允許使用null值和null鍵。LinkedHashMap保證了元素迭代的順序。該迭代順序可以是插入順序或者是訪問順序
LinkedHashMap可以認為是HashMap+LinkedList，即它既使用HashMap操作數(shù)據(jù)結(jié)構(gòu)，又使用LinkedList維護插入元素的先后順序
LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
//雙鏈表的頭和尾
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
//具體實現(xiàn)就是HashMap的Node節(jié)點
super(hash, key, value, next);
}
}
看看源碼吧
基本構(gòu)造
//雙鏈表的頭部
transient LinkedHashMapEntry<K,V> head;
//尾部
transient LinkedHashMapEntry<K,V> tail;
//排序模式 false 表示插入順序 true 訪問順序
final boolean accessOrder;
//默認無參構(gòu)造
public LinkedHashMap() {
//調(diào)用父類的無參構(gòu)造
super();
//排序模式設(shè)置為 插入順序 從源碼可以知道它的構(gòu)造函數(shù)中accessOrder 一直為false即插入順序
accessOrder = false;
}
/* ... 省略其他構(gòu)造函數(shù) 如果想了解其他知識請自行對照源碼閱讀 本文只是提供閱讀源碼的思路 */
}
get(key)
public V get(Object key) {
//定義節(jié)點
Node<K,V> e;
//通過key獲取key的hash值對應(yīng)的Node節(jié)點e并且e等于null的情況下返回null 詳情HashMap的get()
//注意這里返回的是Node節(jié)點這個Node節(jié)點是HashMap的數(shù)據(jù)結(jié)構(gòu) 并不是linkedHashmap存儲的LinkedHashMapEntry節(jié)點
if ((e = getNode(hash(key), key)) == null)
return null;
//初始化中賦值 accessOrder = false;
if (accessOrder)
//這個方法是hashmap的,但是hashmap是空方法 具體實現(xiàn)就是在linkedHashmap中
afterNodeAccess(e);
return e.value;
}
//這個方法的只要作用就是將順序顛倒過來 或者說倒序排列
void afterNodeAccess(Node<K,V> e) {
//定義最后一個節(jié)點
LinkedHashMapEntry<K,V> last;
//accessOrder 插入順序 并且把尾結(jié)點賦值給last 判斷當前節(jié)點e不等于最后一個節(jié)點
if (accessOrder && (last = tail) != e) {
//把當前Node節(jié)點轉(zhuǎn)換成linkedHashmap存儲的LinkedHashMapEntry節(jié)點 邏輯如下
LinkedHashMapEntry<K,V> p =(LinkedHashMapEntry<K,V>)e,
b = p.before, a = p.after;
//P的尾結(jié)點置空 這個很重要 參照下圖去理解,也可以看看put的過程回過來看這個流程
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;
}
}
afterNodeAccess方法邏輯圖.png
put()
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
//evict=true 成立
//(first = head) != null首節(jié)點不等于空
//removeEldestEntry(first) removeEldestEntry方法返回true值指定插入元素時移除最老的元素removeEldestEntry 這個方法適合做LRU算法 后續(xù)
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//移除首節(jié)點
removeNode(hash(key), key, null, false, true);
}
}
?```
