理解HashMap

Has45C 8年前發布 | 7K 次閱讀鏈表紅黑樹 Java開發

以 Android 最新源碼里面的 HashMap 為例，其實也和 JDK8 里面的 HashMap 差不多。

位置：[aosp]/libcore/ojluni/src/main/java/java/util/HashMap.java

思考

如果從零開始設計一個 HashMap 結構該如何思考？

棧？隊列？數組？鏈表？樹？圖？

結構

早期的 HashMap 的確是只使用了數組和鏈表，但從 Java8 中開始引入樹（紅黑樹）結構以提高鏈表過長情況下的性能。

數組:

transient Node<K,V>[] table;

鏈表 Node(next)：

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;
 }
}

紅黑樹 TreeNode(parent, left, right)：

staticfinalclassTreeNode<K,V>extendsLinkedHashMap.LinkedHashMapEntry<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
booleanred;
 TreeNode(inthash, K key, V val, Node<K,V> next) {
super(hash,key,val,next);
 }
}

基本原理

詳細的細節后面會逐步闡述，HashMap 的核心原理就是，把數據的 key 轉化為 hash 值，放到某 n 長度的數組中改 hash 對應的 position，比如 hash 為 0，則放在數組的第1個位置，如果 hash 為111，則放在數組的第 112 個位置。這樣每次根據 hash 值就能直接知道放在什么位置，或者反過來，根據 hash 值就能直接知道從哪個位置取值。

但是這樣做，會面臨幾個問題：

第一，hash 值一般都是很大，豈不是數組要很大？

這個問題好解決，hash按數組長度取模，這樣無論多大的 hash 總能在數組的范圍之內。

順便一問，取模操作：(n - 1) & hash，想想為什么？

第二，取模后，那么多 hash 取模可能重復在數組的同一位置怎么辦？

這個叫碰撞沖突，這個時候這個 hash 值對應的 Node 既不能放在正確的 position（已被其他占用），也不能隨便的放在其他位置（否則下次就找不到了），我們發現，數組已經不能滿足需求了。

上鏈表！

把這個 Node 掛到已經占用位置的 Node 的 next 上，如果 next 已經被掛了，那就next-next順藤摸瓜掛在最后一個 Node 的next上。

第三，掛起來容易，要查詢的時候怎么找？

無碰撞沖突的情況下，定位到數組位置就找到了。

有碰撞沖突的情況下，定位到數組后，next-next順藤摸瓜，根據key是否相等來判斷是否找到（hash相同碰撞了，但是key總是不同的）。

第四，好像沒用到紅黑樹啊？

當鏈表過長時，可以用紅黑樹去優化性能，關于紅黑樹這里不多講。

三個概念

容量、負載因子、閾值：

容量

// 因為用的是數組，定義一個容量是一個好事，比每次需要動態改變容量性能總是要好的多的。
// 初始化默認值 16
staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;
transientNode<K,V>[] table;
transientintsize;

負載因子

// 如果頻繁的發生碰撞，那么性能就會直線下降。
// 為了提高性能，不要等到滿了才擴容，而是當實際個數到達某個比例就擴容。
// 這個比例就是負載因子：loadFactor，默認為0.75。
finalfloatloadFactor;

閾值

// 超過這個值則以翻倍形式擴容(resize)
// 簡單的計算：threshold = capacity * load factor
intthreshold;

插入(PUT)

見注釋。

/**
 * Implements Map.put and related methods
 *
 * @paramhash hash for key
 * @paramkey the key
 * @paramvalue the value to put
 * @paramonlyIfAbsent if true, don't change existing value
 * @paramevict if false, the table is in creation mode.
 * @returnprevious value, or null if none
 */
finalVputVal(inthash, K key, V value,booleanonlyIfAbsent,
booleanevict) {
 Node<K,V>[] tab; Node<K,V> p; intn, i;
if((tab = table) ==null|| (n = tab.length) ==0)
// 空檢查
 n = (tab = resize()).length;
if((p = tab[i = (n -1) & hash]) ==null)
// 不存在，直接插入
// 注意 i = (n - 1) & hash 就是取模定位數組的索引
 tab[i] = newNode(hash, key, value, null);
else{
// 已存在：一模一樣的值或者碰撞沖突
 Node<K,V> e; K k;
if(p.hash == hash &&
 ((k = p.key) == key || (key != null&& key.equals(k))))
// 已經存在一個一模一樣的值
 e = p;
elseif(pinstanceofTreeNode)
// 樹，略
 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else{
// 碰撞沖突，順藤摸瓜掛在鏈表的最后一個next上
for(intbinCount =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;
 }
 }
// 注意：if true, don't change existing value
if(e !=null) {// existing mapping for key
 V oldValue = e.value;
if(!onlyIfAbsent || oldValue ==null)
 e.value = value;
 afterNodeAccess(e);
returnoldValue;
 }
 }
 ++modCount;
if(++size > threshold)
 resize();
 afterNodeInsertion(evict);
returnnull;
}

