溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關(guān)Java中HashMap的案例分析的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。
HashMap 是數(shù)組和鏈表組合組成的復(fù)雜結(jié)構(gòu)，哈希值決定了鍵值在數(shù)組的位置，當(dāng)哈希值相同時則以鏈表形式存儲，當(dāng)鏈表長度到達(dá)設(shè)定的閾值則會對其進(jìn)行樹化，這樣做是為了保證數(shù)據(jù)安全和數(shù)據(jù)相關(guān)操作的效率
HashMap 性能表現(xiàn)取決于哈希碼的有效性，所以 hashCode 和 equals 的基本約定規(guī)則尤為重要，如：equals 相等，hashCode 一定要相等；重寫了 hashCode 也要重寫 equals；hashCode 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致；equals 的對稱、反射、傳遞等特性
HashMap 與 Hashtable、TreeMap 的區(qū)別
HashMap：基于數(shù)組的非同步哈希表，支持 null 鍵或值，是鍵值對存取數(shù)據(jù)場景的首選
Hashtable：基于數(shù)組的同步哈希表，不支持null鍵或值，因為同步導(dǎo)致性能影響，很少被使用
TreeMap：基于紅黑樹提供順序訪問的 Map，比 HashMap 節(jié)省空間，但它的數(shù)據(jù)操作（查、增、刪）時間復(fù)雜度均為：O（log(n)），這點與 HashMap 不同。支持空值，當(dāng)鍵為空時且未實現(xiàn) Comparator 接口，會出現(xiàn) NullPointerException ，實現(xiàn)了 Comparator 接口并對 null 對象進(jìn)行判斷可實現(xiàn)正常存入
HashMap、Hashtable、TreeMap 均以鍵值對形式存儲或操作數(shù)據(jù)元素。HashMap、TreeMap 繼承自 AbstractMap 類，Hashtable 繼承自 Dictionary 類，三者均實現(xiàn) Map 接口
HashMap 源碼解析
HashMap()
public HashMap(int initialCapacity, float loadFactor){
// ...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}初始化 HashMap 時僅設(shè)置了一些初始值，但在開始處理數(shù)據(jù)時，如 .put() 方法內(nèi)漸漸開始復(fù)雜起來
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) {
// 定義新tab數(shù)組及node對象
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果原table是空的或者未存儲任何元素則需要先初始化進(jìn)行tab的初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 當(dāng)數(shù)組中對應(yīng)位置為null時，將新元素放入數(shù)組中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 若對應(yīng)位置不為空時處理哈希沖突
else {
Node<K,V> e; K k;
// 1 - 普通元素判斷： 更新數(shù)組中對應(yīng)位置數(shù)據(jù)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2 - 紅黑樹判斷：當(dāng)p為樹的節(jié)點時，向樹內(nèi)插入節(jié)點
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3 - 鏈表判斷：插入節(jié)點
else {
for (int binCount = 0; ; ++binCount) {
// 找到尾結(jié)點并插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判斷鏈表長度是否達(dá)到樹化閾值，達(dá)到就對鏈表進(jìn)行樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 更新鏈表中對應(yīng)位置數(shù)據(jù)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果存在這個映射就覆蓋
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判斷是否允許覆蓋，并且value是否為空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回調(diào)以允許LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更新修改次數(shù)
++modCount;
// 檢查數(shù)組是否需要進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
// 回調(diào)以允許LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
}當(dāng) table 為 null，會通過 resize() 初始化，且 resize() 有兩個作用，一是創(chuàng)建并初始化 table ，二是在 table 容量不滿足需求時進(jìn)行擴(kuò)容：
if (++size > threshold)
resize();具體的鍵值對存儲位置計算方法為：
if ((p = tab[i = (n - 1) & hash]) == null)
// 向數(shù)組賦值新元素
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果新插入的結(jié)點和table中p結(jié)點的hash值，key值相同的話
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是紅黑樹結(jié)點的話，進(jìn)行紅黑樹插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 代表這個單鏈表只有一個頭部結(jié)點，則直接新建一個結(jié)點即可
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表長度大于8時，將鏈表轉(zhuǎn)紅黑樹
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
p = e;
}
}
// 如果存在這個映射就覆蓋
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判斷是否允許覆蓋，并且value是否為空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 回調(diào)以允許LinkedHashMap后置操作
return oldValue;
}
}留意 .put() 方法中的 hash 計算，它并不是 key 的 hashCode ，而是將 key 的 hashCode 高位數(shù)據(jù)移位到低位進(jìn)行異或運算，這樣一些計算出來的哈希值主要差異在高位時的數(shù)據(jù)，就不會因 HashMap 里哈希尋址時被忽略容量以上的高位，那么即可有效避免此類情況下的哈希碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap.resize()
final Node<K,V>[] resize() {
// 把當(dāng)前底層數(shù)組賦值給oldTab，為數(shù)據(jù)遷移工作做準(zhǔn)備
Node<K,V>[] oldTab = table;
// 獲取當(dāng)前數(shù)組的大小，等于或小于0表示需要初始化數(shù)組，大于0表示需要擴(kuò)容數(shù)組
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 獲取擴(kuò)容的閾值（容量*負(fù)載系數(shù)）
int oldThr = threshold;
// 定義并初始化新數(shù)組長度和目標(biāo)閾值
int newCap, newThr = 0;
// 判斷是初始化數(shù)組還是擴(kuò)容，等于或小于0表示需要初始化數(shù)組，大于0表示需要擴(kuò)容數(shù)組。若 if(oldCap > 0)=true 表示需擴(kuò)容而非初始化
if (oldCap > 0) {
// 判斷數(shù)組長度是否已經(jīng)是最大，MAXIMUM_CAPACITY =（2^30）
if (oldCap >= MAXIMUM_CAPACITY) {
// 閾值設(shè)置為最大
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 目標(biāo)閾值擴(kuò)展2倍，數(shù)組長度擴(kuò)展2倍
newThr = oldThr << 1; // double threshold
}
// 表示需要初始化數(shù)組而不是擴(kuò)容
else if (oldThr > 0)
// 說明調(diào)用的是HashMap的有參構(gòu)造函數(shù)，因為無參構(gòu)造函數(shù)并沒有對threshold進(jìn)行初始化
newCap = oldThr;
// 表示需要初始化數(shù)組而不是擴(kuò)容，零初始閾值表示使用默認(rèn)值
else {
// 說明調(diào)用的是HashMap的無參構(gòu)造函數(shù)
newCap = DEFAULT_INITIAL_CAPACITY;
// 計算目標(biāo)閾值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 當(dāng)目標(biāo)閾值為0時需重新計算，公式：容量（newCap）*負(fù)載系數(shù)（loadFactor）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 根據(jù)以上計算結(jié)果將閾值更新
threshold = newThr;
// 將新數(shù)組賦值給底層數(shù)組
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// -------------------------------------------------------------------------------------
// 此時已完成初始化數(shù)組或擴(kuò)容數(shù)組，但原數(shù)組內(nèi)的數(shù)據(jù)并未遷移至新數(shù)組（擴(kuò)容后的數(shù)組），之后的代碼則是完成原數(shù)組向新數(shù)組的數(shù)據(jù)遷移過程
// -------------------------------------------------------------------------------------
// 判斷原數(shù)組內(nèi)是否有存儲數(shù)據(jù)，有的話開始遷移數(shù)據(jù)
if (oldTab != null) {
// 開始循環(huán)遷移數(shù)據(jù)
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 將數(shù)組內(nèi)此下標(biāo)中的數(shù)據(jù)賦值給Node類型的變量e，并判斷非空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1 - 普通元素判斷：判斷數(shù)組內(nèi)此下標(biāo)中是否只存儲了一個元素，是的話表示這是一個普通元素，并開始轉(zhuǎn)移
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 2 - 紅黑樹判斷：判斷此下標(biāo)內(nèi)是否是一顆紅黑樹，是的話進(jìn)行數(shù)據(jù)遷移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3 - 鏈表判斷：若此下標(biāo)內(nèi)包含的數(shù)據(jù)既不是普通元素又不是紅黑樹，則它只能是一個鏈表，進(jìn)行數(shù)據(jù)轉(zhuǎn)移
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;
}
}
}
}
}
// 返回初始化完成或擴(kuò)容完成的新數(shù)組
return newTab;
}容量和負(fù)載系數(shù)決定了數(shù)組容量，空余太多會造成空間浪費，使用太滿會影響操作性能
如果能夠明確知道 HashMap 將要存取的鍵值對的數(shù)量，可以考慮預(yù)先設(shè)置合適的容量大小。具體數(shù)值我們可以根據(jù)擴(kuò)容發(fā)生的條件來做簡單預(yù)估，根據(jù)前面的代碼分析，我們知道它需要符合計算條件：負(fù)載因子 * 容量 > 元素數(shù)量
所以，預(yù)先設(shè)置的容量需要滿足，大于 預(yù)估元素數(shù)量 / 負(fù)載因子，同時它是 2 的冪數(shù)
但需要注意的是：
如果沒有特別需求，不要輕易進(jìn)行更改，因為 JDK 自身的默認(rèn)負(fù)載因子是非常符合通用場景的需求的。如果確實需要調(diào)整，建議不要設(shè)置超過 0.75 的數(shù)值，因為會顯著增加沖突，降低 HashMap 的性能。如果使用太小的負(fù)載因子，按照上面的公式，預(yù)設(shè)容量值也進(jìn)行調(diào)整，否則可能會導(dǎo)致更加頻繁的擴(kuò)容，增加無謂的開銷，本身訪問性能也會受影響。
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;
// 將table賦值給變量tab并判斷非空 && tab 的廠部大于0 && 通過位運算得到求模結(jié)果確定鏈表的首節(jié)點賦值并判斷非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷首節(jié)點hash值 && 判斷key的hash值（地址相同 || equals相等）均為true則表示first即為目標(biāo)節(jié)點直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 若首節(jié)點非目標(biāo)節(jié)點，且還有后續(xù)節(jié)點時，則繼續(xù)向后尋找
if ((e = first.next) != null) {
// 1 - 樹：判斷此節(jié)點是否為樹的節(jié)點，是的話遍歷樹結(jié)構(gòu)查找節(jié)點，查找結(jié)果可能為null
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 2 - 鏈表：若此節(jié)點非樹節(jié)點，說明它是鏈表，遍歷鏈表查找節(jié)點，查找結(jié)果可能為null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}HashMap 為什么會被樹化
為了保證數(shù)據(jù)安全及相關(guān)操作效率
因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴(yán)重影響存取的性能
而在現(xiàn)實世界，構(gòu)造哈希沖突的數(shù)據(jù)并不是非常復(fù)雜的事情，惡意代碼就可以利用這些數(shù)據(jù)大量與服務(wù)器端交互，導(dǎo)致服務(wù)器端 CPU 大量占用，這就構(gòu)成了哈希碰撞拒絕服務(wù)攻擊，國內(nèi)一線互聯(lián)網(wǎng)公司就發(fā)生過類似攻擊事件
感謝各位的閱讀！關(guān)于Java中HashMap的案例分析就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