不論是android面試還是java面試，都會(huì)問(wèn)到hashmap的原理和怎么實(shí)現(xiàn)的，今天我們就來(lái)總結(jié)下；
一、HashMap(數(shù)組+鏈表+紅黑樹)原理
HashMap底層使用數(shù)組，每個(gè)數(shù)組元素存的是Node類型（或者TreeNode），table的每一個(gè)位置，又可以稱為Hash桶，也就是說(shuō)，會(huì)將相同hash值的元素存放到一個(gè)Hash桶中（這里的hash值，是指對(duì)key計(jì)算的hash值），也就是在Table的下標(biāo)中相同，為了解決同一個(gè)位置有多個(gè)元素（沖突），HashMap用來(lái)拉鏈法和紅黑樹兩種數(shù)據(jù)結(jié)構(gòu)來(lái)解決沖突
1、數(shù)據(jù)結(jié)構(gòu)參數(shù)的含義
// 閾值（容量*加載因子）。當(dāng)HashMap中的鍵值對(duì)超過(guò)了該值，HashMap就會(huì)進(jìn)行擴(kuò)容
int threshold;
// 哈希表的加載因子，描述的是HashMap滿的程度。接近0表示很空，1表示填滿了
final float loadFactor;
// 默認(rèn)的初始容量-必須是2的冪，默認(rèn)值是16。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 能存的最大元素?cái)?shù)量。默認(rèn)值是1 << 30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)的加載因子0.75，當(dāng)map中的元素個(gè)數(shù)達(dá)到容量的75%時(shí)會(huì)觸發(fā)擴(kuò)容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶的樹化閾值：即鏈表轉(zhuǎn)成紅黑樹的閾值，在存儲(chǔ)數(shù)據(jù)時(shí)，當(dāng)鏈表長(zhǎng)度 > 該值時(shí)，則將鏈表轉(zhuǎn)換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 桶的鏈表還原閾值：即紅黑樹轉(zhuǎn)為鏈表的閾值，當(dāng)原有的紅黑樹內(nèi)數(shù)量 < 6 時(shí)，則將紅黑樹轉(zhuǎn)換成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹形化容量閾值：即當(dāng)哈希表中的容量 > 該值時(shí)，允許鏈表轉(zhuǎn)換成紅黑樹，否則直接擴(kuò)容
static final int MIN_TREEIFY_CAPACITY = 64;
2、構(gòu)造方法：
// 構(gòu)造一個(gè)空的HashMap，具有默認(rèn)的初始容量
public HashMap() {
// 負(fù)載系數(shù)，默認(rèn)值是0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 使用指定的初始值構(gòu)造一個(gè)空的HashMap
public HashMap(int initialCapacity) {
// 初始容量和負(fù)載系數(shù)
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 使用指定的初始值構(gòu)造一個(gè)空的HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量大于最大初始容量時(shí)，初始容量為最大初始容量
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);
}
// 返回大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù)
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;
}
3、Node節(jié)點(diǎn)和TreeNode節(jié)點(diǎn)
在HashMap中，存的value不是put的K-V，而是一個(gè)Node類型，還有一個(gè)TreeNode類型，可以和Node類型相關(guān)轉(zhuǎn)換
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
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;
}
}4、hash計(jì)算以及確定下標(biāo)
/**
* 計(jì)算key的hash值：
* 1.如果key為null，則hash值為0
* 2.如果key不為null，將key的hashCode值和高16位進(jìn)行異或計(jì)算（異或：相同為0，不同為1）
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
5、resize擴(kuò)容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// threshold表示觸發(fā)擴(kuò)容的閾值（size >= capacity * loadfactor時(shí)會(huì)擴(kuò)容）
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap大于0證明已經(jīng)對(duì)map進(jìn)行過(guò)操作，并非剛創(chuàng)建map的時(shí)候
if (oldCap > 0) {
// 如果當(dāng)前容量允許的大于最大容量，則將閾值設(shè)置為整數(shù)最大值，不會(huì)進(jìn)行復(fù)制操作
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果2倍舊容量未超過(guò)允許的最大容量，并且舊容量達(dá)到了默認(rèn)的初始容量16，則新的擴(kuò)容閾值設(shè)置2倍的舊容量
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 使用HashMap(capacity)或者HashMap(capacity, loadFactor)創(chuàng)建map
// 這是初次擴(kuò)容，新容量設(shè)置為threshold，也就是capacity*loadFactor
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 第一次擴(kuò)容，使用new HashMap()這種方式創(chuàng)建map，容量和負(fù)載因子都使用默認(rèn)
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 設(shè)置下一次進(jìn)行擴(kuò)容的閾值
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"})
// 申請(qǐng)一個(gè)新的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 下面是將舊數(shù)組中的元素復(fù)制到新申請(qǐng)的數(shù)組中
// 因?yàn)樵谂f數(shù)組中節(jié)點(diǎn)的索引計(jì)算方式：oldIndex=(oldCapacity - 1) & key.hash，
// 當(dāng)數(shù)組的容量發(fā)生變化后，需要重新確定節(jié)點(diǎn)的索引，新的節(jié)點(diǎn)位置有兩種可能：
// 1.newIndex=oldIndex，索引不變，前提是key.hash & oldCapacity結(jié)果為0
// 2.newIndex=oldIndex+oldCapacity，不是第一種情況，就是第二種情況
if (oldTab != null) {
// 遍歷舊數(shù)組（oldCap長(zhǎng)度）
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)
// 將紅黑樹的節(jié)點(diǎn)進(jìn)行拆分，將樹中的每個(gè)節(jié)點(diǎn)都存入新位置，同時(shí)判斷是否需要進(jìn)行樹轉(zhuǎn)鏈表
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 遍歷鏈表，將鏈表分為兩部分，一部分（loHead）是索引不變，一部分（hiHead）的新索引是 oldIndex+oldCapacity
// 然后將鏈表放入對(duì)應(yīng)的數(shù)組中
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;
}關(guān)于擴(kuò)容，在Java7的HashMap中，如果發(fā)生多線程更改HashMap（同時(shí)擴(kuò)容），則可能會(huì)引起鏈表產(chǎn)生環(huán)的問(wèn)題，這是因?yàn)镴ava7只是使用了數(shù)組加鏈表，插入鏈表的時(shí)候使用頭插法，并且在擴(kuò)容的時(shí)候鏈表節(jié)點(diǎn)的順序會(huì)發(fā)生改變；而Java8在插入節(jié)點(diǎn)時(shí)使用是尾插法，在擴(kuò)容的時(shí)候鏈表節(jié)點(diǎn)的順序不會(huì)發(fā)生改變，可以避免出現(xiàn)環(huán)的問(wèn)題。但這并不能說(shuō)明Java8的HashMap就可以支持并發(fā)修改，因?yàn)槠鋬?nèi)部很多操作都沒(méi)有保證原子性（比如兩個(gè)線程同時(shí)插入元素，size++，都未做原子性保證。?
6、resize時(shí)紅黑樹的split拆分
和鏈表一樣，紅黑樹中的元素也需要挨個(gè)確定新索引位置，同樣是分為2部分，一部分是索引不變，一部分的新索引為oldIndex+oldCapacity。
注意：split是HashMap中的內(nèi)部類TreeNode的方法，而不是HashMap的方法。
/**
* 擴(kuò)容時(shí)，對(duì)同一個(gè)hash桶中的元素（紅黑樹）進(jìn)行拆分，有可能拆分為兩部分
* part1.節(jié)點(diǎn)的hash和原數(shù)組的容量與之后為0 -> 移到新表后，索引和舊表保持不變
* part2.節(jié)點(diǎn)的hash和原數(shù)組的容量與之后不為0 -> 移到新表后，新索引為"oldIndex+oldCapacity"
* 這兩部分，在做完拆分后，判斷是否需要將樹轉(zhuǎn)換為鏈表，如果各自的數(shù)量未超過(guò)UNTREEIFY_THRESHOLD(默認(rèn)為6)，則需轉(zhuǎn)換為鏈表
*
* @param map hashMap實(shí)例本身
* @param tab 擴(kuò)容新申請(qǐng)的數(shù)組
* @param index 本次要拆分的下標(biāo)索引（對(duì)應(yīng)舊數(shù)組）
* @param bit 舊數(shù)組的容量
*/
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
// loHead鏈著索引不變的節(jié)點(diǎn)
TreeNode<K,V> loHead = null, loTail = null;
// hiHead鏈著索引改變的節(jié)點(diǎn)
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 如果當(dāng)前節(jié)點(diǎn)和原數(shù)組的容量與之后為0，則擴(kuò)容后的索引位置和與在舊表保持一致
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
} else {
// 如果當(dāng)前節(jié)點(diǎn)和原數(shù)組的容量與之后不為0，則擴(kuò)容后的索引位置為"oldIndex+oldCapacity"
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
// 高位節(jié)點(diǎn)不為空，說(shuō)明原鏈表元素被拆分了，切地位紅黑樹節(jié)點(diǎn)個(gè)數(shù)大于6，不滿足轉(zhuǎn)鏈表?xiàng)l件，需要重新樹化
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
// 低位節(jié)點(diǎn)不為空，說(shuō)明原鏈表元素被拆分了，切地位紅黑樹節(jié)點(diǎn)個(gè)數(shù)大于6，不滿足轉(zhuǎn)鏈表?xiàng)l件，需要重新樹化
if (loHead != null)
hiHead.treeify(tab);
}
}
}
7、鏈表轉(zhuǎn)紅黑樹
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果map的容量（數(shù)組的長(zhǎng)度）為0，或者小于MIN_TREEIFY_CAPACITY（默認(rèn)64），則進(jìn)行擴(kuò)容操作，而不進(jìn)行轉(zhuǎn)換紅黑樹
// 底層數(shù)組，也稱為hash桶，也就是說(shuō)hash桶的數(shù)量小于64時(shí)，則會(huì)進(jìn)行擴(kuò)容操作
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 將鏈表節(jié)點(diǎn)轉(zhuǎn)換為紅黑樹節(jié)點(diǎn)
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);
// 轉(zhuǎn)換紅黑樹的操作
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}8、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;
// 初始狀態(tài)，HashMap為空，則需要擴(kuò)容，n為擴(kuò)容后的容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 要放入的位置沒(méi)有其他項(xiàng)（沒(méi)有沖突），則直接放入該位置
tab[i] = newNode(hash, key, value, null);
else {
// 計(jì)算后，要放入的位置已經(jīng)有了其他項(xiàng)，需要解決沖突（拉鏈法或者紅黑樹）
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 上一步操作后，p指向的該"桶"的第一個(gè)Node，判斷位置是否匹配，如果位置匹配，且key相同，表示是put的數(shù)據(jù)已經(jīng)存在，直接覆蓋即可
e = p;
else if (p instanceof TreeNode)
// 如果p指向的是TreeNode，也就是紅黑樹存儲(chǔ)的節(jié)點(diǎn)，那么就將新增元素加入到紅黑樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// p指向的是鏈表頭結(jié)點(diǎn)，則利用尾插法，將新節(jié)點(diǎn)插入到末尾（遍歷過(guò)程中發(fā)現(xiàn)相同節(jié)點(diǎn)則進(jìn)行覆蓋）
for (int binCount = 0; ; ++binCount) {
// 走到尾節(jié)點(diǎn)
if ((e = p.next) == null) {
// 將新節(jié)點(diǎn)插到末尾
p.next = newNode(hash, key, value, null);
// 判斷鏈表的長(zhǎng)度是否達(dá)到樹化的閾值，如果是，則將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 注意并不一定會(huì)轉(zhuǎn)換為紅黑樹，還與tab的長(zhǎng)度有關(guān)，tab.length<MIN_TREEIFY_CAPACITY時(shí)，仍舊采取擴(kuò)容，而非樹化
treeifyBin(tab, hash);
break;
}
// 如果是已經(jīng)存在的節(jié)點(diǎn)，則中斷循環(huán)，后面將進(jìn)行覆蓋value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 數(shù)據(jù)已經(jīng)存在，則進(jìn)行覆蓋操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 計(jì)數(shù)加一（用來(lái)快速失?。?br> ++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}9、get操作
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* get的時(shí)候，最關(guān)鍵的就是，先根據(jù)key的hash值找到桶位置，然后在根據(jù)key來(lái)查找
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 根據(jù)key進(jìn)行hash后的位置存在數(shù)據(jù)，如果不存在，則直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 根據(jù)hash和key進(jìn)行判斷第一個(gè)節(jié)點(diǎn)是否為要找的元素，如果是，則返回第一個(gè)節(jié)點(diǎn)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 如果節(jié)點(diǎn)時(shí)紅黑樹的節(jié)點(diǎn)類型，則遍歷紅黑樹，進(jìn)行查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 遍歷鏈表進(jìn)行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}10、remove操作
remove有兩個(gè)接口，remove(key)、remove(key,value)，內(nèi)部都是調(diào)用一個(gè)removeNode方法，如下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 實(shí)現(xiàn)了Map接口中的remove方法
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != 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;
// map不為空，且hash對(duì)應(yīng)的位置不為空，才進(jìn)行查找，否則認(rèn)為未找到，返回null
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;
// 匹配hash地址的第一個(gè)節(jié)點(diǎn)是否匹配，hash和key都匹配，則證明找到了要?jiǎng)h除的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 遍歷紅黑樹
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為null，證明未找到key對(duì)應(yīng)的元素
// node不為null，則根據(jù)調(diào)用的remove(key)還是remove(key,value)來(lái)判斷
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 要?jiǎng)h除的節(jié)點(diǎn)匹配，如果是樹節(jié)點(diǎn)類型，則從樹中刪除節(jié)點(diǎn)
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 要?jiǎng)h除的節(jié)點(diǎn)時(shí)第一個(gè)節(jié)點(diǎn)時(shí)，直接將頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)往前提一個(gè)位置（舊頭節(jié)點(diǎn)被刪除）
tab[index] = node.next;
else
// 非頭結(jié)點(diǎn)，修改指針，將下一個(gè)節(jié)點(diǎn)賦給父節(jié)點(diǎn)的next
p.next = node.next;
// 修改次數(shù)加一，元素?cái)?shù)量減一
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}二、hashmap常見(jiàn)的面試題
1.講下對(duì)HashMap的認(rèn)識(shí)
- HashMap 存儲(chǔ)的是鍵值對(duì) key - value，key 具有唯一性，采用了鏈地址法來(lái)處理哈希沖突。當(dāng)往 HashMap 中添加元素時(shí)，會(huì)計(jì)算 key 的 hash 值取余得出元素在數(shù)組中的的存放位置。
- HashMap底層的數(shù)據(jù)結(jié)構(gòu)在 JDK1.8 中有了較大的變化，1.8之前采用數(shù)組加鏈表的數(shù)據(jù)結(jié)構(gòu)，1.8采用數(shù)組加鏈表加紅黑樹的數(shù)據(jù)結(jié)構(gòu)。
- HashMap 是線程不安全的，線程安全可以使用 HashTable 和 ConcurrentHashMap 。
- 在 1.8 版本的中 hash() 和 resize( ) 方法也有了很大的改變，提升了性能。
- 鍵和值都可存放null，鍵只能存放一個(gè)null，鍵為null時(shí)存放入table[0]。
2.HashMap的一些參數(shù)
//HashMap的默認(rèn)初始長(zhǎng)度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap的最大長(zhǎng)度2的30次冪
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap的默認(rèn)加載因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap鏈表升級(jí)成紅黑樹的臨界值
static final int TREEIFY_THRESHOLD = 8;
//HashMap紅黑樹退化成鏈表的臨界值
static final int UNTREEIFY_THRESHOLD = 6;
//HashMap鏈表升級(jí)成紅黑樹第二個(gè)條件：HashMap數(shù)組(桶)的長(zhǎng)度大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap底層Node桶的數(shù)組
transient Node<K,V>[] table;
//擴(kuò)容閾值，當(dāng)你的hashmap中的元素個(gè)數(shù)超過(guò)這個(gè)閾值，便會(huì)發(fā)生擴(kuò)容
//threshold = capacity * loadFactor
int threshold;
3.為什么HashMap的長(zhǎng)度必須是2的n次冪？
- 在計(jì)算存入結(jié)點(diǎn)下標(biāo)時(shí)，會(huì)利用 key 的 hsah 值進(jìn)行取余操作，而計(jì)算機(jī)計(jì)算時(shí)，并沒(méi)有取余等運(yùn)算，會(huì)將取余轉(zhuǎn)化為其他運(yùn)算
- 當(dāng)n為2次冪時(shí)，會(huì)滿足一個(gè)公式：(n - 1) & hash = hash % n，就可以用位運(yùn)算代替取余運(yùn)算，計(jì)算更加高效
4.HashMap 為什么在獲取 hash 值時(shí)要進(jìn)行位運(yùn)算
換種問(wèn)法：能不能直接使用key的hashcode值計(jì)算下標(biāo)存儲(chǔ)？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}如果使用直接使用hashCode對(duì)數(shù)組大小取余，那么相當(dāng)于參與運(yùn)算的只有hashCode的低位，高位是沒(méi)有起到任何作用的，所以我們的思路就是讓 hashCode取值出的高位也參與運(yùn)算，進(jìn)一步降低hash碰撞的概率，使得數(shù)據(jù)分布更平均，我們把這樣的操作稱為擾動(dòng)。
(h >>> 16)是無(wú)符號(hào)右移16位的運(yùn)算，右邊補(bǔ)0，得到 hashCode 的高16位。
(h = key.hashCode()) ^ (h >>> 16) 把 hashCode 和它的高16位進(jìn)行異或運(yùn)算，可以使得到的 hash 值更加散列，盡可能減少哈希沖突，提升性能。
而這么來(lái)看 hashCode 被散列 (異或) 的是低16位，而 HashMap 數(shù)組長(zhǎng)度一般不會(huì)超過(guò)2的16次冪，那么高16位在大多數(shù)情況是用不到的，所以只需要拿 key 的 HashCode 和它的低16位做異或即可利用高位的hash值，降低哈希碰撞概率也使數(shù)據(jù)分布更加均勻。
5.HashMap在JDK1.7和JDK1.8中有哪些不同？ HashMap的底層實(shí)現(xiàn)
在Java中，保存數(shù)據(jù)有兩種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表。數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；鏈表的特點(diǎn)是：尋址困難，但插入和刪除容易；所以我們將數(shù)組和鏈表結(jié)合在一起，發(fā)揮兩者各自的優(yōu)勢(shì)，使用一種叫做拉鏈法的方式可以解決哈希沖突。
JDK1.8主要解決或優(yōu)化了以下問(wèn)題：
resize 擴(kuò)容和 計(jì)算hash 優(yōu)化
引入了紅黑樹，目的是避免單條鏈表過(guò)長(zhǎng)而影響查詢效率，紅黑樹算法請(qǐng)參考;
解決了多線程死循環(huán)問(wèn)題，但仍是非線程安全的，多線程時(shí)可能會(huì)造成數(shù)據(jù)丟失問(wèn)題
6.HashMap的put方法的具體流程？
源碼，上面有代碼
HashMap是懶加載，只有在第一次put時(shí)才會(huì)創(chuàng)建數(shù)組。
- 判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull，否則執(zhí)行resize()進(jìn)行擴(kuò)容；
- 根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點(diǎn)添加，轉(zhuǎn)向⑥，如果table[i]不為空，轉(zhuǎn)向③；
- 判斷table[i]的首個(gè)元素是否和key一樣，如果相同直接覆蓋value，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals；
- 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對(duì)，否則轉(zhuǎn)向⑤；
- 遍歷table[i]，并記錄遍歷長(zhǎng)度，如果遍歷過(guò)程中發(fā)現(xiàn)key值相同的，則直接覆蓋value，沒(méi)有相同的key則在鏈表尾部插入結(jié)點(diǎn)，插入后判斷該鏈表長(zhǎng)度是否大等于8，大等于則考慮樹化，如果數(shù)組的元素個(gè)數(shù)小于64，則只是將數(shù)組resize，大等于才樹化該鏈表；
- 插入成功后，判斷數(shù)組中的鍵值對(duì)數(shù)量size是否超過(guò)了閾值threshold，如果超過(guò)，進(jìn)行擴(kuò)容。
7.HashMap 的 get 方法的具體流程？
源碼，上面有代碼
- 首先根據(jù) hash 方法獲取到 key 的 hash 值；
- 然后通過(guò) hash & (length - 1) 的方式獲取到 key 所對(duì)應(yīng)的Node數(shù)組下標(biāo) ( length對(duì)應(yīng)數(shù)組長(zhǎng)度 )；
- 首先判斷此結(jié)點(diǎn)是否為空，是否就是要找的值，是則返回空，否則判斷第二個(gè)結(jié)點(diǎn)是否為空，是則返回空，不是則判斷此時(shí)數(shù)據(jù)結(jié)構(gòu)是鏈表還是紅黑樹
- 鏈表結(jié)構(gòu)進(jìn)行順序遍歷查找操作，每次用 == 符號(hào) 和 equals( ) 方法來(lái)判斷 key 是否相同，滿足條件則直接返回該結(jié)點(diǎn)。鏈表遍歷完都沒(méi)有找到則返回空；
- 紅黑樹結(jié)構(gòu)執(zhí)行相應(yīng)的 getTreeNode( ) 查找操作；
8.HashMap的擴(kuò)容操作是怎么實(shí)現(xiàn)的？
不管是JDK1.7或者JDK1.8 當(dāng)put方法執(zhí)行的時(shí)候，如果table為空，則執(zhí)行resize()方法擴(kuò)容，默認(rèn)長(zhǎng)度為16；
JDK1.7擴(kuò)容
條件：發(fā)生擴(kuò)容的條件必須同時(shí)滿足兩點(diǎn)
- 當(dāng)前存儲(chǔ)的數(shù)量大于等于閾值；
- 發(fā)生hash碰撞；
特點(diǎn)：先擴(kuò)容，再添加（擴(kuò)容使用的頭插法），頭插法會(huì)使鏈表發(fā)生反轉(zhuǎn)，多線程環(huán)境下可能會(huì)死循環(huán)
JDK1.8擴(kuò)容
條件：
- 當(dāng)前存儲(chǔ)的數(shù)量大于等于閾值
- 當(dāng)某個(gè)鏈表長(zhǎng)度>=8，但是數(shù)組存儲(chǔ)的結(jié)點(diǎn)數(shù)size() < 64時(shí)
- 特點(diǎn)：先插后判斷是否需要擴(kuò)容（擴(kuò)容時(shí)是尾插法）
- 缺點(diǎn)：多線程下，1.8會(huì)有數(shù)據(jù)覆蓋
9.鏈表升級(jí)成紅黑樹的條件
鏈表長(zhǎng)度大于8時(shí)才會(huì)考慮升級(jí)成紅黑樹，是有一個(gè)條件是 HashMap 的 Node 數(shù)組長(zhǎng)度大于等于64（不滿足則會(huì)進(jìn)行一次擴(kuò)容替代升級(jí)）；
10.紅黑樹退化成鏈表的條件
- 擴(kuò)容 resize( ) 時(shí)，紅黑樹拆分成的 樹的結(jié)點(diǎn)數(shù)小于等于臨界值6個(gè)，則退化成鏈表；
- 刪除元素 remove( ) 時(shí)，在 removeTreeNode( ) 方法會(huì)檢查紅黑樹是否滿足退化條件，與結(jié)點(diǎn)數(shù)無(wú)關(guān)。如果紅黑樹根 root 為空，或者 root 的左子樹/右子樹為空，root.left.left 根的左子樹的左子樹為空，都會(huì)發(fā)生紅黑樹退化成鏈表；
11.HashMap是怎么解決哈希沖突的？
- 使用鏈地址法（使用散列表）來(lái)鏈接擁有相同下標(biāo)的數(shù)據(jù)；
- 使用2次擾動(dòng)函數(shù)（hash函數(shù)）來(lái)降低哈希沖突的概率，使得數(shù)據(jù)分布更平均；
- 引入紅黑樹進(jìn)一步降低遍歷的時(shí)間復(fù)雜度，使得遍歷更快；
