走,HashMap,敢去爬山嗎?
List 系列差不多寫完了, 單線程環境下最重要的就是 ArrayList 和LinkedList,多線程環境下最重要的就是CopyOnWriteArrayList,新來的同學可以點擊鏈接回顧一下 List 的知識點。接下來,我要帶着 HashMap 去爬山了,注意不是六峯山,純粹就是爲了鍛鍊了一下身體,不不不,純粹是爲了和 HashMap 拉近關係,同學們注意不要掉隊。
說一句很廢的話,HashMap 是一個 Map,用來存儲 key-value 的鍵值對,每個鍵都可以精確地映射到一個值,然後我們可以通過這個鍵快速地找到對應的值。
對於一個 List 來說,如果要找到一個值,時間複雜度爲,如果 List 排序過的話,時間複雜度可以降低到(二分查找法),但如果是 Map 的話,大多數情況下,時間複雜度能夠降低到。
來看一下 HashMap 的特點:
-
HashMap 的鍵必須是唯一的,不能重複。
-
HashMap 的鍵允許爲 null,但只能有一個這樣的鍵;值可以有多個 null。
-
HashMap 是無序的,它不保證元素的任何特定順序。
-
HashMap 不是線程安全的;多線程環境下,建議使用 ConcurrentHashMap,或者使用
Collections.synchronizedMap(hashMap)
將 HashMap 轉成線程同步的。 -
只能使用關聯的鍵來獲取值。
-
HashMap 只能存儲對象,所以基本數據類型應該使用其包裝器類型,比如說 int 應該爲 Integer。
-
HashMap 實現了 Cloneable 和 Serializable 接口,因此可以拷貝和序列化。
01、HashMap 的重要字段
HashMap 有 5 個非常重要的字段,我們來了解一下。(JDK 版本爲 14)
transient Node<K,V>[] table;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
1)table 是一個 Node 類型的數組,默認長度爲 16,在第一次執行 resize()
方法的時候初始化。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
final HashMap.Node<K,V>[] resize() {
newCap = DEFAULT_INITIAL_CAPACITY;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}
Node 是 HashMap 的一個內部類,實現了 Map.Entry 接口,本質上是一個鍵值對。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
HashMap.Node<K,V> next;
Node(int hash, K key, V value, HashMap.Node<K,V> next) {
...
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
...
}
public final V setValue(V newValue) {
...
}
public final boolean equals(Object o) {
...
}
}
2)size 就是 HashMap 中實際存儲的鍵值對數量,它和 table 的 length 是有區別的。
爲了說明這一點,我們來看下面這段代碼:
HashMap<String,Integer> map = new HashMap<>();
map.put("1", 1);
聲明一個 HashMap,然後 put 一個鍵值對。在 put()
方法處打一個斷點後進入,等到該方法臨近結束的時候加一個 watch( table.length
),然後就可以觀察到如下結果。
也就是說,數組的大小爲 16,但 HashMap 的大小爲 1。
3)modCount 主要用來記錄 HashMap 實際操作的次數,以便迭代器在執行 remove()
等操作的時候快速拋出 ConcurrentModificationException,因爲 HashMap 和 ArrayList 一樣,也是 fail-fast 的。
關於 ConcurrentModificationException 的更多信息,請點擊下面的鏈接查看 03 小節的內容。
4)threshold 用來判斷 HashMap 所能容納的最大鍵值對數量,它的值等於數組大小 * 負載因子。默認情況下爲 12(16 * 0.75),也就是第一次執行 resize()
方法的時候。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final HashMap.Node<K,V>[] resize() {
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
5)loadFactor 爲負載因子,默認的 0.75 是對空間和時間效率上的一個平衡選擇,一般不建議修改,像我這種工作了十多年的老菜鳥,就從來沒有修改過這個值。
02、HashMap 的 hash 算法
Hash,一般譯作“散列”,也有直接音譯爲“哈希”的,這玩意什麼意思呢?就是把任意長度的數據通過一種算法映射到固定長度的域上(散列值)。
再直觀一點,就是對一串數據 wang 進行雜糅,輸出另外一段固定長度的數據 er——作爲數據 wang 的特徵。我們通常用一串指紋來映射某一個人,別小瞧手指頭那麼大點的指紋,在你所處的範圍內很難找出第二個和你相同的(人的散列算法也好厲害,有沒有?)。
對於任意兩個不同的數據塊,其散列值相同的可能性極小,也就是說,對於一個給定的數據塊,找到和它散列值相同的數據塊極爲困難。再者,對於一個數據塊,哪怕只改動它的一個比特位,其散列值的改動也會非常的大——這正是 Hash 存在的價值!
同學們已經知道了,HashMap 的底層數據結構是一個數組,那不管是增加、刪除,還是查找鍵值對,定位到數組的下標非常關鍵。
那 HashMap 是通過什麼樣的方法來定位下標呢?
第一步, hash()
方法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
第二步, putVal()
方法中的一行代碼:
n = (tab = resize()).length;
i = (n - 1) & hash;
爲了更容易理解,我把這兩步的方法合併到了一起:
String [] keys = {"沉","默","王","二"};
for (String k : keys) {
int hasCode = k.hashCode();
int right = hasCode >>> 16;
int hash = hasCode ^ right;
int i = (16 - 1) & hash;
System.out.println(hash + " 下標:" + i);
}
1) k.hashCode()
用來計算鍵的 hashCode 值。對於任意給定的對象,只要它的 hashCode()
返回值是相同,那麼 hash()
方法計算得到的 Hash 碼就總是相同的。
要能夠做到這一點,就要求作爲鍵的對象必須是不可變的,並且 hashCode()
方法要足夠的巧妙,能夠最大可能返回不重複的 hashCode 值,比如說 String 類。
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
2) >>>
爲無符號右移運算符,高位補 0,移多少位補多少個 0。
3) ^
爲異或運算符,其運算規則爲 1^0 = 1、1^1 = 0、0^1 = 1、0^0 = 0。
4) &
爲按位與運算符,運算規則是將兩邊的數轉換爲二進制位,然後運算最終值,運算規則即(兩個爲真才爲真)1&1=1、1&0=0、0&1=0、0&0=0。
關於 >>>
、 ^
、 &
運算符,涉及到二進制,本篇文章不再深入研究,感興趣的同學可以自行研究一下。
假如四個字符串分別是"沉","默","王","二",它們通過 hash()
方法計算後值和下標如下所示:
27785 下標:9
40664 下標:8
29579 下標:11
20108 下標:12
應該說,這樣的 hash 算法非常巧妙,尤其是第二步。
HashMap 底層數組的長度總是 2 的 n 次方,當 length 總是 2 的 n 次方時, (length - 1) & hash
運算等價於對數組的長度取模,也就是 hash%length
,但是 & 比 % 具有更高的效率。
03、HashMap 的 put()
方法
HashMap 的 hash 算法我們是明白了,但似乎有一絲疑慮,就是萬一計算後的 hash 值衝突了怎麼辦?
比如說,“沉X”計算後的 hash 值爲 27785,其下標爲 9,放在了數組下標爲 9 的位置上;過了一會,又來個“沉Y”計算後的 hash 值也爲 27785,下標也爲 9,也需要放在下標爲 9 的位置上,該怎麼辦?
爲了模擬這種情況,我們來新建一個自定義的鍵類。
public class Key {
private final String value;
public Key(String value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value.equals(key.value);
}
@Override
public int hashCode() {
if (value.startsWith("沉")) {
return "沉".hashCode();
}
return value.hashCode();
}
}
在 hashCode()
方法中,加了一個判斷,如果鍵是以“沉”開頭的話,就返回“沉”的 hashCode 值,這就意味着“沉X”和“沉Y”將會出現在數組的同一個下標上。
HashMap<Key,String> map = new HashMap<>();
map.put(new Key("沉X"),"沉默王二X");
map.put(new Key("沉Y"),"沉默王二Y");
那緊接着來看一下 put()
方法的源碼:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put()
方法會先調用 hash()
方法計算 key 的 hash 值,然後再調用內部方法 putVal()
:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// ①、數組 table 爲 null 時,調用 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 {
HashMap.Node<K,V> e; K k;
// ③、如果鍵已經存在了,並且 hash 值相同,直接覆蓋
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④、紅黑樹處理
else if (p instanceof HashMap.TreeNode)
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);
// 如果鏈表長度大於 8 轉換爲紅黑樹處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果鍵已經存在了,並且 hash 值相同,直接覆蓋
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;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// ⑥、超過容量限制,擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
代碼裏我加了一些註釋,同學們一定要花點時間看一下。
如果哈希衝突的話,會執行 ② 處對應的 else 語句,先判斷鍵是否相等,相等的話直接覆蓋;否則執行 ④,做紅黑樹處理;如果不是,會執行 ⑤,把上一個節點的 next 賦值爲新的 Node。
也就是說,如果哈希衝突了,會在數組的同一個位置上增加鏈表,如果鏈表的長度大於 8,將會轉化成紅黑樹進行處理。
以上就是大牛們嘴裏常說的“鏈地址法”,簡單點說,就是數組加鏈表,由於鏈表的查詢效率比較低(時間複雜度爲),Java 8 又追加了紅黑樹(時間複雜度爲)。
留個小作業哈,同學們可以研究一下,當鍵爲 null 的時候,鍵值對存放在什麼位置上?
04、HashMap 的 get()
方法
理解了 HashMap 的 hash 算法和 put()
方法, get()
方法就很容易理解。
public V get(Object key) {
HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
首先計算 key 的 hash 值,當 hash 值確定後,鍵值對在數組中的下標位置也就確定了,然後再調用 getNode()
方法:
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.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) {
if (first instanceof HashMap.TreeNode)
return ((HashMap.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;
}
其中 first = tab[(n - 1) & hash]
就可以快速的確定鍵對應的值,如果鍵相等並且鍵的 hash 相等,則直接返回;如果鍵的哈希衝突了,就先判斷是不是紅黑樹,不是的話就遍歷鏈表。
05、最後
說句實在話,在寫這篇文章之前,我對 HashMap 的認知並沒有這麼深刻,但寫完這篇文章後,我敢拍着胸脯信誓旦旦地說:“HashMap 我真的掌握了,同學們誰以後再問我,就可以把這篇文章甩給他了。”
這次爬山雖然很累,但確實收穫很大,值了!
------------------
公衆號:沉默王二(ID:cmower)
CSDN:沉默王二
這是一個有顏值卻靠才華喫飯的程序員,你知道,他的文章風趣幽默,讀起來就好像花錢一樣爽快。
長按下圖二維碼關注,你將感受到一個有趣的靈魂, 且每篇文章都有乾貨。
-------------- --- -
原創不易,莫要白票,如果覺得有點用的話,請毫不留情地素質三連吧,分享、點贊、在看,我不挑 ,因爲這將是我寫作更多優質文章的最強動力。
PS:公佈昨天送書的中獎讀者,我聯繫他們要郵寄地址的時候,都驚呆了,紛紛表示不相信自己有這樣的好運氣,我真的是氣啊。知道我爲了從 1 數到 200 有多累嗎?
一邊要記到小紙條上,一邊還怕數錯,前後要數兩遍,真不知道爲什麼自己要這麼幹?可能就是純粹想給讀者們謀求點福利啊,你說出版社也看上咱的名氣了,非要(可能不恰當,就裝逼一下吧)送書給二哥。抽獎助手吧,有人說不公平,所以二哥就只能自己手數,採取這種笨辦法。
第 1:ELK
第 50:自由如風
第 100:張魚兒
第 150:the catcher in the rye
第 200:zzx
不知道爲什麼,前 150 達成的很快,第 150-200 很少,估計很多人看了閱讀量,呀,2000 人閱讀了,是不是沒有機會了,就很早就放棄了,於是我在羣裏喊了好一會。多說一句啊,白嫖的機會你都不珍惜,你還能中大樂透?積極點哈!
好了,不 BB 了,以上五名幸運觀衆,請速給我聯繫。不出意外的話,下週繼續送書。當然了,文章還是要好好看的哦,記得留言,在看,轉發,給二哥滿滿的愛,好嗎?