簡(jiǎn)述
HashMap是一種比較常見的map子類，是由數(shù)組+鏈表組成(JDK8以后采用的是數(shù)組+鏈表+紅黑樹的形式)。
元素是以鍵值對(duì)的形式存在，并且允許使用null作為鍵和值存入其中。另外HashMap是無序的(有序的可以使用LinkHashMap)，且是線程不安全的(線程安全的可以使用ConcurrentHashMap)。
首先看下HashMap的幾個(gè)構(gòu)造方法:
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
第一個(gè)就是最常見的無參構(gòu)造方法，這個(gè)構(gòu)造方法僅僅是初始化了加載因子，DEFAULT_LOAD_FACTOR為0.75。
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
接下來這兩個(gè)可以一起看:
- 單參數(shù)的構(gòu)造方法就是將初始容量傳入，然后加載因子設(shè)置成默認(rèn)值，然后調(diào)用兩個(gè)參數(shù)的構(gòu)造方法。
- 兩個(gè)參數(shù)的構(gòu)造方法控制了初始容量不可小于0，并且不能超過最大容量數(shù)，加載因子也不能小于0.最后調(diào)用tableSizeFor方法進(jìn)行HashMap的閾值的初始化。
tableSizeFor方法待會(huì)講。這里我們看到構(gòu)造方法里面我們有看到三個(gè)參數(shù):loadFactor，threshold和initialCapacity。默認(rèn)情況下加載因子為0.75，初始容量是16，閾值則為loadFactor * initialCapacity，一旦HashMap的size超過了閾值以后，HashMap就會(huì)進(jìn)行一次resize操作。
為什么要設(shè)置這個(gè)加載因子？
當(dāng)加載因子增大，意味著到時(shí)候填充的元素就越多了(因?yàn)閿U(kuò)容的門檻上升)，空間利用率提升了，但是hash沖突的概率就會(huì)增大會(huì)降低查找效率，是一種時(shí)間換空間的做法。當(dāng)加載因子減少，意味著填充的元素越少(擴(kuò)容門檻的下降會(huì)導(dǎo)致插入沒有多少元素就會(huì)進(jìn)行一次擴(kuò)容)，這樣空間利用率就低了，但是hash沖突的概率會(huì)降低提升了查找效率，是一種以空間換時(shí)間的做法。這樣可以根據(jù)項(xiàng)目本身的需要來設(shè)置不同的加載因子
默認(rèn)加載因子為什么是0.75?
注釋里面已經(jīng)有給出，下面這段注釋大致意思是說HashMap的Node分步頻率服從λ為0.5的泊松分布，當(dāng)長(zhǎng)度為16的數(shù)組中存入了12個(gè)數(shù)據(jù)的時(shí)候，其中一個(gè)鏈表的長(zhǎng)度為8的概率只有 0.00000006(鏈表長(zhǎng)度大于8的時(shí)候會(huì)轉(zhuǎn)化成紅黑樹)
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
好了，接下來看下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;
}
這方法其實(shí)是算出最接近當(dāng)前cap的2的n次冪值。第一步減1主要是為了防止當(dāng)前cap正好是2的n次冪值。為什么要這么做呢？我們舉個(gè)栗子：假設(shè)當(dāng)前cap是16。
- int n = cap - 1(n = 15)
- n |= n>>>1 (n先右移一位變成0b00111即7 ，然后做或運(yùn)算得0b01111即15)
- n |= n>>>2 (n先右移兩位變成0b00011即3，然后做或運(yùn)算得0b01111即15)
- n |= n>>>4 (n先右移三位變成0b00000即0，然后做或運(yùn)算得0b01111即15)
- n |= n>>>8 (n先右移四位變成0b00000即0，然后做或運(yùn)算得0b01111即15)
- n |= n>>>16 (n先右移四位變成0b00000即0，然后做或運(yùn)算得0b01111即15)
- 當(dāng)前n必然小于最大容量值，那么最后的結(jié)果就是16。
如果第一步?jīng)]有減1的操作，那么最后的結(jié)果就是是32，這樣會(huì)浪費(fèi)大量的空間。我們做tableSizeFor的操作目的就是獲得最接近當(dāng)前cap的2的n次冪值，所以當(dāng)cap等于16的時(shí)候最后的結(jié)果應(yīng)該是16而非32。
上面的步驟完全沒有體現(xiàn)2~6步的價(jià)值，那么我們接下來再舉個(gè)栗子看下:假設(shè)當(dāng)前cap是17
- int n = cap - 1(n = 16)
- n |= n>>>1 (n先右移一位變成0b01000即8 ，然后做或運(yùn)算得0b11000即24)
- n |= n>>>2 (n先右移兩位變成0b00110即6，然后做或運(yùn)算得0b11110即28)
- n |= n>>>4 (n先右移三位變成0b00001即1，然后做或運(yùn)算得0b11111即31)
- n |= n>>>8 (n先右移四位變成0b00000即0，然后做或運(yùn)算得0b11111即31)
- n |= n>>>16 (n先右移四位變成0b00000即0，然后做或運(yùn)算得0b11111即31)
- 當(dāng)前n必然小于最大容量值，那么最后的結(jié)果就是32。
所以當(dāng)cap等于17時(shí)，得到的結(jié)果就是32。
為什么最后的結(jié)果必須是2的n次冪值，稍后在做解釋。初始化完成，接下來就是HashMap的幾大操作了put,get,remove。下面我們假設(shè)默認(rèn)初始容量為16
put操作
首先看下HashMap的核心方法:
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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;
if ((tab = table) == null || (n = tab.length) == 0) //step1
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //step2
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)))) //step3
e = p;
else if (p instanceof TreeNode) //step4
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//step5
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 //step6
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //step7
resize();
//step8
afterNodeInsertion(evict);
return null;
}
put操作主要調(diào)用內(nèi)部方法putVal方法，傳入了key的hash值，以及key和Value。
在講put的主要邏輯之前，在這里先解釋下為什么初始容量必須是2的n次冪值，我們看下step2
if ((p = tab[i = (n - 1) & hash]) == null) //step2
tab[i] = newNode(hash, key, value, null);
這里會(huì)先判斷(n-1)&hash值在數(shù)組里面是否存在，我們假設(shè)當(dāng)前初始容量是16，那么n-1就是15換成二進(jìn)制就是1111，這樣與后面的hash做與運(yùn)算就是等于hash值，所以只要hash值不一樣，那么就不會(huì)出現(xiàn)hash沖突的情況。那如果初始容量不是2的n次冪值呢，假設(shè)為15，那么n-1就是14換成二進(jìn)制就是1110，這樣后面的hash值只要前三位一樣，后面一位不管是0還是1，的出來的值就是一樣的，這樣會(huì)增大hash沖突的概率。所以設(shè)置成2的n次冪的值主要就是為了減少hash沖突。
接下來進(jìn)入正題，我們看下代碼的主要邏輯。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //step1
第一次put的時(shí)候table必然是空，那么執(zhí)行step1，做一次resize操作，具體操作后面再講，resize的主要作用就是擴(kuò)容或者初始化數(shù)組，這里會(huì)分配一個(gè)初始容量的數(shù)組。
然后進(jìn)入step2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //step2
n為初始數(shù)組大小16，這個(gè)時(shí)候n-1與上hash得出來的結(jié)果為10(假設(shè)插入的hash值是10，key為"青菜",value為"14元"，那么0b01111 & 0b01010 = 0b01010)，tab[10]必然是空，所以會(huì)new一個(gè)新的Node放入到tab[10]中。然后當(dāng)size大于閾值的時(shí)候會(huì)進(jìn)行一次擴(kuò)容操作即resize(注意這里的閾值并不是一開始設(shè)置的初始容量，閾值會(huì)在初次調(diào)用resize操作的時(shí)候乘上加載因子，得出最終的閾值。這個(gè)加載因子的作用我們稍后再講，這里記住是這樣的機(jī)制就行)。
- 接下來put一個(gè)新的值(假設(shè)hash值仍為10，key仍為"青菜",value為"15元")
此時(shí)我們會(huì)跳過step1和step2，進(jìn)入else分支step3
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
此時(shí)p獲取出來是有值的，并且key是等于傳入的key，hash值也相同,那么將p賦值給e，然后進(jìn)入step7
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
此時(shí)將新的value值替換掉舊的value值。
- put一個(gè)新的值(假設(shè)hash為10，key為"白菜"，value為“10元”)
此時(shí)我們會(huì)跳過step1,step2和step3,又因?yàn)槲覀儺?dāng)前的鏈表并沒有達(dá)到一定的長(zhǎng)度,所以p不為TreeNode，直接進(jìn)入step5
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;
}
此時(shí)根據(jù)hash值可以獲取到對(duì)應(yīng)的p值，但是p的key跟傳入的key不一致，所以開始在鏈表里面尋找與當(dāng)前key一致的node。
如果到最后發(fā)現(xiàn)仍然不存在，那么就新建一個(gè)node，插入到當(dāng)前鏈表的最后一個(gè)位置。這里有個(gè)treeifyBin方法，其實(shí)就是將鏈表轉(zhuǎn)化成紅黑樹的操作。TREEIFY_THRESHOLD為8，也就是說鏈表長(zhǎng)度大于8的時(shí)候會(huì)將鏈表轉(zhuǎn)化成紅黑樹，這個(gè)時(shí)候node會(huì)轉(zhuǎn)變成TreeNode(只有JDK8之后的HashMap才會(huì)有這個(gè)操作。紅黑樹的原理在我這篇文章中講過，這里不再贅述)。
這里重點(diǎn)提一下HashMap中TREEIFY_THRESHOLD為8，而UNTREEIFY_THRESHOLD為6，也就是說鏈表長(zhǎng)度大于8的時(shí)候才會(huì)轉(zhuǎn)化成紅黑樹，而元素個(gè)數(shù)小于6的時(shí)候才會(huì)變回鏈表。
為什么兩個(gè)值要不一致呢？其實(shí)鏈表與紅黑樹的轉(zhuǎn)化是比較耗費(fèi)性能的。如果存在著某個(gè)場(chǎng)景HashMap的某個(gè)下標(biāo)上面的節(jié)點(diǎn)數(shù)在8之間來回跳，那么就有可能導(dǎo)致鏈表和紅黑樹之間反復(fù)轉(zhuǎn)化，導(dǎo)致HashMap效率低下。為了避免這種情況，才會(huì)設(shè)計(jì)出兩個(gè)不一樣的值
如果發(fā)現(xiàn)存在對(duì)應(yīng)的節(jié)點(diǎn)，那么就替換掉原來的節(jié)點(diǎn)
-
put一個(gè)新的值(假設(shè)hash為8，key為"蘿卜"，value為“8元”)
此時(shí)step2獲取到的p值為null，所以會(huì)new一個(gè)新的Node出來
插入蘿卜.jpg - 接下來我們依次插入10個(gè)hash值不同的值，這樣整個(gè)數(shù)組長(zhǎng)度就等于12
此時(shí)在step7的時(shí)候滿足條件會(huì)做一次resize操作，那我們看下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() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//step1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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 //step2
newCap = oldThr;
else { // zero initial threshold signifies using defaults //step3
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { //step4
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) { //step5
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;
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;
}
先看注釋，初始化或者擴(kuò)容到之前兩倍的size。這里我們還是分步來解釋:
還記得第一次put操作么，它會(huì)先進(jìn)入resize方法，
- 這個(gè)時(shí)候table是空的(因?yàn)榈谝淮蝡ut的時(shí)候table并沒有賦值)，所以oldCap為0，因?yàn)閷?dāng)前閾值賦值給了oldThr，所以此時(shí)oldThr是有值的，就是一開始的初始容量 16，所以會(huì)進(jìn)入step2
- 將oldThr賦值給newCap，此時(shí)newThr沒有賦值，所以會(huì)進(jìn)入step4
- newCap乘以loadFactor也就是16??0.75 = 12，將12賦值給了閾值(所以使用的時(shí)候閾值肯定是最大容量*加載因子)。
- 因?yàn)閛ldTab是空的，所以step5就直接跳過了。
以上就是第一次的put操作，那么我們?cè)賮砜聪聞偛艛?shù)組size到達(dá)閾值以后的擴(kuò)容操作
- 因?yàn)檫@個(gè)時(shí)候是要擴(kuò)容了，所以table必然不為空，所以oldCap必然是大于0的(為16),所以進(jìn)入step1
- oldCap并沒有超過最大閾值，然后
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
滿足這個(gè)條件，所以此時(shí)oldThr左移一位，賦值給newThr相當(dāng)于是??2。此時(shí)newThr不為0，所以跳過了step4
- 進(jìn)行擴(kuò)容操作，即新建一個(gè)原來兩倍大小的數(shù)組，然后進(jìn)入step5
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- step5代碼有點(diǎn)長(zhǎng)，直接用通俗一點(diǎn)的話來說就是將原數(shù)組上面的node給賦值到新的已經(jīng)擴(kuò)容好的數(shù)組上面去，那么看下具體的實(shí)現(xiàn)邏輯吧：
//這個(gè)判斷主要是為了過濾首次進(jìn)行resize操作的情況，初始化的時(shí)候不需要進(jìn)行擴(kuò)容操作，所以也就不存在將舊數(shù)組的值移到新數(shù)組上面去
if (oldTab != null) {
//這里做循環(huán)主要就是將數(shù)組的值復(fù)制到新數(shù)組上面
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//原數(shù)組當(dāng)前下標(biāo)必須是有值才會(huì)進(jìn)入此if條件中，否則沒有復(fù)制的必要
oldTab[j] = null;
//當(dāng)e.next是空的時(shí)候證明當(dāng)前鏈表只有一個(gè)節(jié)點(diǎn)，那么直接通過hash & (newCap - 1)來計(jì)算出新的下標(biāo)，將e放入數(shù)組對(duì)應(yīng)下標(biāo)中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//這個(gè)只有在當(dāng)前節(jié)點(diǎn)已經(jīng)是紅黑樹的節(jié)點(diǎn)的時(shí)候才會(huì)進(jìn)行的處理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//進(jìn)入這個(gè)else循環(huán)，證明當(dāng)前鏈表節(jié)點(diǎn)不止一個(gè)
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//所以這里做的do-while循環(huán)目的就是將當(dāng)前下標(biāo)的鏈表里面的所有節(jié)點(diǎn)生成兩條不同的鏈表。
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;
}
}
}
}
}
前面部分可以直接看代碼注釋，這里著重解釋下do-while以及之后的操作，為什么要將一個(gè)下標(biāo)下面的鏈表分成兩個(gè)不同的鏈表呢。
首先數(shù)組下標(biāo)是通過hash&(cap-1)生成的，一旦擴(kuò)容以后，cap的值就會(huì)變成原來的兩倍。這樣hash&(cap-1)的下標(biāo)要么就跟老的數(shù)組的下標(biāo)一致，要么就是拿老的數(shù)組下標(biāo)再加上老的數(shù)組的長(zhǎng)度來作為新數(shù)組的下標(biāo)。
為何呢？我們舉個(gè)栗子：假設(shè)舊的cap是16即0b10000,則oldcap-1為0b01111:那么擴(kuò)容以后就是32即0b100000，則newcap-1為0b011111。我們拿hash&(cap-1)其實(shí)就是(hash&01111)和(hash&011111)。我們可以看到后四位運(yùn)算得出來的結(jié)果肯定是一樣的，唯一的不同就是第5位，假設(shè)hash值是10101，那么舊下標(biāo)就是0101(5)，新下標(biāo)就是10101(21)，結(jié)果就是5+16 = 21也就是剛才說的【老的數(shù)組下標(biāo)再加上老的數(shù)組的長(zhǎng)度】。假設(shè)hash值是00101，那么舊下標(biāo)就是0101，新下標(biāo)也是0101，所以新下標(biāo)跟舊下標(biāo)保持一致。
這個(gè)其實(shí)也是為什么初始容量會(huì)是2的n次冪值的原因之一，便于擴(kuò)容的時(shí)候計(jì)算。
上面這段解釋看明白了以后，這里面的操作其實(shí)就不難理解了。這里會(huì)將鏈表分拆成lo和hi。
loHead：下標(biāo)不變的鏈表頭
loTail：下標(biāo)不變的鏈表尾
hiHead：(下標(biāo)+原數(shù)組長(zhǎng)度)的鏈表頭
hiTail：(下標(biāo)+原數(shù)組長(zhǎng)度)的鏈表尾
而(e.hash & oldCap) == 0就是為了判斷高位一位。如果是0，那么代表下標(biāo)不變，加入到lo中；如果是1，那么代表下標(biāo)變成了[下標(biāo)+原數(shù)組長(zhǎng)度]，那么就加入到hi中。里面的操作、就是鏈表插入的基本操作這里就不加以展開了。
下面給出對(duì)應(yīng)的流程圖：
get操作
相對(duì)于put操作來說，get操作的邏輯就簡(jiǎn)單了很多，我們直接看代碼
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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) { //step1
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) //step2
return first;
if ((e = first.next) != null) { //step3
if (first instanceof TreeNode) //step4
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { //step5
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- step1判斷當(dāng)前table是否初始化過，長(zhǎng)度是否大于0，并且(n-1)&hash獲取的第一個(gè)Node元素不為0，才會(huì)進(jìn)入step2
- step2 判斷獲取的第一個(gè)Node元素與傳入的key對(duì)應(yīng)的hash值是否相等，key值相等(這里有個(gè)或運(yùn)算:前者判斷基本數(shù)據(jù)類型所對(duì)應(yīng)的key是否相等;后者判斷對(duì)象類型是否為同一個(gè))，一旦滿足就直接返回對(duì)應(yīng)的node
- step3判斷第一個(gè)節(jié)點(diǎn)是否有next節(jié)點(diǎn)，如果存在進(jìn)入step4，否則直接返回null
- step4判斷如果是紅黑樹的話，通過紅黑樹的方式找到對(duì)應(yīng)的node，如果不是則進(jìn)入step5
- step5做一個(gè)do-while循環(huán)，判斷邏輯與step2一致，目的是為了找出當(dāng)前鏈表中key相同的那個(gè)node返回出去，否則返回null。
以上就是get的所有邏輯。相對(duì)比較簡(jiǎn)單，沒有什么需要特殊說明的。
remove操作
remove會(huì)比get稍微復(fù)雜點(diǎn)
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { //step1
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //step2
node = p;
else if ((e = p.next) != null) { //step3
if (p instanceof TreeNode) //step4
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do { //step5
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) { //step6
if (node instanceof TreeNode) //step7
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //step8
tab[index] = node.next;
else //step9
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
- 其實(shí)remove的step1,step2,step3,step4,step5跟get方法里面的五步操作一樣，目的都是為了找到指定的元素，不同的是get是獲取到以后直接return掉，而remove是找到以后需要?jiǎng)h除以及接下來一系列的操作
- step6如果能獲取到node，那么肯定就進(jìn)入條件了(因?yàn)槲覀兺饨缯{(diào)用的remove方法傳入的matchValue默認(rèn)是false)。
- step7判斷是否為紅黑樹，如果是的話在紅黑樹中找出對(duì)應(yīng)node，刪除以后如果不滿足紅黑樹了需要做旋轉(zhuǎn)和變色來自平衡。如果不是則進(jìn)入step8
- step8 如果node==p條件成立，那么就是step2獲取的值，而step2獲取的就是對(duì)應(yīng)下標(biāo)下的頭節(jié)點(diǎn)。所以直接將頭結(jié)點(diǎn)的next作為當(dāng)前下標(biāo)的頭結(jié)點(diǎn)
- step9 這里p節(jié)點(diǎn)其實(shí)就是node之前的一個(gè)節(jié)點(diǎn)，(我們可以看下step5的邏輯：如果當(dāng)前節(jié)點(diǎn)e滿足傳入的key值和hash值的話，那就把e賦值給node，而e就是p.next得到的)。所以只要把node的next節(jié)點(diǎn)與node節(jié)點(diǎn)切斷，與p.next連接即可。然后size自減。
在put和remove方法里面調(diào)用了下面三個(gè)空方法:
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
這三個(gè)方法主要是LinkedHashMap實(shí)現(xiàn)的，這里就不展開細(xì)講了，后續(xù)有機(jī)會(huì)分析LinkedHashMap的時(shí)候再講。
