HashMap
是我們最常用的集合類型之一了。也由于其高效、使用友善,我們有必要對其内部進行梳理一番。
JDK1.8源碼中,關于
Map
的類圖關系如下:
Map
家族的對比
Map
從
Map
的類圖關系中,我們可以看出還是蠻豐富的。需要用到順序的,可以使用
TreeMap
,需要線程安全的可以使用
HashTable
和
ConcurrentHashMap
。其各自特點總結如下:
類 | 特點 |
---|---|
| 存儲資料無序;非線程安全;key可為 ,但是其桶索引為0;效率為O(1) |
| 遠古時代就具有的,存儲資料無序;線程安全,但是是使用笨重的 ;key不可為 |
| 新貴,存儲資料無序;線程安全,采用 ;key不可為 |
| 存儲資料有序;非線程安全 |
| 存儲資料有序;非線程安全 |
讓我們先從
HashMap
開始。
HashMap
概述
HashMap
JDK1.7中,
HashMap
由數組和連結清單構成,當連結清單資料特别多的時候,很明顯的其效率受到影響。于是,在JDK1.8中的
HashMap
當連結清單資料過長時,轉為紅黑樹的資料結構。
HashMap
源碼
HashMap
我們選取常用的幾個方法(執行個體化、put)來看下源碼。
HashMap
屬性
HashMap
//Map預設初始化的容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//Map的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//連結清單轉為紅黑樹的門檻值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉為連結清單的門檻值
static final int UNTREEIFY_THRESHOLD = 6;
//連結清單轉為紅黑樹表的門檻值
static final int MIN_TREEIFY_CAPACITY = 64;
//桶數組
transient Node<K,V>[] table;
//對Map的entrySet結果緩存
transient Set<Map.Entry<K,V>> entrySet;
//key-value對的數量
transient int size;
//增加或者删除Map元素、rehash的次數
transient int modCount;
//HashMap需要resize的門檻值
int threshold;
//負載因子
final float loadFactor;
HashMap
初始化
HashMap
選取個複雜點的構造方法:
//initialCapacity表示HashMap的容量,loadFactor表示負載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//tableSizeFor是将initialCapacity轉為不小于其的最小2的幂次方
this.threshold = tableSizeFor(initialCapacity);
}
//tableSizeFor的方法如下
//目前算法我看的不太明白
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;
}
大家通過源代碼可以看到,初始化時,可以說幾乎沒發生沒什麼事情。隻指派了
loadFactor
和確定
Map
的容量為2的幂次方。
這裡就有個問題?為什麼需要確定
Map
的容量為2的幂次方?其實這是個非正常的設計,正常的設計是把桶的大小設計為素數(參考:https://blog.csdn.net/liuqiyao_01/article/details/14475159)。在講完
put
方法後我們來闡述。
其實,這裡可以看作是
Map
的延遲初始化。在首次
put
元素時,會初始化屬性
table
。在這裡順便提下
table
的類型
Node
。在為連結清單時,其資料結構為:
//連結清單節點
static class Node<K,V> implements Map.Entry<K,V> {
//key的hash值
final int hash;
//Map的key值
final K key;
//Map的key對應的value
V value;
//下一個元素
Node<K,V> next;
//省略getter&setter、equals
}
當轉為紅黑樹時,其結構為:
//樹節點
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;
}
HashMap put
方法
HashMap put
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.首次存入元素時,會在resize方法中初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.如果key對應的索引位置((n - 1) & hash)沒有元素,則直接存入元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//3.如果key對應的索引位置有元素
Node<K,V> e; K k;
//3.1 如果key相同,則直接覆寫key對應的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//3.2 如果key不同,判斷Node是否屬于紅黑樹類型,是則入樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//3.3 Node屬于連結清單節點類型
for (int binCount = 0; ; ++binCount) {
//3.3.1 下一個節點為空,則插傳入連結表中
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//3.3.1.1 節點數量是否超過樹化的門檻值,超過則進行樹化。注意此處并非一定會轉化為紅黑樹,還會判斷屬性table的長度,可以參考treeifyBin方法
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//3.3.2 下一個節點不為空,判斷key是否相同,相同則覆寫舊值
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;
//為LinkedHashMap預備
afterNodeAccess(e);
return oldValue;
}
}
//添加修改次數
++modCount;
//超過門檻值則配置設定空間,重新rehash運算
if (++size > threshold)
resize();
//為LinkedHashMap預備
afterNodeInsertion(evict);
return null;
}
我們可以畫個流程圖:
其他的方法,譬如
get
、
remove
等,主要的都是先要确定
key
對應的索引。即
hash & (n - 1)
。其中
hash
為
key
對應的
hash
值,
n
為
capacity
,即
Map
的容量。
我們先來看下
hash
的計算:
static final int hash(Object key) {
int h;
//如果為null,則索引為0;否則是其hashCode低16位與hashCode高16位的抑或結果
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
為什麼
hashCode
需要與其高16為抑或?簡單點說就是讓高位和低位都參與運算,使
key
的分布盡量更均勻些。參見https://zhuanlan.zhihu.com/p/21673805
有了
hash
值之後,我們可以計算索引的位置了。一般都是取模運算,但是大家都知道計算機是二進制的,位運算會比取餘快多了。是以這裡的
hash & (n - 1)
可以看做是用空間來換取時間。因為當
n
為2的幂次方時,
n-1
的二進制恰恰全是
1
,其與
hashCode
的二進制與值正好是取模的結果。這裡就回答了上面為什麼需要確定
Map
的容量為2的幂次方的問題。
HashMap
的源碼目前就分析到這裡。流程其實說起來不是很難,難的關鍵就是為什麼設計者會是這樣的設計?這恰恰是我們需要多思考的。本篇在關于這一點上還是遠遠不足的,大家可以多搜尋幾篇來看看,多思考思考。