文章目錄
-
-
-
-
- 一、面試常見問題
- 二、基本常量屬性
- 三、構造方法
- 四、節點結構
-
- 4.1 Node類
- 4.2.TreeNode
- 五、put方法
-
- 5.1 key的hash方法
- 5.2 resize() 擴容方法
- 六、get方法
-
-
-
一、面試常見問題
Q1: HashMap底層資料結構是什麼？
jdk1.7是數組+連結清單； jdk1.8 采用數組+ 連結清單+紅黑樹
Q2:為什麼要引入紅黑樹，有什麼優勢，解決什麼問題？
紅黑樹的引入是為了提高查詢效率，哈希沖突可以減少（元素key均勻散列程度和通過擴容）,不可避免，
如果沖突元素較多，會導緻連結清單過長，而連結清單查詢效率是O(n), 當連結清單長度超過8後，且數組長度(length)超過64才轉化為紅黑樹,
這點易忽略（後源碼證明）,不是連結清單長度一超高8個就将其樹化為紅黑樹，此時擴容解決沖突效果更好。（注：紅黑樹的特性需要了解掌握）
Q3: 在一條連結清單上新增節點，什麼方式插入？
1.8 是尾插法，1.7是采用頭插法，為什麼1.7需要頭插法？頭插法效率高？
詳見1.7源碼分析
Q4：放入HashMap中元素需要什麼特性？
需要重寫hashCode和 equals()方法 ，不重寫會有什麼問題？
Q5: HashMap是線程安全的嗎？你列舉其他線程安全的，特性？
不是, 因為它的方法沒有同步鎖，HashTable 是線程安全的，每個方法有加synhronized關鍵字，線程安全，但也會導緻效率變低；
一般多線程環境使用 ConcurrentHashMap，其原理是采用了分段鎖機制，每一段（Segment）中是一個HashMap，每個Segment中操作是加鎖的，
即保證線程操作某一個Segment是排他的，但不同線程在不同Segment是可以同時操作的，
即保證了線程安全，又提高了并發效率。
（此處不詳細展開ConcurrentHashMap，面試問題是環環相套的，好的面試官會步步引導，目的是為了全面考察面試者的技術水準）。
Q6: 1.7中 HashMap存在什麼問題？
在多線程環境下，1.7中Map可能會導緻cpu使用率過高，是因為存在環形連結清單了，HashMap中 連結清單是單連結清單結構，怎麼會有環？
是連結清單中元素指向下一個元素的指針next,指向了前面的元素，導緻了環，是以在周遊連結清單時，程式一直死循環無法結束。在多個線程放置元素時，resize()方法中導緻(後源碼證明)。
Q7: 1.8是先插入新值再判斷是否擴容，還是先擴容在插入新值？
1.8是先插入元素，在判斷容量是否超過門檻值，擴容，1.7是先擴容再插入新值
Q8: HashMap是延遲初始化？
是的，建立的Map對象，如果有指定容量大小，會記錄下來;沒有指定會使用預設16，在第一次put元素時才初始化數組，1.7，1.8都是如此，可以節省記憶體空間。
Q9: HashMap允許放置空鍵(null)，空值(null)嗎？
允許放置，null 鍵是放置在數組第一個位置的，是以在判斷某個key是否存在時，不能通過該get() 方法擷取value為null判斷，
這時鍵值對可能是 null:null,此時是存在Node對象的，可以通過containsKey(key)判斷 ，key為null，Node對象不為null,如下圖1所示
對比HashTable ,HashTable 不允許 null鍵，null值.
Q10 ：簡要講述一下HashMap放置元素過程，即put()方法。
put方法流程如下圖2所示
二、基本常量屬性
//預設初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
*最大容量，如果在構造函數中指定大于該值，會使用該值作為容量大小，2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 預設加載因子75%，好比地鐵滿載率，受疫情影響地鐵滿載率不超過30%
* 1,加載因子設定較大，随着數組中元素裝的越多，發生的沖突的機率越大，即對應的連結清單
* 越長，影響查找效率。
* 2，加載因子設定較小，元素很容易達到設定的門檻值，發生擴容操作，數組空間還有很大部分
* 沒有利用上，造成空間浪費。
* 是以在時間與空間上的權衡考慮
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 樹化門檻值：在連結清單元素超過8個了，将連結清單轉化為紅黑數結果，提高查找效率
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 取消樹化門檻值：在紅黑樹中節點數量小于6個，将其轉化為連結清單結構
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小樹化容量,容易忽視
* 連結清單樹化紅黑樹條件：
* 1，連結清單中元素數量超過(>)8個;
* 2, 滿足map中元素個數(size)大于等于64否則會先擴容，擴容對解決hash沖突更有效。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
三、構造方法
//傳有初始容量和加載因子
1.HashMap(int initialCapacity, float loadFactor)
//有初始容量，加載因子預設
2.HashMap(int initialCapacity)
//初始容量, 加載因子預設
3.HashMap()
//傳遞的一個Map子集
4.HashMap(Map<? extends K, ? extends V> m)
四、節點結構
- 1.數組和連結清單節點對象為HashMap内部類 Node.
- 2.紅黑樹節點 TreeNode，繼承LinkedHashMap.Entry , 而 Entry繼承Node,是以 TreeNode 實際是 Node孫子.
- 3.Node類,重寫了hashCode和 equals方法，記錄了目前key, value, key的hash值，以及指向後一個元素指針.
4.1 Node類
//實作Map集合的Entry類
static class Node<K,V> implements Map.Entry<K,V> {
//記錄目前節點key的hash
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//重寫了hashcode
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//重寫了equals
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;
}
}
4.2.TreeNode
什麼是紅黑樹？特點？
性質1. 節點是紅色或黑色.
性質2. 根節點是黑色.
性質3.所有葉子都是黑色.（葉子是NUIL節點）
性質4. 每個紅色節點的兩個子節點都是黑色.（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點.
// 繼承LinkedHashMap.Entry 繼承>> HashMap.Node
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;
五、put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
5.1 key的hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash(key)方法：
1.hashMap支援 key 為null,放在數組索引為0的位置
2.為了保證key的hash值分布均分、散列，減少沖突
等于 key的hash值 異或于 其hash值的低 16位
例："水果"的 hashCode()
h = 11011000000111101000
h>>>16=00000000000000001101
兩者異或，不同為1，相同為0
1101 10000001 11101000
^
0000 00000000 00001101
----------------------
1101 10000001 11100101
put核心方法
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)
//1，數組為空，初始化操作，此處resize() 待解析1
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
/**2,通過key的計算出的hash值與數組長度-1與運算，算出在數組下标位置
* 若該位置為空則建立新節點封裝元素值，放在該位置
*/
tab[i] = newNode(hash, key, value, null);
else {
// 若數組下标位置已經有值
Node<K,V> e; K k;
//3,首先判斷數組位置兩個key是否相同，e用來指向存在相同key的節點。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//4，key不相同的情況下，判斷數組該下标位置連接配接的是連結清單還是樹節點
//若是樹結構，就将該值放入樹中(放入樹中操作，也會周遊樹判斷是否存在相同的key的節點，若無相同會以新節點插入樹中)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//數組該下标位置隻有1個節點或者連結清單：這裡統一為連結清單形式
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//5，沒有找到相同key的元素，在連結清單後插入新節點
p.next = newNode(hash, key, value, null);
/**此處為什麼要>=7,因為bincount從0開始遞增，當bincount=7時，
*此時for循環執行了7次，加上新增加的節點，以及數組下标位置節點
*共7+1+1= 9了，即該數組下标位置連結清單長度大于8了,需要轉化為紅黑樹
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//周遊連結清單比較判斷是否存在兩個key相同元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//有上面 e= p.next,這裡 p有重新被指派為e，即繼續周遊連結清單下一個元素
p = e;
}
}
// 存在相同的key的元素，可能在數組、連結清單、樹上
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//6，覆寫舊值，傳回舊值，也可設定僅僅當舊value存在，不為null情況才覆寫原值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//修改次數+1
++modCount;
//7,判斷整個map中元素個數是否大于門檻值，大于則擴容，由此可見是先插入元素再判斷容量大小是否擴容，差別1.7先擴容再插入新值
if (++size > threshold)
resize();
//該方法為空，不用理會
afterNodeInsertion(evict);
return null;
}
5.2 resize() 擴容方法
該方法有個比較有意思的是将舊數組的元素移到擴大為原來容量2倍的新數組中時，原來數組中連結清單需要進行拆鍊，非常巧妙，下見。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//1,原來數組容量>0情況
if (oldCap > 0) {
//如果數組容量已經為最大值了 2^30,那就僅僅是将擴容門檻值修改
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//1.1 如果原來數組容量>=16,且其2倍小于最大容量(oldCap<<1 等價于 oldCap*2^1）
// 門檻值也擴容為原來2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//1.2 什麼情況數組容量=0，門檻值>0呢？
//建立HashMap，指定了數組初始容量cap，會将其轉換為大于等于cap的最小的2的幂次方的數指派給threshold,這裡即将數組容量指派
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//1.3原來數組容量和門檻值都為0，即常用的無參構造方式，使用預設容量大小
//門檻值根據容量和負載因子算出
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//2,newThr = 0情況出現在1.1中，沒滿足條件擴大為原來2倍
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
//小于最大容量，則用容量和加載因子乘積，否則為 Integer最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//3,建立新數組對象
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//4,原數組對象不為空，需要将原數組元素移到新數組中
if (oldTab != null) {
//周遊舊數組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//數組下标位置有元素
if ((e = oldTab[j]) != null) {
//直接把該下标位置連結清單(或紅黑樹)取出來，1個元素也當做連結清單看待，原數組該位置置空，隻要我們拿着連結清單頭節點/樹根節點(e)就行
oldTab[j] = null;
if (e.next == null)
//該位置隻有1個元素，直接與新數組長度hash，确定位置放入新數組
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//該位置是一顆紅黑樹，遷移到新數組
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//5，重點解析：這裡将原數組連結清單拆分為2條連結清單放入新數組，那它是怎麼拆的呢？
// loHead,loTail(lo 了解為low縮寫)分别記錄放在新數組下标小的那一條連結清單的頭節點和尾結點,
// 同理hiHead，hiTail(hi了解為 hight縮寫)放在新數組下标大的位置
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// e.hash & oldCap 是什麼目的呢？
// e.hash & (oldCap-1)求得是數組下标，e.hash & oldCap
// 是為了擷取比oldCap-1更高的那位一是0還是1，是0的就留在原位，是1的話需要增加oldCap。這裡不易了解，下面詳解
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;
}
擴容拆鍊過程分析：
#1,擴容前位置
23&15= 7
0001 0111
&
0000 1111
---------
0000 0111
#2,擴容後位置
23&31= 23
0001 0111
&
0001 1111
---------
0001 0111
/**因為每次擴容都是old數組長度的2倍，那麼在要計算在擴容後新數組位置，
那麼隻需要關心key的hash值左邊新增計算的那位是0還是1，如上未擴容前23與15與運算，隻需關心低4位值，高位無論其是否有1，與運算後都會為0; 而擴容後，15變為31，那麼key的hash值影響計算結果位由4位變為5位，
是以 e.hash & oldCap的結果就是擷取新增的位置，000X 0000,即X的值，0或者1；
0運算結果不變，放在原位，1與運算結果會增加一個原數組長度。
*/
如下圖所示：
7 & 7=7
0000 0111
0000 0111
----------
23 & 7=7
0001 0111
0000 0111
----------
31 & 7=7
0001 1111
0000 0111
----------
15 & 7=7
0000 1111
0000 0111
#可見第4位(從右向左)為1的有15，31，擴容後位置：原有下标+原數組長度
拆鍊位運算實作的巧妙：
1,擴容遷移原有數組中的元素，不用再重複計算原有元素key的hash值，提高效率.
2,擴容後拆鍊，會将連結清單長度縮短，減少hash沖突，提高查找效率.
六、get方法
根據鍵值對中的鍵（key）擷取值
public V get(Object key) {
Node<K,V> e;
//擷取節點指派給e,e！=null, 傳回該鍵值對的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
下見方法：getNode(int hash, Object key)
final Node<K,V> getNode(int hash, Object key) {
//傳入的hash值與put方法一樣的方法，相同規則計算key的hash值
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) {
//1，擷取數組下标位置的第一個節點，first
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null &&
key.equals(k))))
//2，檢查是否為相同的key,是直接傳回該節點對象；不是則周遊下一個節點
return first;
if ((e = first.next) != null) {
//3,下一個節點存在，需判斷是紅黑樹，還是連結清單
if (first instanceof TreeNode)
//3.1紅黑樹則周遊樹擷取是否存在與該key相同的節點
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//3.2 連結清單則依次周遊，查找相同的key，找到則傳回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//數組為空，或者沒有找到傳回空
return null;
}
參考：
一、1.7解析
二、1.8解析
歡迎關注我微信公衆号呀，不定期分享工作學習所得
微信号：flydashpig
道阻且長，且歌且行！ 每天一小步，踏踏實實走好腳下的路，文章為自己學習總結，不複制黏貼，就是想讓自己的知識沉澱一下，也希望與更多的人交流，如有錯誤，請批評指正！