看了這篇，HashMap底層原理終于搞懂了！
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
HashMap結(jié)構(gòu)圖
代碼分析
常見(jiàn)的參數(shù)及意義
//默認(rèn)的Hash表的長(zhǎng)度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//Hash表的最大長(zhǎng)度
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當(dāng)鏈表的長(zhǎng)度為8的時(shí)候轉(zhuǎn)化為紅黑樹(shù)
static final int TREEIFY_THRESHOLD = 8;
//桶中元素個(gè)數(shù)小于6的時(shí)候紅黑樹(shù)轉(zhuǎn)換為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//只有當(dāng)數(shù)組的長(zhǎng)度大于等于64并且鏈表個(gè)數(shù)大于8才會(huì)轉(zhuǎn)換為紅黑樹(shù)
static final int MIN_TREEIFY_CAPACITY = 64;
//Hash表
transient Node<K,V>[] table;
//遍歷的時(shí)候使用返回一個(gè)K-V集合
transient Set<Map.Entry<K,V>> entrySet;
//表中K-V的個(gè)數(shù)
transient int size;
//對(duì)集合的修改次數(shù)，主要是后面出現(xiàn)的集合校驗(yàn)
transient int modCount;
//閾值當(dāng)size大于threshold時(shí)就會(huì)進(jìn)行resize
int threshold;
//加載因子
final float loadFactor;
源碼解釋
構(gòu)造方法
//傳入初始化容量，和指定的加載因子
public HashMap(int initialCapacity, float loadFactor) {
//參數(shù)校驗(yàn)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果傳入的值大于最大容量，就將最大的值賦給他
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//參數(shù)校驗(yàn)
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//返回的是2的整數(shù)次冪
this.threshold = tableSizeFor(initialCapacity);
}
//指定HashMap的容量
public HashMap(int initialCapacity) {
//調(diào)用如上的雙參構(gòu)造函數(shù)
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//無(wú)參構(gòu)造函數(shù)
public HashMap() {
//初始化加載因子為默認(rèn)的加載因子
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//構(gòu)造一個(gè)映射關(guān)系與指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
//初始化加載因子為默認(rèn)的加載因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
//構(gòu)造的過(guò)程函數(shù)
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//獲取m集合中元素個(gè)數(shù)
int s = m.size();
//如果m集合元素個(gè)數(shù)是0個(gè)那么下面這些操作也就沒(méi)有必要了
if (s > 0) {
if (table == null) { //表示的拷貝構(gòu)造函數(shù)調(diào)用putMapEntries函數(shù)，或者是構(gòu)造了HashMap但是還沒(méi)有存放元素
//計(jì)算的值存在小數(shù)所以+1.0F向上取整
float ft = ((float)s / loadFactor) + 1.0F;
//將ft強(qiáng)制轉(zhuǎn)換為整形
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果計(jì)算出來(lái)的值大于當(dāng)前HashMap的閾值更新新的閾值為2次方
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)//如果Map集合元素大于當(dāng)前集合HashMap的閾值則進(jìn)行擴(kuò)容
resize();
//將Map集合中元素存放到當(dāng)前集合中
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);
}
}
}
size函數(shù)
//返回key-val的數(shù)量
public int size() {
return size;
}
isEmpty函數(shù)
//當(dāng)前的集合是否為null
public boolean isEmpty() {
return size == 0;
}
get具體過(guò)程函數(shù)
//根據(jù)key獲取對(duì)應(yīng)的val
public V get(Object key) {
Node<K,V> e;
//通過(guò)hash值，key找到目標(biāo)節(jié)點(diǎn)再返回對(duì)應(yīng)的val
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//獲取key對(duì)應(yīng)的節(jié)點(diǎn)
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果集合為空和對(duì)應(yīng)的下標(biāo)數(shù)組中的值為空直接返回null
//first = tab[(n - 1) & hash]數(shù)組的長(zhǎng)度是2n次方減1后對(duì)應(yīng)位全部變?yōu)?，這樣為與操作永遠(yuǎn)都會(huì)在數(shù)組下標(biāo)范圍內(nèi)不會(huì)越界
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // 如果第一個(gè)節(jié)點(diǎn)hash與對(duì)應(yīng)hash相等，并且key也相等則返回當(dāng)前節(jié)點(diǎn)
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為null
if ((e = first.next) != null) {
//判斷節(jié)點(diǎn)是否為樹(shù)形
if (first instanceof TreeNode)
//在樹(shù)形結(jié)構(gòu)中查找節(jié)點(diǎn)并返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//通過(guò)do...while結(jié)構(gòu)遍歷找對(duì)應(yīng)key的節(jié)點(diǎn)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//找到節(jié)點(diǎn)并返回
return e;
} while ((e = e.next) != null);
}
}
//未找到對(duì)應(yīng)的節(jié)點(diǎn)
return null;
}
containsKey函數(shù)
//查看是否包含指定key
public boolean containsKey(Object key) {
//通過(guò)getNode返回是否為null判斷是否存在key
return getNode(hash(key), key) != null;
}
put函數(shù)
//調(diào)用putVal向當(dāng)前集合中存放元素并返回對(duì)應(yīng)的val
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//存放對(duì)應(yīng)的key-val
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果當(dāng)前集合為null則將集合擴(kuò)容并且將新的存放結(jié)構(gòu)賦值給tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//找到key存放的鏈表，如果為空直接將當(dāng)前節(jié)點(diǎn)存放鏈表在第一個(gè)位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //當(dāng)前為鏈表不為null
Node<K,V> e; K k;
//表示當(dāng)前鏈表第一個(gè)位置key已經(jīng)存在，將當(dāng)前節(jié)點(diǎn)賦值給e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//查看當(dāng)前的節(jié)點(diǎn)是否屬于樹(shù)形結(jié)構(gòu)如果是則在TreeNode中查找并將賦值給e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//找到當(dāng)前存放位置節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)的next并將當(dāng)前要插入的節(jié)點(diǎn)插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 鏈表的長(zhǎng)度為8的時(shí)候轉(zhuǎn)化為紅黑樹(shù)減一是因?yàn)樵貜?開(kāi)始
treeifyBin(tab, hash);
//跳出死循環(huán)
break;
}
//表示的是當(dāng)前鏈表已經(jīng)存在當(dāng)前要插入的key，HashMap不存在重復(fù)的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//將節(jié)點(diǎn)后移
p = e;
}
}
if (e != null) { // 當(dāng)前節(jié)點(diǎn)不為null將e.val存放在oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//不管oldValue是否為null都會(huì)發(fā)生value賦值給e.value
//當(dāng)出現(xiàn)重復(fù)的key之后上面會(huì)將節(jié)點(diǎn)保存給e并未修改新的val值，在此更新
e.value = value;
//將結(jié)點(diǎn)向后調(diào)整到最后面
afterNodeAccess(e);
//如果為null返回null，不為null返回對(duì)應(yīng)的val
return oldValue;
}
}
//++modCount對(duì)其集合操作的次數(shù)+1
++modCount;
if (++size > threshold)//如果在放入元素以后大于閾值則進(jìn)行2倍擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
resize函數(shù)
//將集合擴(kuò)容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//舊表的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//之前的閾值
int oldThr = threshold;
int newCap, newThr = 0;
//這里也可以說(shuō)集合不為空
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果集合現(xiàn)在數(shù)組的長(zhǎng)度大于等于最大容量
threshold = Integer.MAX_VALUE;//將整型最大的值賦值給threshold
return oldTab;
}
//當(dāng)前集合數(shù)組長(zhǎng)度擴(kuò)大二倍賦值給newCap小于MAXIMUM_CAPACITY
//并且集合的容量大于等于默認(rèn)容量將當(dāng)前閾值擴(kuò)大二倍賦值給新的閾值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//若沒(méi)有經(jīng)歷過(guò)初始化，通過(guò)構(gòu)造函數(shù)指定了initialCapcity，將當(dāng)前容量設(shè)置為大于它最小的2的n次方
else if (oldThr > 0)
newCap = oldThr;
else { // 初始的時(shí)候長(zhǎng)度和閾值都使用默認(rèn)值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//重新計(jì)算threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新當(dāng)前集合閾值
threshold = newThr;
//從這里開(kāi)始便是將oldTab數(shù)據(jù)重新hash放入擴(kuò)容后的newTab
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//將table指向的oldTab指向newTab
table = newTab;
if (oldTab != null) {
//遍歷哈希表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//當(dāng)前鏈表是否為null、并且將就鏈表賦值給e
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//將原來(lái)位置的鏈表置為null方便垃圾回收
if (e.next == null)//鏈表的長(zhǎng)度為1直接將鏈表中的一個(gè)節(jié)點(diǎn)重新hash存放到相應(yīng)的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //表示節(jié)點(diǎn)類型為樹(shù)形結(jié)構(gòu)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //鏈表是非樹(shù)形結(jié)構(gòu)，并且節(jié)點(diǎn)數(shù)量是大于1
//將鏈表拆分為兩個(gè)子鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { //通過(guò)do...while遍歷鏈表
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null) //設(shè)置頭節(jié)點(diǎn)
loHead = e;
else //設(shè)置尾結(jié)點(diǎn)
loTail.next = e;
loTail = e;//將尾結(jié)點(diǎn)變?yōu)樽詈笠粋€(gè)節(jié)點(diǎn)
}
else {
if (hiTail == null)//同上都是設(shè)置頭節(jié)點(diǎn)下面也一樣是設(shè)置尾結(jié)點(diǎn)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {//在新表的j位置存放鏈表
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//在新表的j+oldCap位置存放鏈表
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
remove函數(shù)
// 移除指向key返回對(duì)應(yīng)的val
public V remove(Object key) {
Node<K,V> e;
//返回如果為空返回null否則返回e.val
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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;
//常規(guī)的判斷表不為null，key有對(duì)應(yīng)的存儲(chǔ)位置
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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//表示的是key存儲(chǔ)在當(dāng)前鏈表的第一個(gè)位置
node = p;
else if ((e = p.next) != null) {//表示的是鏈表的長(zhǎng)度大于1
if (p instanceof TreeNode)//判斷是否是樹(shù)的實(shí)列
//返回對(duì)應(yīng)key在紅黑樹(shù)存儲(chǔ)的位置
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {//當(dāng)前結(jié)構(gòu)為鏈表
do {//遍歷鏈表
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {//找到對(duì)應(yīng)的節(jié)點(diǎn)保存并跳出循環(huán)
node = e;
break;
}
//將節(jié)點(diǎn)后移
p = e;
} while ((e = e.next) != null);
}
}
//表示要?jiǎng)h除的key存在并且找到
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)//如果是樹(shù)形在樹(shù)型結(jié)構(gòu)中移除當(dāng)前節(jié)點(diǎn)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//表示的鏈表中的第一個(gè)節(jié)點(diǎn)
tab[index] = node.next;
else
p.next = node.next;//移除節(jié)點(diǎn)
++modCount;//操作+1
--size;//長(zhǎng)度-1
afterNodeRemoval(node);
//返回節(jié)點(diǎn)
return node;
}
}
return null;
}
clear函數(shù)
//清除集合中的所有key-value
public void clear() {
Node<K,V>[] tab;
//集合操作+1
modCount++;
if ((tab = table) != null && size > 0) {//表不為null才進(jìn)行遍歷
size = 0;
for (int i = 0; i < tab.length; ++i)//遍歷集合所有元素都置為null，方便垃圾回收
tab[i] = null;
}
}
containsValue函數(shù)
//查看集合是否包含指定value
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {//表不為null
for (int i = 0; i < tab.length; ++i) {//遍歷數(shù)組
for (Node<K,V> e = tab[i]; e != null; e = e.next) {//遍歷鏈表
if ((v = e.value) == value ||
(value != null && value.equals(v)))
//存在指定的value直接返回true
return true;
}
}
}
//集合中不存在指定value返回false
return false;
}
keySet函數(shù)
//返回key的所有集合set
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
values函數(shù)
//返回所有的value集合
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
entrySet函數(shù)
// 返回所有的key-value集合
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
面試常見(jiàn)的問(wèn)題
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。
本文鏈接：
https://blog.csdn.net/weixin_44048140/article/details/116133070
鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布
??????
??長(zhǎng)按上方微信二維碼 2 秒
感謝點(diǎn)贊支持下哈 
評(píng)論
圖片
表情