徹底理解HashMap及LinkedHashMap
作者：GeorgiaStar
blog.csdn.net/fuzhongmin05/article/details/104355841
HashMap是Map族中最為常用的一種，也是Java Collection Framework的重要成員。HashMap和雙向鏈表合二為一即是LinkedHashMap。所謂LinkedHashMap，其落腳點(diǎn)在HashMap，因此更準(zhǔn)確地說(shuō)，它是一個(gè)將所有Node節(jié)點(diǎn)鏈入一個(gè)雙向鏈表的HashMap。
下面基于JDK 1.8的源碼來(lái)學(xué)習(xí)HashMap及LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)、原理。不同JDK版本之間也許會(huì)有些許差異，但不影響原理學(xué)習(xí)，JDK8相比以前對(duì)HashMap的修改比較大。
1、HashMap概述
Map是 Key-Value鍵值對(duì)映射的抽象接口，該映射不包括重復(fù)的鍵，即一個(gè)鍵對(duì)應(yīng)一個(gè)值。HashMap是Java Collection Framework的重要成員，也是Map族(如下圖所示)中我們最為常用的一種。
簡(jiǎn)單地說(shuō)，HashMap是基于哈希表的Map接口的實(shí)現(xiàn)，以Key-Value的形式存在，即存儲(chǔ)的對(duì)象是 Node (同時(shí)包含了Key和Value) 。
在HashMap中，其會(huì)根據(jù)hash算法來(lái)計(jì)算key-value的存儲(chǔ)位置并進(jìn)行快速存取。特別地，HashMap最多只允許一條Node的key為Null，但允許多條Node的value為Null。此外，HashMap是Map 的一個(gè)非同步的實(shí)現(xiàn)。
以下是HashMap的類(lèi)繼承圖
必須指出的是，雖然容器號(hào)稱(chēng)存儲(chǔ)的是 Java 對(duì)象，但實(shí)際上并不會(huì)真正將 Java 對(duì)象放入容器中，只是在容器中保留這些對(duì)象的引用。也就是說(shuō)，Java 容器實(shí)際上包含的是引用變量，而這些引用變量指向了我們要實(shí)際保存的 Java 對(duì)象。
1.1、HashMap定義及構(gòu)造函數(shù)
JDK中的定義為
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
//...
}
HashMap 一共提供了四個(gè)構(gòu)造函數(shù)，其中 默認(rèn)無(wú)參的構(gòu)造函數(shù) 和 參數(shù)為Map的構(gòu)造函數(shù) 為 Java Collection Framework 規(guī)范的推薦實(shí)現(xiàn)，其余兩個(gè)構(gòu)造函數(shù)則是 HashMap 專(zhuān)門(mén)提供的。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//僅僅將負(fù)載因子初始化為默認(rèn)值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// all other fields defaulted
}
HashMap(int initialCapacity, float loadFactor)構(gòu)造函數(shù)意在構(gòu)造一個(gè)指定初始容量和指定負(fù)載因子的空HashMap，其源碼如下：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//容量最大為2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//這里調(diào)用函數(shù)計(jì)算觸發(fā)擴(kuò)容的閾值，threshold/loadFactor就是容量
this.threshold = tableSizeFor(initialCapacity);
}
以上構(gòu)造函數(shù)的最后一行就是jdk8的修改，實(shí)際上在jdk7之前的版本，這個(gè)構(gòu)造方法最后一行就是：
table = new Entry[capacity];
但是jdk8的最后一行并沒(méi)有立刻new出一個(gè)數(shù)組，而是調(diào)用了tableSizeFor方法，將結(jié)果賦值給了threshold變量。tableSizeFor方法源碼如下，從注釋就可以看出來(lái)，其目的是要獲得大于cap的最小的2的冪。比如cap=10，則返回16。
/**
* 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;
}
1.2、HashMap的數(shù)據(jù)結(jié)構(gòu)
我們知道，在Java中最常用的兩種結(jié)構(gòu)是數(shù)組和鏈表，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來(lái)組合實(shí)現(xiàn)，HashMap就是這種應(yīng)用的一個(gè)典型。
實(shí)際上，經(jīng)典的HashMap就是一個(gè)鏈表數(shù)組，只是jdk1.8再次對(duì)經(jīng)典hashMap的數(shù)據(jù)結(jié)構(gòu)作了小幅調(diào)整，如下是當(dāng)前HaspMap的數(shù)據(jù)結(jié)構(gòu)：
在JDK1.6和JDK1.7中，HashMap采用數(shù)組+鏈表實(shí)現(xiàn)，即使用鏈表處理沖突，同一hash值的key-value鍵值對(duì)都存儲(chǔ)在一個(gè)鏈表里。但是當(dāng)數(shù)組中一個(gè)位置上的元素較多，即hash值相等的元素較多時(shí)，通過(guò)key值依次查找的效率較低。
而在JDK1.8中，HashMap采用數(shù)組+鏈表+紅黑樹(shù)實(shí)現(xiàn)，當(dāng)鏈表長(zhǎng)度超過(guò)閾值8時(shí)，并且數(shù)組總?cè)萘砍^(guò)64時(shí)，將鏈表轉(zhuǎn)換為紅黑樹(shù)，這樣大大減少了查找時(shí)間。從鏈表轉(zhuǎn)換為紅黑樹(shù)后新加入鍵值對(duì)的效率降低，但查詢(xún)、刪除的效率都變高了。而當(dāng)發(fā)生擴(kuò)容或remove鍵值對(duì)導(dǎo)致原有的紅黑樹(shù)內(nèi)節(jié)點(diǎn)數(shù)量小于6時(shí)，則又將紅黑樹(shù)轉(zhuǎn)換成鏈表。
每一個(gè)HashMap都有一個(gè)Node類(lèi)型的table數(shù)組，其中Node類(lèi)型的定義如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 聲明 hash 值為 final 的
final K key; // 聲明 key 為 final 的
V value; // 鍵值對(duì)的值
Node<K,V> next; // 指向下一個(gè)節(jié)點(diǎn)的引用
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
Node為HashMap的內(nèi)部類(lèi)，實(shí)現(xiàn)了Map.Entry接口，其包含了鍵key、值value、下一個(gè)節(jié)點(diǎn)next，以及hash值四個(gè)屬性。事實(shí)上，Node是構(gòu)成哈希表的基石，是哈希表所存儲(chǔ)的元素的具體形式。值得注意的是，int類(lèi)型的hash值及引用變量key都被聲明成final，即不可變。
1.3、HashMap的快速存取
在HashMap中，我們最常用的兩個(gè)操作就是：put(Key,Value)和get(Key)。我們都知道，HashMap中的Key是唯一的，那它是如何保證唯一性的呢？
我們首先想到的是用equals比較，沒(méi)錯(cuò)，這樣是可以實(shí)現(xiàn)的，但隨著元素的增多，put和get的效率將越來(lái)越低，這里的時(shí)間復(fù)雜度是O(n)。也就是說(shuō)，假如HashMap有1000個(gè)元素，那么put時(shí)就需要比較1000次，這是相當(dāng)耗時(shí)的，遠(yuǎn)達(dá)不到HashMap快速存取的目的。
實(shí)際上，HashMap很少會(huì)用到equals方法，因?yàn)槠鋬?nèi)通過(guò)一個(gè)哈希表管理所有元素，利用哈希算法可以快速的存取元素。當(dāng)我們調(diào)用put方法存值時(shí)，HashMap首先會(huì)調(diào)用Key的hashCode方法，然后基于此值獲取Key的哈希碼，通過(guò)哈希碼快速找到某個(gè)位置，這個(gè)位置可以被稱(chēng)之為 bucketIndex。
根據(jù)equals方法與hashCode的協(xié)定可以知道，如果兩個(gè)對(duì)象的hashCode不同，那么equals一定為 false；如果其hashCode相同，equals也不一定為true。所以，理論上，hashCode 可能存在碰撞的情況，當(dāng)碰撞發(fā)生時(shí)，這時(shí)會(huì)取出bucketIndex桶內(nèi)已存儲(chǔ)的元素（如果該桶next引用不空，即有了鏈表也要遍歷鏈表），并通過(guò)hashCode()和equals()來(lái)逐個(gè)比較以判斷Key是否已存在。
如果已存在，則使用新Value值替換舊Value值，并返回舊Value值；如果不存在，則存放新的鍵值對(duì)<Key, Value>到鏈表中。因此，在HashMap中，equals()方法只有在哈希碼碰撞時(shí)才會(huì)被用到。
結(jié)合源碼來(lái)看HashMap的put操作：
public V put(K key, V value) {
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; Node<K,V> p; int n, i;
//第一次put元素時(shí)，table數(shù)組為空，先調(diào)用resize生成一個(gè)指定容量的數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash值和n-1的與運(yùn)算結(jié)果為桶的位置，如果該位置空就直接放置一個(gè)Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果計(jì)算出的bucket不空，即發(fā)生哈希沖突，就要進(jìn)一步判斷
else {
Node<K,V> e; K k;
//判斷當(dāng)前Node的key與要put的key是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷當(dāng)前Node是否是紅黑樹(shù)的節(jié)點(diǎn)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//以上都不是，說(shuō)明要new一個(gè)Node，加入到鏈表中
else {
for (int binCount = 0; ; ++binCount) {
//在鏈表尾部插入新節(jié)點(diǎn)，注意jdk1.8是在鏈表尾部插入新節(jié)點(diǎn)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果當(dāng)前鏈表中的元素大于樹(shù)化的閾值，進(jìn)行鏈表轉(zhuǎn)樹(shù)的操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//在鏈表中繼續(xù)判斷是否已經(jīng)存在完全相同的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//走到這里，說(shuō)明本次put是更新一個(gè)已存在的鍵值對(duì)的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//在hashMap中，afterNodeAccess方法體為空，交給子類(lèi)去實(shí)現(xiàn)
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果當(dāng)前size超過(guò)臨界值，就擴(kuò)容。注意是先插入節(jié)點(diǎn)再擴(kuò)容
if (++size > threshold)
resize();
//在hashMap中，afterNodeInsertion方法體為空，交給子類(lèi)去實(shí)現(xiàn)
afterNodeInsertion(evict);
return null;
}
通過(guò)上述源碼我們可以清楚了解到HashMap保存數(shù)據(jù)的過(guò)程。先計(jì)算key的hash值，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素，則查找是否存在相同的key，若存在則覆蓋原來(lái)key的value，否則將該元素保存在鏈表尾部，注意JDK1.7中采用的是頭插法，即每次都將沖突的鍵值對(duì)放置在鏈表頭，這樣最初的那個(gè)鍵值對(duì)最終就會(huì)成為鏈尾，而JDK1.8中使用的是尾插法。 此外，若table在該處沒(méi)有元素，則直接保存。
對(duì)于hash函數(shù)，具體的來(lái)看下源碼
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
以上可以看到key==null時(shí)，直接返回0，所以HashMap中鍵為NULL的鍵值對(duì)，一定在第一個(gè)桶中。
h >>> 16是用來(lái)取出h的高16位(>>>是無(wú)符號(hào)右移) 如下展示：
0000 0100 1011 0011 1101 1111 1110 0001
>>> 16
0000 0000 0000 0000 0000 0100 1011 0011
通過(guò)之前putVal的源碼可以知道，HashMap是用(length - 1) & hash來(lái)計(jì)算數(shù)組下標(biāo)的。絕大多數(shù)情況下length一般都小于2^16即小于65536。所以hash & (length-1)；結(jié)果始終是hash的低16位與（length-1）進(jìn)行&運(yùn)算。要是能讓hash的高16位也參與運(yùn)算，會(huì)讓得到的下標(biāo)更加散列。
如何讓高16也參與運(yùn)算呢。方法就是讓hashCode()和自己的高16位進(jìn)行^運(yùn)算。由于與運(yùn)單和或運(yùn)單都會(huì)使得結(jié)果偏向0或者1，并不是均勻的概念，所以用異或。
結(jié)合源碼來(lái)看HashMap的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;
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) {
//如果是紅黑樹(shù)，就調(diào)用樹(shù)的查找方法，否則遍歷鏈表直到找到
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;
}
在這里能夠根據(jù)key快速的取到value，除了和HashMap的數(shù)據(jù)結(jié)構(gòu)密不可分外，還和Node有莫大的關(guān)系。在前面就已經(jīng)提到過(guò)，HashMap在存儲(chǔ)過(guò)程中并沒(méi)有將key/value分開(kāi)來(lái)存儲(chǔ)，而是當(dāng)做一個(gè)整體key-value來(lái)處理的，這個(gè)整體就是Node對(duì)象。
1.4 為什么HashMap的底層數(shù)組長(zhǎng)度總是2的n次方
當(dāng)?shù)讓訑?shù)組的length為2的n次方時(shí)， hash & (length - 1) 就相當(dāng)于對(duì)length取模，其效率要比直接取模高得多，這是HashMap在效率上的一個(gè)優(yōu)化。
我們希望HashMap中的元素存放的越均勻越好。最理想的效果是，Node數(shù)組中每個(gè)位置都只有一個(gè)元素，這樣，查詢(xún)的時(shí)候效率最高，不需要遍歷單鏈表，也不需要通過(guò)equals去比較Key，而且空間利用率最大。
那如何計(jì)算才會(huì)分布最均勻呢？正如上一節(jié)提到的，HashMap采用了一個(gè)分兩步走的哈希策略：
使用 hash()方法用于對(duì)Key的hashCode進(jìn)行重新計(jì)算，以防止質(zhì)量低下的hashCode()函數(shù)實(shí)現(xiàn)。由于hashMap的支撐數(shù)組長(zhǎng)度總是2的倍數(shù)，通過(guò)右移可以使低位的數(shù)據(jù)盡量的不同，從而使Key的hash值的分布盡量均勻；使用 hash & (length - 1)方法進(jìn)行取余運(yùn)算，以使每個(gè)鍵值對(duì)的插入位置盡量分布均勻；
由于length是2的整數(shù)冪，length-1的低位就全是1，高位全部是0。在與hash值進(jìn)行低位&運(yùn)算時(shí)，低位的值總是與原來(lái)hash值相同，高位&運(yùn)算時(shí)值為0。這就保證了不同的hash值發(fā)生碰撞的概率比較小，這樣就會(huì)使得數(shù)據(jù)在table數(shù)組中分布較均勻，查詢(xún)速度也較快。
1.5 HashMap的擴(kuò)容
隨著HashMap中元素的數(shù)量越來(lái)越多，發(fā)生碰撞的概率將越來(lái)越大，所產(chǎn)生的子鏈長(zhǎng)度就會(huì)越來(lái)越長(zhǎng)，這樣勢(shì)必會(huì)影響HashMap的存取速度。為了保證HashMap的效率，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理，該臨界點(diǎn)就是HashMap中元素的數(shù)量在數(shù)值上等于threshold（table數(shù)組長(zhǎng)度*加載因子）。 但是，不得不說(shuō)，擴(kuò)容是一個(gè)非常耗時(shí)的過(guò)程，因?yàn)樗枰匦掠?jì)算這些元素在新table數(shù)組中的位置并進(jìn)行復(fù)制處理。
首先回答一個(gè)問(wèn)題，在插入一個(gè)臨界節(jié)點(diǎn)時(shí)，HashMap是先擴(kuò)容后插入還是先插入后擴(kuò)容？這樣選取的優(yōu)勢(shì)是什么？
答案是：先插入后擴(kuò)容。通過(guò)查看putVal方法的源碼可以發(fā)現(xiàn)是先執(zhí)行完新節(jié)點(diǎn)的插入后，然后再做size是否大于threshold的判斷的。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
//如果插入新結(jié)點(diǎn)后的size超過(guò)了臨界值，就擴(kuò)容，注意是先插入節(jié)點(diǎn)再擴(kuò)容
if (++size > threshold)
resize();
//在hashMap中，afterNodeInsertion方法體為空，交給子類(lèi)去實(shí)現(xiàn)
afterNodeInsertion(evict);
return null;
}
為什么是先插入后擴(kuò)容？源碼已經(jīng)很清楚的表達(dá)了擴(kuò)容原因，調(diào)用put不一定是新增數(shù)據(jù)，還可能是覆蓋掉原來(lái)的數(shù)據(jù)，這里就存在一個(gè)key的比較問(wèn)題。推薦：Java面試題寶典
以先擴(kuò)容為例，先比較是否是新增的數(shù)據(jù)，再判斷增加數(shù)據(jù)后是否要擴(kuò)容，這樣比較會(huì)浪費(fèi)時(shí)間，而先插入后擴(kuò)容，就有可能在中途直接通過(guò)return返回了（本次put是覆蓋操作，size不變不需要擴(kuò)容），這樣可以提高效率的。
JDK1.8相對(duì)于JDK1.7對(duì)HashMap的實(shí)現(xiàn)有較大改進(jìn)，做了很多優(yōu)化，鏈表轉(zhuǎn)紅黑樹(shù)是其中的一項(xiàng)，其實(shí)擴(kuò)容方法JDK1.8也有優(yōu)化，與JDK1.7有較大差別。
JDK1.8中resize方法源碼如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 原來(lái)的容量就已經(jīng)超過(guò)最大值就不再擴(kuò)容了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒(méi)超過(guò)最大值，就擴(kuò)容為原來(lái)的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
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);
}
// 計(jì)算新的resize上限，即新的threshold值
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;
if (oldTab != null) {
// 把舊的bucket都移動(dòng)到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
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;
//原來(lái)的桶索引值
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);
// 擴(kuò)容后，鍵值對(duì)在新table數(shù)組中的位置與舊數(shù)組中一樣
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 擴(kuò)容后，鍵值對(duì)在新table數(shù)組中的位置與舊數(shù)組中不一樣
// 新的位置=原來(lái)的位置 + oldCap
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
必要的位置已經(jīng)加了注釋。最讓人疑惑的有兩個(gè)點(diǎn)：
為什么 （e.hash & oldCap）== 0時(shí)就放入lo鏈表，否則就是hi鏈表;為什么 j + oldCap就是鍵值對(duì)在新的table數(shù)組中的位置；
其實(shí)這里包含著一些數(shù)學(xué)技巧。類(lèi)似于上一小節(jié)為什么HashMap中數(shù)組的長(zhǎng)度總是取2的整數(shù)次冪。
查看源碼，我們發(fā)現(xiàn)擴(kuò)容時(shí)，使用的是2次冪的擴(kuò)展即長(zhǎng)度擴(kuò)為原來(lái)2倍，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。
看下圖可以明白這句話的意思，n為table的長(zhǎng)度，圖中上半部分表示擴(kuò)容前的key1和key2兩個(gè)Node的索引位置，圖中下半部分表示擴(kuò)容后key1和key2兩個(gè)Node新的索引位置。
元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍，那么n-1在高位多1bit，因此新的index就會(huì)發(fā)生這樣的變化：
因此，我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要像JDK1.7的實(shí)現(xiàn)那樣重新hash，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒(méi)變，是1的話索引變成“原索引+oldCap”，這個(gè)設(shè)計(jì)確實(shí)非常的巧妙，既省去了重新hash值的時(shí)間，而且同時(shí)，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過(guò)程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了，這一塊就是JDK1.8新增的優(yōu)化點(diǎn)。
1.6 HashMap為什么引入紅黑樹(shù)而不是AVL樹(shù)
上面這個(gè)問(wèn)題也可以理解為：有了二叉查找樹(shù)、平衡樹(shù)（AVL）為啥還需要紅黑樹(shù)？
二叉查找樹(shù)，也稱(chēng)有序二叉樹(shù)（ordered binary tree），或已排序二叉樹(shù)（sorted binary tree），是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：
若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù); 沒(méi)有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）
因?yàn)橐豢糜蒒個(gè)結(jié)點(diǎn)隨機(jī)構(gòu)造的二叉查找樹(shù)的高度為logN，所以順理成章，二叉查找樹(shù)的一般操作的執(zhí)行時(shí)間為O(logN)。但二叉查找樹(shù)若退化成了一棵具有N個(gè)結(jié)點(diǎn)的線性鏈后，則這些操作最壞情況運(yùn)行時(shí)間為O(N)。
可想而知，我們不能讓這種情況發(fā)生，為了解決這個(gè)問(wèn)題，于是我們引申出了平衡二叉樹(shù)，即AVL樹(shù)，它對(duì)二叉查找樹(shù)做了改進(jìn)，在我們每插入一個(gè)節(jié)點(diǎn)的時(shí)候，必須保證每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的左子樹(shù)和右子樹(shù)的樹(shù)高度差不超過(guò)1。如果超過(guò)了就對(duì)其進(jìn)行左旋或右旋，使之平衡。
雖然平衡樹(shù)解決了二叉查找樹(shù)退化為近似鏈表的缺點(diǎn)，能夠把查找時(shí)間控制在 O(logN)，不過(guò)卻不是最佳的，因?yàn)槠胶鈽?shù)要求每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差至多等于1，這個(gè)要求實(shí)在是太嚴(yán)了，導(dǎo)致每次進(jìn)行插入/刪除節(jié)點(diǎn)的時(shí)候，幾乎都會(huì)破壞平衡樹(shù)的規(guī)則，進(jìn)而我們都需要通過(guò)左旋和右旋來(lái)進(jìn)行調(diào)整，使之再次成為一顆符合要求的平衡樹(shù)。
顯然，如果在那種插入、刪除很頻繁的場(chǎng)景中，平衡樹(shù)需要頻繁著進(jìn)行調(diào)整，這會(huì)使平衡樹(shù)的性能大打折扣，為了解決這個(gè)問(wèn)題，于是有了紅黑樹(shù)。紅黑樹(shù)是不符合AVL樹(shù)的平衡條件的，即每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多差1的二叉查找樹(shù)，但是提出了為節(jié)點(diǎn)增加顏色，紅黑樹(shù)是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，相較于AVL樹(shù)為了維持平衡的開(kāi)銷(xiāo)要小得多。
AVL樹(shù)是嚴(yán)格平衡樹(shù)，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹(shù)要多，所以紅黑樹(shù)的插入效率相對(duì)于AVL樹(shù)更高。單單在查找方面比較效率的話，由于AVL高度平衡，因此AVL樹(shù)的查找效率比紅黑樹(shù)更高。
對(duì)主要的幾種平衡樹(shù)作個(gè)比較，發(fā)現(xiàn)紅黑樹(shù)有著良好的穩(wěn)定性和完整的功能，性能表現(xiàn)也很不錯(cuò)，綜合實(shí)力強(qiáng)，在諸如STL的場(chǎng)景中需要穩(wěn)定表現(xiàn)。實(shí)際應(yīng)用中，若搜索的頻率遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL，如果發(fā)生搜索和插入刪除操作的頻率差不多，應(yīng)該選擇紅黑樹(shù)。
1.7 HashMap的線程不安全
所有人都知道HashMap是線程不安全的，我們應(yīng)該使用ConcurrentHashMap。但是為什么HashMap是線程不安全的呢？
首先需要強(qiáng)調(diào)一點(diǎn)，HashMap的線程不安全體現(xiàn)在會(huì)造成死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋這些問(wèn)題。其中死循環(huán)和數(shù)據(jù)丟失是在JDK1.7中出現(xiàn)的問(wèn)題，在JDK1.8中已經(jīng)得到解決，然而1.8中仍會(huì)有數(shù)據(jù)覆蓋的問(wèn)題，即在并發(fā)執(zhí)行HashMap的put操作時(shí)會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。
首先擴(kuò)容會(huì)造成HashMap的線程不安全，根源就在JDK1.7的transfer函數(shù)中。transfer方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里。JDK1.7中HashMap的transfer函數(shù)源碼如下：
void transfer(Entry[] newTable) {
//src引用了舊的Entry數(shù)組
Entry[] src = table;
int newCapacity = newTable.length;
//遍歷舊的Entry數(shù)組
for (int j = 0; j < src.length; j++) {
//取得舊Entry數(shù)組的每個(gè)元素
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
//釋放舊Entry數(shù)組的對(duì)象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對(duì)象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
//重新計(jì)算每個(gè)元素在數(shù)組中的位置
e.next = newTable[i]; //標(biāo)記[1]
newTable[i] = e; //將元素放在數(shù)組上
e = next;
//訪問(wèn)下一個(gè)Entry鏈上的元素
} while (e != null);
}
}
}
這段代碼是HashMap的擴(kuò)容操作，重新定位每個(gè)桶的下標(biāo)，并采用頭插法將元素遷移到新數(shù)組中。頭插法會(huì)將鏈表的順序翻轉(zhuǎn)，這也是在多線程環(huán)境下會(huì)形成死循環(huán)的關(guān)鍵點(diǎn)。 擴(kuò)容造成死循環(huán)和數(shù)據(jù)丟失的詳細(xì)過(guò)程這里不再贅述，可以搜索很多分析這個(gè)過(guò)程的文章。
JDK1.8的源碼中已經(jīng)沒(méi)有transfer函數(shù)，因?yàn)镴DK1.8直接在resize函數(shù)中完成了數(shù)據(jù)遷移。此外JDK1.8在進(jìn)行元素插入時(shí)使用的是尾插法。為什么多線程環(huán)境下JDK1.8的HashMap會(huì)出現(xiàn)數(shù)據(jù)覆蓋的情況呢，我們來(lái)看一下JDK1.8中的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;
//第一次put元素時(shí)，table數(shù)組為空，先調(diào)用resize生成一個(gè)指定容量的數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash值和n-1的與運(yùn)算結(jié)果為桶的位置，如果該位置空就直接放置一個(gè)Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果計(jì)算出的bucket不空，即發(fā)生哈希沖突，就要進(jìn)一下判斷
else {
Node<K,V> e; K k;
//判斷當(dāng)前Node的key與要put的key是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷當(dāng)前Node是否是紅黑樹(shù)的節(jié)點(diǎn)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//以上都不是，說(shuō)明要new一個(gè)Node，加入到鏈表中
else {
for (int binCount = 0; ; ++binCount) {
//進(jìn)入這個(gè)if說(shuō)明是到達(dá)鏈表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//在鏈表中繼續(xù)判斷是否已經(jīng)存在完全相同的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//走到這里，說(shuō)明本次put是更新一個(gè)已存在的鍵值對(duì)的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//在hashMap中，afterNodeAccess方法體為空，交給子類(lèi)去實(shí)現(xiàn)
afterNodeAccess(e);
return oldValue;
}
}
//下面兩個(gè)自增操作都不是原子的
++modCount;
if (++size > threshold)
resize();
//在hashMap中，afterNodeInsertion方法體為空，交給子類(lèi)去實(shí)現(xiàn)
afterNodeInsertion(evict);
return null;
}
其中if((p = tab[i = (n - 1) & hash]) == null)是判斷是否出現(xiàn)hash碰撞，假設(shè)兩個(gè)線程A、B都在進(jìn)行put操作，并且hash函數(shù)計(jì)算出的插入下標(biāo)是相同的，當(dāng)線程A執(zhí)行完這行代碼后由于時(shí)間片耗盡導(dǎo)致被掛起，而線程B得到時(shí)間片后在該下標(biāo)處插入了元素，完成了正常的插入，然后線程A獲得時(shí)間片，由于之前已經(jīng)進(jìn)行了hash碰撞的判斷，所以此時(shí)不會(huì)再進(jìn)行判斷，而是直接進(jìn)行插入，這就導(dǎo)致了線程B插入的數(shù)據(jù)被線程A覆蓋了，從而線程不安全。
除此之外，還有就是代碼的末尾部分有個(gè)++size，我們這樣想，還是線程A、B，這兩個(gè)線程同時(shí)進(jìn)行put操作時(shí)，假設(shè)當(dāng)前HashMap的size大小為10，當(dāng)線程A執(zhí)行到size自增這行代碼時(shí)，從主內(nèi)存中獲得size的值為10后準(zhǔn)備進(jìn)行+1操作，但是由于時(shí)間片耗盡只好讓出CPU，線程B拿到CPU還是從主內(nèi)存中拿到size的值10進(jìn)行+1操作，完成了put操作并將size=11寫(xiě)回主內(nèi)存，由于size不是volatile修改的變量，然后線程A再次拿到CPU后不會(huì)再?gòu)闹鲀?nèi)存中加載一次size的值，而是使用自己工作內(nèi)存中的副本，繼續(xù)執(zhí)行加1，當(dāng)執(zhí)行完put操作后，還是將size=11寫(xiě)回主內(nèi)存，此時(shí)，線程A、B都執(zhí)行了一次put操作，但是size的值只增加了1，所有說(shuō)還是由于數(shù)據(jù)覆蓋又導(dǎo)致了線程不安全。推薦：Java面試題寶典
2、LinkedHashMap概述
HashMap是Java Collection Framework的重要成員，也是Map族中我們最為常用的一種。不過(guò)遺憾的是，HashMap是無(wú)序的，也就是說(shuō)，迭代HashMap所得到的元素順序并不是它們最初放置到HashMap的順序。HashMap的這一缺點(diǎn)往往會(huì)造成諸多不便，因?yàn)樵谟行﹫?chǎng)景中，我們確需要用到一個(gè)可以保持插入順序的Map。
慶幸的是，JDK為我們解決了這個(gè)問(wèn)題，它為HashMap提供了一個(gè)子類(lèi) —— LinkedHashMap。雖然LinkedHashMap增加了時(shí)間和空間上的開(kāi)銷(xiāo)，但是它通過(guò)維護(hù)一個(gè)額外的雙向鏈表保證了迭代順序==。特別地，==該迭代順序可以是插入順序，也可以是訪問(wèn)順序。
因此，根據(jù)鏈表中元素的順序可以將LinkedHashMap分為：保持插入順序的LinkedHashMap和保持訪問(wèn)順序的LinkedHashMap，其中LinkedHashMap的默認(rèn)實(shí)現(xiàn)是按插入順序排序的。
更直觀地，下圖很好地還原了LinkedHashMap的原貌：HashMap和雙向鏈表的密切配合和分工合作造就了LinkedHashMap。特別需要注意的是，next用于維護(hù)HashMap各個(gè)桶中的Entry鏈，before、after用于維護(hù)LinkedHashMap的雙向鏈表，雖然它們的作用對(duì)象都是Entry，但是各自分離，是兩碼事兒。
特別地，由于LinkedHashMap是HashMap的子類(lèi)，所以LinkedHashMap自然會(huì)擁有HashMap的所有特性。比如，LinkedHashMap也最多只允許一條Entry的鍵為Null(多條會(huì)覆蓋)，但允許多條Entry的值為Null。
此外，LinkedHashMap 也是 Map 的一個(gè)非同步的實(shí)現(xiàn)。此外，LinkedHashMap還可以用來(lái)實(shí)現(xiàn)LRU (Least recently used, 最近最少使用)算法。
2.1、LinkedHashMap定義及構(gòu)造函數(shù)
本質(zhì)上，HashMap和雙向鏈表合二為一即是LinkedHashMap。JDK1.8中LinkedHashMap的定義源碼如下：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
//再加兩個(gè)引用，分別指向前一個(gè)插入的Entry與后一個(gè)插入的Entry
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* The head (eldest) of the doubly linked list.
* 頭節(jié)點(diǎn)引用
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
* 尾節(jié)點(diǎn)引用
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* true表示按照訪問(wèn)順序迭代，false時(shí)表示按照插入順序
* @serial
*/
final boolean accessOrder;
...
}
LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了Entry。LinkedHashMap中的Entry繼承了HashMap.Node，但增加了兩個(gè)指針before 和 after，它們分別用于維護(hù)雙向鏈接列表。特別需要注意的是，next用于維護(hù)HashMap各個(gè)Node的連接順序，before、after用于維護(hù)Entry插入的先后順序。
LinkedHashMap的5大構(gòu)造函數(shù)都是在HashMap的構(gòu)造函數(shù)的基礎(chǔ)上實(shí)現(xiàn)的，分別如下：
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;
}
2.2、LinkedHashMap的快速存取
在HashMap中最常用的兩個(gè)操作就是：put(Key,Value) 和 get(Key)。同樣地，在 LinkedHashMap 中最常用的也是這兩個(gè)操作。對(duì)于put(Key,Value)方法而言，LinkedHashMap完全繼承了HashMap的 put(Key,Value) 方法，只是對(duì)putVal(hash,key, value, onlyIfAbsent,evict)方法所調(diào)用的afterNodeAccess方法和afterNodeInsertion方法進(jìn)行了重寫(xiě)；對(duì)于get(Key)方法，LinkedHashMap則直接對(duì)它進(jìn)行了重寫(xiě)。
下面我們結(jié)合JDK源碼看 LinkedHashMap 的存取實(shí)現(xiàn)。
HashMap的putVal源碼，上一節(jié)中已經(jīng)分析過(guò)，直接來(lái)看LinkedHashMap對(duì)afterNodeAccess和afterNodeInsertion方法的實(shí)現(xiàn)：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
/**
* 如果map應(yīng)該刪除最老的節(jié)點(diǎn)，返回true
* 這個(gè)方法在被put和putAll方法被調(diào)用，當(dāng)向map中插入一個(gè)新的entry時(shí)被執(zhí)行。這個(gè)方法提供了當(dāng)一個(gè)新的entry被添加到linkedHashMap中，刪除最老節(jié)點(diǎn)的機(jī)會(huì)。
*
* 這個(gè)方法是很有用的，可以通過(guò)刪除最老節(jié)點(diǎn)來(lái)減少內(nèi)存消耗，避免溢出。
*
* 簡(jiǎn)單的例子：這個(gè)方法的重寫(xiě)將map的最大值設(shè)為100，到100時(shí)，每次增一個(gè)entry，就刪除一次最老節(jié)點(diǎn)。
*
* private static final int MAX_ENTRIES = 100;
*
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;
* }
*
* 這個(gè)方法一般不會(huì)直接修改map，而是通過(guò)返回true或者false來(lái)控制是否修改map。
*
*
* @param eldest 最老的節(jié)點(diǎn)（即頭節(jié)點(diǎn)）
* @return 如果map應(yīng)該刪除頭節(jié)點(diǎn)就返回true，否則返回false
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
以上afterNodeInsertion方法由于removeEldestEntry方法默認(rèn)一直返回的false而無(wú)執(zhí)行意義。也就意味著如果想要讓它有意義必須重寫(xiě)removeEldestEntry方法。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
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;
}
}
可見(jiàn)僅有accessOrder為true時(shí)，且訪問(wèn)節(jié)點(diǎn)不等于尾節(jié)點(diǎn)時(shí)，該方法才有意義。通過(guò)before/after重定向，將新訪問(wèn)節(jié)點(diǎn)鏈接為鏈表尾節(jié)點(diǎn)。推薦：Java面試題寶典
LinkedHashMap的get操作：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
//當(dāng)accessOrder為true時(shí)，才會(huì)出現(xiàn)個(gè)性化邏輯
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
//以下是HashMap中的getNode方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
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;
}
在LinkedHashMap的get方法中，通過(guò)HashMap中的getNode方法獲取Node對(duì)象。
注意這里的afterNodeAccess方法，如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做；如果鏈表中元素的排序規(guī)則是按照訪問(wèn)的先后順序排序的話，則將e移到鏈表的末尾處。
2.3、LinkedHashMap與LRU算法
到此為止，我們已經(jīng)分析完了LinkedHashMap的存取實(shí)現(xiàn)，這與HashMap大體相同。LinkedHashMap區(qū)別于HashMap最大的一個(gè)不同點(diǎn)是，前者是有序的，而后者是無(wú)序的。為此，LinkedHashMap增加了兩個(gè)屬性用于保證順序，分別是雙向鏈表頭結(jié)點(diǎn)header和標(biāo)志位accessOrder。我們知道，header是LinkedHashMap所維護(hù)的雙向鏈表的頭結(jié)點(diǎn)，而accessOrder用于決定具體的迭代順序。
我們知道，當(dāng)accessOrder標(biāo)志位為true時(shí)，表示雙向鏈表中的元素按照訪問(wèn)的先后順序排列，可以看到，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有判斷accessOrder的值。
如果accessOrder為true，put時(shí)將新插入的元素放入到雙向鏈表的尾部，get時(shí)將當(dāng)前訪問(wèn)的Entry移到雙向鏈表的尾部。當(dāng)標(biāo)志位accessOrder的值為false時(shí)，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部，這樣遍歷雙向鏈表時(shí)，Entry的輸出順序便和插入的順序一致，這也是默認(rèn)的雙向鏈表的存儲(chǔ)順序。
測(cè)試代碼
@Test
public void testLinkedHashMap() {
Map<String, String> map = new HashMap<>(128);
System.out.println("------HashMap------");
map.put("first", "a");
map.put("second", "b");
map.put("third", "c");
map.put("fourth", "d");
map.put("fifth", "e");
map.put("sixth", "f");
map.forEach((key,value) -> {
System.out.println("key=" + key + ",value=" + value);
});
map.clear();
System.out.println("------LinkedHashMap------");
map = new LinkedHashMap<>(128);
map.put("first", "a");
map.put("second", "b");
map.put("third", "c");
map.put("fourth", "d");
map.put("fifth", "e");
map.put("sixth", "f");
map.forEach((key,value) -> {
System.out.println("key=" + key + ",value=" + value);
});
}
運(yùn)行結(jié)果如下，HashMap不保證有序而LinkedHashMap默認(rèn)按迭代順序和插入的順序一致。
前面介紹的LinkedHashMap的五種構(gòu)造方法，前四個(gè)構(gòu)造方法都將accessOrder設(shè)為false，說(shuō)明默認(rèn)是按照插入順序排序的；而第五個(gè)構(gòu)造方法可以自定義傳入的accessOrder的值。當(dāng)我們要用LinkedHashMap實(shí)現(xiàn)LRU算法時(shí)，就需要調(diào)用該構(gòu)造方法并將accessOrder置為true。
使用LinkedHashMap實(shí)現(xiàn)LRU的必要前提是將accessOrder標(biāo)志位設(shè)為true以便開(kāi)啟按訪問(wèn)順序排序的模式。我們可以看到，無(wú)論是put方法還是get方法，都會(huì)導(dǎo)致目標(biāo)Entry成為最近訪問(wèn)的Entry，因此就把該Entry加入到了雙向鏈表的末尾。這樣，我們便把最近使用的Entry放入到了雙向鏈表的后面。多次操作后，雙向鏈表前面的Entry便是最近沒(méi)有使用的，這樣當(dāng)節(jié)點(diǎn)個(gè)數(shù)滿(mǎn)的時(shí)候，刪除最前面的Entry即可，因?yàn)樗褪亲罱钌偈褂玫腅ntry。另外，關(guān)注Java知音公眾號(hào)，回復(fù)“后端面試”，送你一份面試題寶典！
public class SomeTest {
@Test
public void testLru() {
LRU<Character, Integer> lru = new LRU<>(8);
String s = "abcdefghijkl";
for (int i = 0; i < s.length(); i++) {
lru.put(s.charAt(i), i + 1);
}
System.out.println("LRU的大?。?nbsp;" + lru.size());
System.out.println(lru);
System.out.println("LRU的中key為h的value值： " + lru.get('h'));
System.out.println(lru);
lru.put('z', 26);
System.out.println(lru);
}
public static class LRU<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRU(int cacheSize) {
super(cacheSize, 0.75f, true);
this.cacheSize = cacheSize;
}
/**
* 重寫(xiě)LinkedHashMap中的removeEldestEntry方法，當(dāng)LRU中元素多余cacheSize個(gè)時(shí)，刪除最老的節(jié)點(diǎn)（即最不經(jīng)常使用的元素）
* @param eldest
* @return
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > getCacheSize();
}
public int getCacheSize() {
return cacheSize;
}
}
}
運(yùn)行結(jié)果：
LRU的大?。?
{e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12}
LRU的中key為h的value值：8
{e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8}
{f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}
最近給大家找了 Vue進(jìn)階
資源，怎么領(lǐng)??？
掃二維碼，加我微信，回復(fù)：Vue進(jìn)階
注意，不要亂回復(fù) 沒(méi)錯(cuò)，不是機(jī)器人 記得一定要等待，等待才有好東西