查詢(GET)

見注釋。

/**
 * Implements Map.get and related methods
 *
 * @paramhash hash for key
 * @paramkey the key
 * @returnthe node, or null if none
 */
finalNode<K,V>getNode(inthash, Object key){
 Node<K,V>[] tab; Node<K,V> first, e; intn; K k;
if((tab = table) !=null&& (n = tab.length) >0&&
 (first = tab[(n - 1) & hash]) !=null) {
// 注意 i = (n - 1) & hash 就是取模定位數組的索引
if(first.hash == hash &&// always check first node
 ((k = first.key) == key || (key != null&& key.equals(k))))
// 找到：hash相等 和 key也相等
returnfirst;
if((e = first.next) !=null) {
if(firstinstanceofTreeNode)
// 遞歸樹查找
return((TreeNode<K,V>)first).getTreeNode(hash, key);
 do {
// 遍歷鏈表
if(e.hash == hash &&
 ((k = e.key) == key || (key != null&& key.equals(k))))
returne;
 } while((e = e.next) !=null);
 }
 }
returnnull;
}

擴容(Resize)

resize 的代碼我就不貼了，這里只強調一點：

每次擴容都需要重新分配數組，并把老的值再分配到新的數組，代價還是挺大的，所以盡量避免擴容。

舉個例子，現在可能大約有 100 個

，我們比較一下：

// 128 = 2^7 < 100/0.75 < 2^8 = 256
// 最簡單的形式，只是純粹的聲明變量
// 初始化容量16 = 2^4，最后會到2^8才夠用
// 中間會經歷了4次擴容
newHashMap<String, String>();

// 指定容量，優化后，無擴容，又剛好夠用
newHashMap<String, Strring>(256);

其他

常見的幾個問題的簡要說明。

HashMap 和 HashTable 區別

在 HashMap 的官方文檔第一段里面就有句話：

The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

簡簡單單的一句話道出了兩點核心區別：

HashMap是unsynchronized，要注意線程安全；
HashMap允許null而HashTable不允許null。

同步

HashMap 不是線程安全的，如果有并發問題，請使用 ConcurrentHashMap （當然也可以用 HashTable ）。

這個問題其實很重要，《疫苗：Java HashMap的死循環》提到，淘寶因為沒考慮到 HashMap 在并發的情況下會有問題，出現死循環，CPU 達到100%。

Fail-Fast機制

在創建迭代器后，如果發現 HashMap 發生變化，則拋出 ConcurrentModificationException 異常，這就是 Fail-Fast 機制。

這也是一種契約約束吧。

HashMap 主要是通過 modCount 來記錄和檢測的，大概代碼片段如下（僅作示意）：

if(map.modCount != expectedModCount)
thrownewConcurrentModificationException();

巧妙的取模

加入數組長度是 n, 如果要對 hash 取模，大家可能想到的解法是：

hash % n

而 HashMap 采用的方法是：

// n 是 2 的次方，所以 n - 1 的而進制01111111111..
// hash “與” 01111111111實際上是取保留低位值，結果在 n 的范圍之內，類似于取模。
// 對于我這種沒見過市面的人來說，還是很巧妙的。
hash & (n - 1)

后者比前者性能據說要高好幾倍，可以考慮一下為什么。

數組長度為什么總是設定為 2 的 N 次方？

從上面的問題的答案中，基本可以管中窺豹，一切都是為了性能。

1. 取模快。

其實就是上面為什么快的原因：位與取模比 % 取模要快的多。

2. 分散平均，減少碰撞。

這個是主要原因。

如果二進制某位包含 0，則此位置上的數據不同對應的 hash 卻是相同，碰撞發生，而 (2^x - 1) 的二進制是 0111111…，分散非常平均，碰撞也是最少的。

小結

HashMap 做為一個經典的數據結構，值得我們去分析原理去理解透徹，很有幫助。

而且 HashMap 也是是最常見的面試問題。

來自：http://www.jayfeng.com/2016/11/17/理解HashMap/

本文由用戶 Has45C 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1479437384694.html

鏈表紅黑樹 Java開發

理解HashMap

思考

結構

基本原理

三個概念

插入(PUT)

查詢(GET)

擴容(Resize)

其他

小結

相關經驗

相關資訊

相關文檔

目錄