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 了,以上五名幸運觀衆,請速給我聯繫。不出意外的話,下週繼續送書。當然了,文章還是要好好看的哦,記得留言,在看,轉發,給二哥滿滿的愛,好嗎?

相關文章