溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
HashMap最早出現在JDK1.2中，底層基于散列算法實現。HashMap 允許 null 鍵和 null 值，是非線程安全類，在多線程環境下可能會存在問題。
1.8版本的HashMap數據結構：
為什么有的是鏈表有的是紅黑樹？
默認鏈表長度大于8時轉為樹
Node是HhaspMap中的一個靜態內部類 ：
//Node是單向鏈表，實現了Map.Entry接口
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;
}
// getter and setter ... toString ...
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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;
}
}
TreeNode 是紅黑樹的數據結構。
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
/**
* 默認初始容量16(必須是2的冪次方)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 最大容量，2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認加載因子，用來計算threshold
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表轉成樹的閾值，當桶中鏈表長度大于8時轉成樹
threshold = capacity * loadFactor
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 進行resize操作時，若桶中數量少于6則從樹轉成鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶中結構轉化為紅黑樹對應的table的最小大小
當需要將解決 hash 沖突的鏈表轉變為紅黑樹時，
需要判斷下此時數組容量，
若是由于數組容量太小（小于 MIN_TREEIFY_CAPACITY ）
導致的 hash 沖突太多，則不進行鏈表轉變為紅黑樹操作，
轉為利用 resize() 函數對 hashMap 擴容
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
保存Node<K,V>節點的數組
該表在首次使用時初始化，并根據需要調整大小。 分配時，
長度始終是2的冪。
*/
transient Node<K,V>[] table;
/**
* 存放具體元素的集
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 記錄 hashMap 當前存儲的元素的數量
*/
transient int size;
/**
* 每次更改map結構的計數器
*/
transient int modCount;
/**
* 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
*/
int threshold;
/**
* 負載因子：要調整大小的下一個大小值（容量*加載因子）。
*/
final float loadFactor;
/**
* 傳入初始容量大小，使用默認負載因子值 來初始化HashMap對象
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 默認容量和負載因子
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 傳入初始容量大小和負載因子 來初始化HashMap對象
*/
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否則報錯
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值，否則為最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負載因子不能小于或等于0，不能為非數字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化負載因子
this.loadFactor = loadFactor;
// 初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 找到大于或等于 cap 的最小2的整數次冪的數。
*/
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;
}
用位運算找到大于或等于 cap 的最小2的整數次冪的數。比如10，則返回16
讓cap-1再賦值給n的目的是使得找到的目標值大于或等于原值。例如二進制0100,十進制是4,若不減1而直接操作，答案是0001 0000十進制是16，明顯不符合預期。
對n右移1位：001xx…xxx，再位或：011xx…xxx
對n右移2位：00011…xxx，再位或：01111…xxx
對n右移4位…
對n右移8位…
對n右移16位,因為int最大就2^32所以移動1、2、4、8、16位并取位或,會將最高位的1后面的位全變為1。
再讓結果n+1，即得到了2的整數次冪的值了。
附帶一個實例：
對于 HashMap 來說，負載因子是一個很重要的參數，該參數反應了 HashMap 桶數組的使用情況。通過調節負載因子，可使 HashMap 時間和空間復雜度上有不同的表現。
當我們調低負載因子時，HashMap 所能容納的鍵值對數量變少。擴容時，重新將鍵值對存儲新的桶數組里，鍵的鍵之間產生的碰撞會下降，鏈表長度變短。此時，HashMap 的增刪改查等操作的效率將會變高，這里是典型的拿空間換時間。
相反，如果增加負載因子（負載因子可以大于1），HashMap 所能容納的鍵值對數量變多，空間利用率高，但碰撞率也高。這意味著鏈表長度變長，效率也隨之降低，這種情況是拿時間換空間。至于負載因子怎么調節，這個看使用場景了。
一般情況下，我們用默認值就可以了。大多數情況下0.75在時間跟空間代價上達到了平衡所以不建議修改。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 獲取hash值
static final int hash(Object key) {
int h;
// 拿到key的hash值后與其五符號右移16位取與
// 通過這種方式，讓高位數據與低位數據進行異或，以此加大低位信息的隨機性，變相的讓高位數據參與到計算中。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K,V> getNode(int hash, Object key) {
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) {
// 判斷桶中第一項(數組元素)相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一個結點
if ((e = first.next) != null) {
// 是否是紅黑樹，是的話調用getTreeNode方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 不是紅黑樹的話，在鏈表中遍歷查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
注意：
HashMap的hash算法(hash()方法)。
(n - 1) & hash等價于對 length 取余。
public V put(K key, V value) {
// 調用hash(key)方法來計算hash
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;
// 容量初始化：當table為空，則調用resize()方法來初始化容器
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//確定元素存放在哪個桶中，桶為空，新生成結點放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果鍵的值以及節點 hash 等于鏈表中的第一個鍵值對節點時，則將 e 指向該鍵值對
e = p;
// 如果桶中的引用類型為 TreeNode，則調用紅黑樹的插入方法
else if (p instanceof TreeNode)
// 放入樹中
e = ((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
treeifyBin(tab, hash);
break;
}
// 判斷鏈表中結點的key值與插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判斷要插入的鍵值對是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 鍵值對數量超過閾值時，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
事實上，new HashMap();完成后，如果沒有put操作，是不會分配存儲空間的。
當桶數組 table 為空時，通過擴容的方式初始化 table
查找要插入的鍵值對是否已經存在，存在的話根據條件判斷是否用新值替換舊值
如果不存在，則將鍵值對鏈入鏈表中，并根據鏈表長度決定是否將鏈表轉為紅黑樹
判斷鍵值對數量是否大于閾值，大于的話則進行擴容操作
在 HashMap 中，桶數組的長度均是2的冪，閾值大小為桶數組長度與負載因子的乘積。當 HashMap 中的鍵值對數量超過閾值時，進行擴容。
HashMap 按當前桶數組長度的2倍進行擴容，閾值也變為原來的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;
// 如果數組桶的容量大與0
if (oldCap > 0) {
// 如果比最大值還大，則賦值為最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果擴容后小于最大值 而且 舊數組桶大于初始容量16， 閾值左移1(擴大2倍)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果數組桶容量<=0 且 舊閾值 >0
else if (oldThr > 0) // initial capacity was placed in threshold
// 新容量=舊閾值
newCap = oldThr;
// 如果數組桶容量<=0 且 舊閾值 <=0
else { // zero initial threshold signifies using defaults
// 新容量=默認容量
newCap = DEFAULT_INITIAL_CAPACITY;
// 新閾值= 負載因子*默認容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新閾值為0
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"})
// 創建新數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 覆蓋數組桶
table = newTab;
// 如果舊數組桶不是空，則遍歷桶數組，并將鍵值對映射到新的桶數組中
if (oldTab != null) {
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)
// 重新映射時，需要對紅黑樹進行拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
}
}
}
}
}
return newTab;
}
整體步驟：
計算新桶數組的容量 newCap 和新閾值 newThr
根據計算出的 newCap 創建新的桶數組，桶數組 table 也是在這里進行初始化的
將鍵值對節點重新映射到新的桶數組里。如果節點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節點，則節點按原順序進行分組。
總結起來，一共有三種擴容方式：
使用默認構造方法初始化HashMap。從前文可以知道HashMap在一開始初始化的時候會返回一個空的table，并且thershold為0。因此第一次擴容的容量為默認值DEFAULT_INITIAL_CAPACITY也就是16。同時threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
指定初始容量的構造方法初始化HashMap。那么從下面源碼可以看到初始容量會等于threshold，接著threshold = 當前的容量（threshold） * DEFAULT_LOAD_FACTOR。
HashMap不是第一次擴容。如果HashMap已經擴容過的話，那么每次table的容量以及threshold量為原有的兩倍。
細心點的人會很好奇，為什么要判斷loadFactor為0呢？
loadFactor小數位為 0，整數位可被2整除且大于等于8時，在某次計算中就可能會導致 newThr 溢出歸零。
首先，用鏈表是為了解決hash沖突。
單鏈表能實現為什么要用雙鏈表呢?(雙鏈表需要更大的存儲空間)
插入效率比平衡二叉樹高，查詢效率比普通二叉樹高。所以選擇性能相對折中的紅黑樹。
equals與hashcode間的關系:
如果兩個對象相同（即用equals比較返回true），那么它們的hashCode值一定要相同；
如果兩個對象的hashCode相同，它們并不一定相同(即用equals比較返回false)
因為在 HashMap 的鏈表結構中遍歷判斷的時候，特定情況下重寫的 equals 方法比較對象是否相等的業務邏輯比較復雜，循環下來更是影響查找效率。所以這里把 hashcode 的判斷放在前面，只要 hashcode 不相等就玩兒完，不用再去調用復雜的 equals 了。很多程度地提升 HashMap 的使用效率。
所以重寫 hashcode 方法是為了讓我們能夠正常使用 HashMap 等集合類，因為 HashMap 判斷對象是否相等既要比較 hashcode 又要使用 equals 比較。而這樣的實現是為了提高 HashMap 的效率。
附上源碼圖：
4. HashMap為什么不直接使用對象的原始hash值呢?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我們發現，HashMap的哈希值是通過上面的方式獲取，而不是通過key.hashCode()方法獲取。
原因：
通過移位和異或運算，可以讓 hash 變得更復雜，進而影響 hash 的分布性。
因為紅黑樹需要進行左旋，右旋操作， 而單鏈表不需要。
以下都是單鏈表與紅黑樹結構對比。
如果元素小于8個，查詢成本高，新增成本低。
如果元素大于8個，查詢成本低，新增成本高。
至于為什么選數字8，是大佬折中衡量的結果-.-，就像loadFactor默認值0.75一樣。
對Java技術，架構技術感興趣的同學，歡迎加群，一起學習，相互討論。可以獲取免費的學習資料，群號：614478470
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
