目錄
- API要點彙總
- 關系圖
- 函數概要
- 源碼解析
-
- hashmap
- 構造方法
- 插入
- 查找
- 删除
- 替換
- 總結
API要點彙總
- 允許空值與空鍵
- 與Hashtable大緻相同，但是不同步
- 不保證映射順序，特别是不能保證order（不知道翻譯成什麼）在其中不随時間變化
- HashMap執行個體有兩個影響其性能的參數:初始容量和負載因子（load factor）。容量是哈希表中的桶數，初始容量就是建立哈希表時的容量。負載因子是衡量在哈希表的容量被自動增加之前，哈希表被允許獲得多少滿的度量。當哈希表中的條目數超過負載因子和目前容量的乘積時，哈希表将被重新哈希(即重新建構内部資料結構)，這樣哈希表的桶數大約擴充兩倍。
不了解的要點：
- 在hashmap需要存儲許多映射時，需要建立更大容量的Hashmap（比它自己擴充效率高），但使用具有相同hashCode()的多個鍵肯定會降低任何散清單的性能。它建議當鍵是可比較的時，該類可以使用鍵之間的比較順序實作（？），但這個是不同步的，于是又有Map m = Collections.synchronizedMap(new HashMap(…));（？）。
- 這個類的所有“collection view methods”傳回的疊代器都是快速失敗的，如果在建立疊代器之後的任何時候對映射進行結構上的修改，除了通過疊代器自己的remove方法之外，疊代器将抛出ConcurrentModificationException。（不是很了解啊）
關系圖
函數概要
| 功能 | 描述 |
|---|---|
| 構造函數 | 能夠用容量、 負載因子、其它hashmap構造 |
| 删除 | 删除所有、依據某個鍵值、鍵對值删除 |
| 克隆 | 傳回淺克隆（鍵對值不被克隆） |
| set | 轉換為set） |
| 擷取 | 擷取值 |
| 添加 | 以鍵對值、map等資料形式添加 |
| 替換 | 替換鍵值對、替換某一鍵對應的值 |
有些函數沒有功能沒有列出，例如compute，這個是java 8新增，不熟悉，等以後用到再更新吧。
源碼解析
其函數挺多的，我其實隻是挑部分感興趣的代碼看，說實話我也不可能每個函數都看一遍，對于沒有實踐體會的看起來實在是枯燥，也就不看了，等以後遇到使用問題再扒出來看吧。
hashmap
如圖，它的實作方式是一種數組（API指的是桶）加連結清單的組合，HashMap 則使用了拉鍊式的雜湊演算法，并在 JDK 1.8 中引入了紅黑樹優化過長的連結清單，也就是将連結清單部分換成紅黑樹，優化查詢等操作效率，在進行增删查等操作時，首先要定位到元素的所在桶的位置，之後再從連結清單中定位該元素。
構造方法
提供如下四種構造函數：
在這裡，我隻列出兩種，另外兩種都十分簡單：
HashMap(int initialCapacity, float 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;
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;
}
以上是tableSizeFor的具體實作，位右移運算，而且，是不是很懵逼？試着在紙上畫畫，你會發現，在經曆過這些操作之後，原始資料所在位數的低位數将全部變為1，最後n + 1顯然得到的是2的整數幂，比如你輸入一個5，最後會得到一個8。是不是很神奇！
下圖是我在網上找的分析圖，供大家了解（實在懶，不想畫）：
HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
由圖上的源碼可以看出，這種構造函數将負載因子設定為預設值（0.75），随後調用了另一個函數，我們來看這個函數：
putMapEntries:
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//數組還是空，初始化參數
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//數組不為空，超過門檻值就擴容
else if (s > threshold)
resize();
//周遊資料，插入
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
有關evict參數，其注釋這樣解釋：evict false when initially constructing this map, else true (relayed to method afterNodeInsertion).
在進行資料的填充時，它使用到了putVal函數，實際上，Hashmap的put函數就是直接調用這個putVal函數，接下來看看這個函數：
插入
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果目前 哈希表内容為空，建立，n 指向最後一個桶的位置，tab 為哈希表另一個引用，将插入動作延期進行
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;
//如果第一個就是想要找的資料時，就将e指向此節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
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;
}
//如果目前連結清單已經包含要插入的鍵值對，終止插入動作
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;
}
}
//統計修改次數，友善fail-fast的判斷
++modCount;
//判斷是否超過門檻值，進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
首先，我們可以明确的是這個函數的final屬性，傳入的參數hash(key)是對于key進行hash計算：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);接下來我們看到了HashMap 的底層資料結構之一的連結清單數組：Node<K,V>[] table;它被聲明為transient類型（Java中transient關鍵字的作用，簡單地說，就是讓某些被修飾的成員屬性變量不被序列化，能夠節省存儲空間）
查找
查找函數的核心算法封裝在如下函數内：
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) {
//若後續為 TreeNode，按照紅黑樹類型進行查找
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;
}
查詢的整體思路并不複雜，但在第一個條件語句中的tab[(n - 1) & hash]使我困惑，雖然大緻知道是找桶所在的位置，但不清楚實作原理，查找網上相關解析，得到如下解釋：
這裡通過(n - 1)& hash即可算出桶的在桶數組中的位置，可能有的朋友不太明白這裡為什麼這麼做，這裡簡單解釋一下。HashMap 中桶數組的大小 length 總是2的幂，此時，(n - 1) & hash 等價于對 length 取餘。但取餘的計算效率沒有位運算高，是以(n - 1) & hash也是一個小的優化。舉個例子說明一下吧，假設 hash = 185，n = 16。計算過程示意圖如下：Java源碼-hashmapAPI要點彙總關系圖函數概要源碼解析總結
删除
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//判斷是否存在以及桶的位置情況
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//目前節點就是查詢節點，傳回節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//判斷節點的下一個節點是否存在
else if ((e = p.next) != null) {
//判斷是否屬于TreeNode，是就采用紅黑樹的函數得到節點
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//周遊連結清單，擷取節點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 删除節點，并修複連結清單或紅黑樹
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
總的來看，基本思路跟查詢操作類似。
替換
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
上面一些代碼很簡單，就是查詢所在節點是否存在，然後進行替換擦作就行，是以就不再贅述。
總結
首先對這篇文章也不是很滿意，但總歸比上篇好些，有一下幾點：
- 讀起來思維比較混亂，雖然我也是從構造函數看起，遇見陌生函數就直接穿插其代碼分析，顯得抓不住重點
- 每個代碼進行分析之後，沒有相關的函數思路總結
- 有些重點沒有闡述清楚，比如門檻值與容量和負載因子的關系
抛開這些之外，閱讀源碼真是讓我收獲良多，特别印象深刻的有關位運算的應用，我們都知道位運算能極大提高效率，但實際應用上卻遠遠不如，其中有關利用位運算實作求一個數的最接近的幂、實作求桶所在的位置等都讓我驚呼神仙操作，還有許多地方的思維邏輯十分嚴謹，總之這是一個大工程，許多東西我還沒有詳細去看，比如有關紅黑樹的操作，有關擴容機制的詳細内容，自己還有很長一段路要走，看源碼是一件很枯燥的事，但與此同時，看大佬的代碼真的讓人受益匪淺！
共勉！下次的文章自己還會改進有關文章表達方面的問題的。
推薦幾篇文章，我認為寫的非常詳細，至少比我寫的不知道好到哪去了，有一些有關位運算的思路我都是從中才明白的：
HashMap源碼詳細解析（JDK1.8） （推薦！）
Java 集合深入了解（16）：HashMap 主要特點和關鍵方法源碼解讀