溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java數據結構之HashMap源碼分析”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java數據結構之HashMap源碼分析”吧！
HashMap是Java集合框架中常用的一種數據結構,它是一種基于哈希表實現的映射表.在JDK1.8版本中,HashMap的get方法和put方法的實現與之前版本有些不同,下面我們來逐步分析其源碼實現.
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// ...
/**
* 默認初始容量為16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 默認負載因子為0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 最大容量:1 << 30(2的30次方)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 存放元素的數組,長度總是2的冪次方
*/
transient HashMap.Node<K,V>[] table;
/**
* 存放鍵值對的數量
*/
transient int size;
/**
* 擴容操作的閾值
*/
int threshold;
/**
* 負載因子,用于計算閾值
*/
final float loadFactor;
// ...
} /**
* 根據key獲取value,如果key不存在則返回null
*
* @param key
* @return
*/
public V get(Object key) {
// 獲取key對應的Node節點
HashMap.Node<K, V> e;
// 調用getNode方法查找key對應的Node節點,并將查找結果賦值給e
// 如果e為null就返回null否則返回e節點的value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 根據key的哈希值和key查找對應的Node節點
*
* @param hash
* @param key
* @return
*/
final HashMap.Node<K, V> getNode(int hash, Object key) {
// 定義局部變量tab,first,e,n和k
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> first, e;
int n;
K k;
// 如果table數據不為null且長度大于0,且第一個Node節點不為空,則開始查找Node節點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果第一個Node節點的哈希值與傳入的hash值相等,且第一個Node節點的key和傳入的key相等,則直接返回第一個Node節點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果第一個Node節點不是要查找的Node節點,則開始遍歷鏈表查找對應的Node節點
if ((e = first.next) != null) {
if (first instanceof HashMap.TreeNode)
// 如果第一個Node節點是紅黑樹節點,則調用紅黑樹節點的getTreeNode方法查找對應的Node節點
return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
// 如果第一個Node節點不是紅黑樹節點,則遍歷鏈表查找對應的Node節點
do {
// 如果遍歷到的Node節點的hash值與傳入的hash值相等,且Node節點的key和傳入的key相等,則返回對應的Node節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 如果在table數組中沒有找到對應的Node節點,則返回null
return null;
}get方法工作流程如下:
根據key的hashCode計算出在哈希表中的位置
遍歷該位置上的鏈表或樹,查找對應的鍵值對
如果找到了對應的鍵值對,則返回對應的value;否則返回null
/**
* 向HashMap中添加一個key-value鍵值對
*
* @param key
* @param value
* @return
*/
public V put(K key, V value) {
// 根據key的哈希值和key查找對應的Node節點,并添加到HashMap中
return putVal(hash(key), key, value, false, true);
}
/**
* 根據key的hash值和key添加一個鍵值對到HashMap中
*
* @param hash
* @param key
* @param value
* @param onlyIfAbsent
* @param evict
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定義局部變量tab,p,n和i
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
// 如果table數組為null或者長度為0,則先調用resize()方法初始化table數組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根據計算出來插入位置i插入新的鍵值對
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果插入的位置為null,則直接插入新的鍵值對
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K, V> e;
K k;
// 如果插入的位置不為null,就遍歷鏈表或樹查找插入位置
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof HashMap.TreeNode)
// 如果插入位置為紅黑樹節點,則調用putTreeVal方法插入新的鍵值對
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// 遍歷鏈表,查找插入位置
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
// 如果此時鏈表長度大于等于8,則將鏈表轉化為紅黑樹
treeifyBin(tab, hash);
break;
}
// 如果找到相同key,終止循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// 如果存在相同key,則替換對應value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 如果插入后的HashMap的大小大于閾值,則調用resize方法擴容HashMap
resize();
afterNodeInsertion(evict);
return null;
}put方法工作流程如下:
根據key的hashCode值計算出在哈希表中的位置
如果該位置為空,則直接插入新的鍵值對
如果該位置不為空,則遍歷該位置上的鏈表或樹,查找是否已經存在對應的鍵值對
如果找到對應的鍵值對,則替換對應的value
如果沒有找到對應的鍵值對,則將新的鍵值對插入到鏈表末尾
如果鏈表長度達到閾值(默認為8),則將鏈表轉化為樹
如果插入后HashMap的大小超過了閾值(默認容量的0.75),則擴容HashMap
插入完成后,執行一些必要的后續操作,例如更新修改次數等等
總的來說,HashMap的get方法和put方法都是基于哈希算法來實現鍵值對的查找和插入的,其中put方法需要考慮更多的情況,包括鏈表轉換為樹,擴容等等.
在Java中,HashMap的容量總是2的n次冪的原因是為了提高HashMap的性能.
HashMap內部使用一個數組來存儲鍵值對,當添加一個鍵值對時,HashMap會根據建的hashCode值計算出它在數組中的索引位置.如果數組長度不是2的n次冪,那么計算索引時就需要進行取模操作,這會影響HashMap的性能.
如果數組長度時2的n次冪,那么計算索引時可以使用位運算(&操作),這比取模操作更快.而且,HashMap的擴容操作也要求長度時2的n次冪,這樣在擴容時可以簡化計算,提高性能.
另外,長度為2的n次冪的數組大小還有一個優點是,它可以保證數組的不同位置發生哈希沖突的概率比較平均,這可以減少哈希沖突的發生,提高HashMap的效率.
感謝各位的閱讀，以上就是“Java數據結構之HashMap源碼分析”的內容了，經過本文的學習后，相信大家對Java數據結構之HashMap源碼分析這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
