前言
這次我和大家一起學(xué)習(xí)HashMap，HashMap我們在工作中經(jīng)常會(huì)使用，而且面試中也很頻繁會(huì)問到，因?yàn)樗锩嫣N(yùn)含著很多知識(shí)點(diǎn)，可以很好的考察個(gè)人基礎(chǔ)。但一個(gè)這么重要的東西，我為什么沒有在一開始就去學(xué)習(xí)它呢，因?yàn)樗怯啥喾N基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和一些代碼設(shè)計(jì)思想組成的。我們要學(xué)習(xí)了這些基礎(chǔ)，再學(xué)習(xí)HashMap，這樣我們才能更好的去理解它。古人云：無欲速，無見小利。欲速則不達(dá)，見小利則大事不成。
HashMap其實(shí)就是ArrayList和LinkedList的數(shù)據(jù)結(jié)構(gòu)加上hashCode和equals方法的思想設(shè)計(jì)出來的。沒有理解上述說的知識(shí)點(diǎn)的同學(xué)可以翻開我過往的文章記錄。
下面我就以面試問答的形式學(xué)習(xí)我們的——HashMap（源碼分析基于JDK8，輔以JDK7），問答內(nèi)容只是對HashMap的一個(gè)總結(jié)歸納，因?yàn)楝F(xiàn)時(shí)已經(jīng)有大牛把HashMap通俗易懂的剖析了一遍，我學(xué)習(xí)HashMap也是主要通過這篇文章學(xué)習(xí)的，強(qiáng)烈推薦：美團(tuán)點(diǎn)評技術(shù)團(tuán)隊(duì)的Java 8系列之重新認(rèn)識(shí)HashMap
問答內(nèi)容
1.
問：HashMap有用過嗎？您能給我說說他的主要用途嗎？
答：
- 有用過，我在平常工作中經(jīng)常會(huì)用到
HashMap這種數(shù)據(jù)結(jié)構(gòu)，HashMap是基于Map接口實(shí)現(xiàn)的一種鍵-值對<key,value>的存儲(chǔ)結(jié)構(gòu)，允許null值，同時(shí)非有序，非同步(即線程不安全)。HashMap的底層實(shí)現(xiàn)是數(shù)組 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分）。它存儲(chǔ)和查找數(shù)據(jù)時(shí)，是根據(jù)鍵key的hashCode的值計(jì)算出具體的存儲(chǔ)位置。HashMap最多只允許一條記錄的鍵key為null，HashMap增刪改查等常規(guī)操作都有不錯(cuò)的執(zhí)行效率，是ArrayList和LinkedList等數(shù)據(jù)結(jié)構(gòu)的一種折中實(shí)現(xiàn)。
示例代碼：
// 創(chuàng)建一個(gè)HashMap，如果沒有指定初始大小，默認(rèn)底層hash表數(shù)組的大小為16
HashMap<String, String> hashMap = new HashMap<String, String>();
// 往容器里面添加元素
hashMap.put("小明", "好帥");
hashMap.put("老王", "坑爹貨");
hashMap.put("老鐵", "沒毛病");
hashMap.put("掘金", "好地方");
hashMap.put("王五", "別搞事");
// 獲取key為小明的元素 好帥
String element = hashMap.get("小明");
// value : 好帥
System.out.println(element);
// 移除key為王五的元素
String removeElement = hashMap.remove("王五");
// value : 別搞事
System.out.println(removeElement);
// 修改key為小明的元素的值value 為 其實(shí)有點(diǎn)丑
hashMap.replace("小明", "其實(shí)有點(diǎn)丑");
// {老鐵=沒毛病, 小明=其實(shí)有點(diǎn)丑, 老王=坑爹貨, 掘金=好地方}
System.out.println(hashMap);
// 通過put方法也可以達(dá)到修改對應(yīng)元素的值的效果
hashMap.put("小明", "其實(shí)還可以啦,開玩笑的");
// {老鐵=沒毛病, 小明=其實(shí)還可以啦,開玩笑的, 老王=坑爹貨, 掘金=好地方}
System.out.println(hashMap);
// 判斷key為老王的元素是否存在(捉奸老王)
boolean isExist = hashMap.containsKey("老王");
// true , 老王竟然來搞事
System.out.println(isExist);
// 判斷是否有 value = "坑爹貨" 的人
boolean isHasSomeOne = hashMap.containsValue("坑爹貨");
// true 老王是坑爹貨
System.out.println(isHasSomeOne);
// 查看這個(gè)容器里面還有幾個(gè)家伙 value : 4
System.out.println(hashMap.size());
-
HashMap的底層實(shí)現(xiàn)是數(shù)組 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分），核心組成元素有：
int size;用于記錄HashMap實(shí)際存儲(chǔ)元素的個(gè)數(shù)；float loadFactor;負(fù)載因子（默認(rèn)是0.75，此屬性后面詳細(xì)解釋）。int threshold;下一次擴(kuò)容時(shí)的閾值，達(dá)到閾值便會(huì)觸發(fā)擴(kuò)容機(jī)制resize（閾值 threshold = 容器容量 capacity * 負(fù)載因子 load factor）。也就是說，在容器定義好容量之后，負(fù)載因子越大，所能容納的鍵值對元素個(gè)數(shù)就越多。Node<K,V>[] table;底層數(shù)組，充當(dāng)哈希表的作用，用于存儲(chǔ)對應(yīng)hash位置的元素Node<K,V>，此數(shù)組長度總是2的N次冪。（具體原因后面詳細(xì)解釋）
示例代碼：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
·····
/* ---------------- Fields -------------- */
/**
* 哈希表，在第一次使用到時(shí)進(jìn)行初始化，重置大小是必要的操作，
* 當(dāng)分配容量時(shí)，長度總是2的N次冪。
*/
transient Node<K,V>[] table;
/**
* 實(shí)際存儲(chǔ)的key - value 鍵值對 個(gè)數(shù)
*/
transient int size;
/**
* 下一次擴(kuò)容時(shí)的閾值
* (閾值 threshold = 容器容量 capacity * 負(fù)載因子 load factor).
* @serial
*/
int threshold;
/**
* 哈希表的負(fù)載因子
*
* @serial
*/
final float loadFactor;
·····
}
- 其中
Node<K,V>[] table;哈希表存儲(chǔ)的核心元素是Node<K,V>,Node<K,V>包含：
final int hash;元素的哈希值，決定元素存儲(chǔ)在Node<K,V>[] table;哈希表中的位置。由final修飾可知，當(dāng)hash的值確定后，就不能再修改。final K key;鍵，由final修飾可知，當(dāng)key的值確定后，就不能再修改。V value;值Node<K,V> next;記錄下一個(gè)元素結(jié)點(diǎn)(單鏈表結(jié)構(gòu)，用于解決hash沖突)
示例代碼：
/**
* 定義HashMap存儲(chǔ)元素結(jié)點(diǎn)的底層實(shí)現(xiàn)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//元素的哈希值 由final修飾可知，當(dāng)hash的值確定后，就不能再修改
final K key;// 鍵，由final修飾可知，當(dāng)key的值確定后，就不能再修改
V value; // 值
Node<K,V> next; // 記錄下一個(gè)元素結(jié)點(diǎn)(單鏈表結(jié)構(gòu)，用于解決hash沖突)
/**
* Node結(jié)點(diǎn)構(gòu)造方法
*/
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;//元素的哈希值
this.key = key;// 鍵
this.value = value; // 值
this.next = next;// 記錄下一個(gè)元素結(jié)點(diǎn)
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
/**
* 為Node重寫hashCode方法，值為：key的hashCode 異或 value的hashCode
* 運(yùn)算作用就是將2個(gè)hashCode的二進(jìn)制中，同一位置相同的值為0，不同的為1。
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 修改某一元素的值
*/
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* 為Node重寫equals方法
*/
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2.
問：您能說說HashMap常用操作的底層實(shí)現(xiàn)原理嗎？如存儲(chǔ)put(K key, V value)，查找get(Object key)，刪除remove(Object key)，修改replace(K key, V value)等操作。
答：
- 調(diào)用
put(K key, V value)操作添加key-value鍵值對時(shí)，進(jìn)行了如下操作：
判斷哈希表
Node<K,V>[] table是否為空或者null，是則執(zhí)行resize()方法進(jìn)行擴(kuò)容。根據(jù)插入的鍵值
key的hash值，通過(n - 1) & hash當(dāng)前元素的hash值 &hash表長度 - 1（實(shí)際就是hash值 %hash表長度） 計(jì)算出存儲(chǔ)位置table[i]。如果存儲(chǔ)位置沒有元素存放，則將新增結(jié)點(diǎn)存儲(chǔ)在此位置table[i]。如果存儲(chǔ)位置已經(jīng)有鍵值對元素存在，則判斷該位置元素的
hash值和key值是否和當(dāng)前操作元素一致，一致則證明是修改value操作，覆蓋value即可。當(dāng)前存儲(chǔ)位置即有元素，又不和當(dāng)前操作元素一致，則證明此位置
table[i]已經(jīng)發(fā)生了hash沖突，則通過判斷頭結(jié)點(diǎn)是否是treeNode，如果是treeNode則證明此位置的結(jié)構(gòu)是紅黑樹，已紅黑樹的方式新增結(jié)點(diǎn)。如果不是紅黑樹，則證明是單鏈表，將新增結(jié)點(diǎn)插入至鏈表的最后位置，隨后判斷當(dāng)前鏈表長度是否 大于等于 8，是則將當(dāng)前存儲(chǔ)位置的鏈表轉(zhuǎn)化為紅黑樹。遍歷過程中如果發(fā)現(xiàn)
key已經(jīng)存在，則直接覆蓋value。插入成功后，判斷當(dāng)前存儲(chǔ)鍵值對的數(shù)量 大于 閾值
threshold是則擴(kuò)容。
示例代碼：
/**
* 添加key-value鍵值對
*
* @param key 鍵
* @param value 值
* @return 如果原本存在此key，則返回舊的value值，如果是新增的key-
* value，則返回nulll
*/
public V put(K key, V value) {
//實(shí)際調(diào)用putVal方法進(jìn)行添加 key-value 鍵值對操作
return putVal(hash(key), key, value, false, true);
}
/**
* 根據(jù)key 鍵 的 hashCode 通過 “擾動(dòng)函數(shù)” 生成對應(yīng)的 hash值
* 經(jīng)過此操作后，使每一個(gè)key對應(yīng)的hash值生成的更均勻，
* 減少元素之間的碰撞幾率（后面詳細(xì)說明）
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 添加key-value鍵值對的實(shí)際調(diào)用方法（重點(diǎn)）
*
* @param hash key 鍵的hash值
* @param key 鍵
* @param value 值
* @param onlyIfAbsent 此值如果是true, 則如果此key已存在value，則不執(zhí)
* 行修改操作
* @param evict 此值如果是false，哈希表是在初始化模式
* @return 返回原本的舊值, 如果是新增，則返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 用于記錄當(dāng)前的hash表
Node<K,V>[] tab;
// 用于記錄當(dāng)前的鏈表結(jié)點(diǎn)
Node<K,V> p;
// n用于記錄hash表的長度，i用于記錄當(dāng)前操作索引index
int n, i;
// 當(dāng)前hash表為空
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化hash表，并把初始化后的hash表長度值賦值給n
n = (tab = resize()).length;
// 1）通過 (n - 1) & hash 當(dāng)前元素的hash值 & hash表長度 - 1
// 2）確定當(dāng)前元素的存儲(chǔ)位置，此運(yùn)算等價(jià)于 當(dāng)前元素的hash值 % hash表的長度
// 3）計(jì)算出的存儲(chǔ)位置沒有元素存在
if ((p = tab[i = (n - 1) & hash]) == null)
// 4) 則新建一個(gè)Node結(jié)點(diǎn)，在該位置存儲(chǔ)此元素
tab[i] = newNode(hash, key, value, null);
else { // 當(dāng)前存儲(chǔ)位置已經(jīng)有元素存在了(不考慮是修改的情況的話，就代表發(fā)生hash沖突了)
// 用于存放新增結(jié)點(diǎn)
Node<K,V> e;
// 用于臨時(shí)存在某個(gè)key值
K k;
// 1)如果當(dāng)前位置已存在元素的hash值和新增元素的hash值相等
// 2)并且key也相等，則證明是同一個(gè)key元素，想執(zhí)行修改value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 將當(dāng)前結(jié)點(diǎn)引用賦值給e
else if (p instanceof TreeNode) // 如果當(dāng)前結(jié)點(diǎn)是樹結(jié)點(diǎn)
// 則證明當(dāng)前位置的鏈表已變成紅黑樹結(jié)構(gòu)，則已紅黑樹結(jié)點(diǎn)結(jié)構(gòu)新增元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 排除上述情況，則證明已發(fā)生hash沖突，并hash沖突位置現(xiàn)時(shí)的結(jié)構(gòu)是單鏈表結(jié)構(gòu)
for (int binCount = 0; ; ++binCount) {
//遍歷單鏈表，將新元素結(jié)點(diǎn)放置此鏈表的最后一位
if ((e = p.next) == null) {
// 將新元素結(jié)點(diǎn)放在此鏈表的最后一位
p.next = newNode(hash, key, value, null);
// 新增結(jié)點(diǎn)后，當(dāng)前結(jié)點(diǎn)數(shù)量是否大于等于 閾值 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 大于等于8則將鏈表轉(zhuǎn)換成紅黑樹
treeifyBin(tab, hash);
break;
}
// 如果鏈表中已經(jīng)存在對應(yīng)的key，則覆蓋value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 已存在對應(yīng)key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //如果允許修改，則修改value為新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 當(dāng)前存儲(chǔ)鍵值對的數(shù)量 大于 閾值 是則擴(kuò)容
if (++size > threshold)
// 重置hash大小，將舊hash表的數(shù)據(jù)逐一復(fù)制到新的hash表中（后面詳細(xì)講解）
resize();
afterNodeInsertion(evict);
// 返回null，則證明是新增操作，而不是修改操作
return null;
}
- 調(diào)用
get(Object key)操作根據(jù)鍵key查找對應(yīng)的key-value鍵值對時(shí)，進(jìn)行了如下操作：
先調(diào)用
hash(key)方法計(jì)算出key的hash值根據(jù)查找的鍵值
key的hash值，通過(n - 1) & hash當(dāng)前元素的hash值 &hash表長度 - 1（實(shí)際就是hash值 %hash表長度） 計(jì)算出存儲(chǔ)位置table[i]，判斷存儲(chǔ)位置是否有元素存在 。
如果存儲(chǔ)位置有元素存放，則首先比較頭結(jié)點(diǎn)元素，如果頭結(jié)點(diǎn)的
key的hash值 和 要獲取的key的hash值相等，并且 頭結(jié)點(diǎn)的key本身 和要獲取的key相等，則返回該位置的頭結(jié)點(diǎn)。如果存儲(chǔ)位置沒有元素存放，則返回
null。
如果存儲(chǔ)位置有元素存放，但是頭結(jié)點(diǎn)元素不是要查找的元素，則需要遍歷該位置進(jìn)行查找。
先判斷頭結(jié)點(diǎn)是否是
treeNode，如果是treeNode則證明此位置的結(jié)構(gòu)是紅黑樹，以紅色樹的方式遍歷查找該結(jié)點(diǎn)，沒有則返回null。如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)的
key的hash值 和 要獲取的key的hash值相等，并且 鏈表結(jié)點(diǎn)的key本身 和要獲取的key相等，則返回該結(jié)點(diǎn)，遍歷結(jié)束仍未找到對應(yīng)key的結(jié)點(diǎn)，則返回null。
示例代碼：
/**
* 返回指定 key 所映射的 value 值
* 或者 返回 null 如果容器里不存在對應(yīng)的key
*
* 更確切地講，如果此映射包含一個(gè)滿足 (key==null ? k==null :key.equals(k))
* 的從 k 鍵到 v 值的映射關(guān)系，
* 則此方法返回 v；否則返回 null。（最多只能有一個(gè)這樣的映射關(guān)系。）
*
* 返回 null 值并不一定 表明該映射不包含該鍵的映射關(guān)系；
* 也可能該映射將該鍵顯示地映射為 null?？墒褂胏ontainsKey操作來區(qū)分這兩種情況。
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
// 1.先調(diào)用 hash(key)方法計(jì)算出 key 的 hash值
// 2.隨后調(diào)用getNode方法獲取對應(yīng)key所映射的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 獲取哈希表結(jié)點(diǎn)的方法實(shí)現(xiàn)
*
* @param hash key 鍵的hash值
* @param key 鍵
* @return 返回對應(yīng)的結(jié)點(diǎn)，如果結(jié)點(diǎn)不存在，則返回null
*/
final Node<K,V> getNode(int hash, Object key) {
// 用于記錄當(dāng)前的hash表
Node<K,V>[] tab;
// first用于記錄對應(yīng)hash位置的第一個(gè)結(jié)點(diǎn)，e充當(dāng)工作結(jié)點(diǎn)的作用
Node<K,V> first, e;
// n用于記錄hash表的長度
int n;
// 用于臨時(shí)存放Key
K k;
// 通過 (n - 1) & hash 當(dāng)前元素的hash值 & hash表長度 - 1
// 判斷當(dāng)前元素的存儲(chǔ)位置是否有元素存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//元素存在的情況
// 如果頭結(jié)點(diǎn)的key的hash值 和 要獲取的key的hash值相等
// 并且 頭結(jié)點(diǎn)的key本身 和要獲取的 key 相等
if (first.hash == hash && // always check first node 總是檢查頭結(jié)點(diǎn)
((k = first.key) == key || (key != null && key.equals(k))))
// 返回該位置的頭結(jié)點(diǎn)
return first;
if ((e = first.next) != null) {// 頭結(jié)點(diǎn)不相等
if (first instanceof TreeNode) // 如果當(dāng)前結(jié)點(diǎn)是樹結(jié)點(diǎn)
// 則證明當(dāng)前位置的鏈表已變成紅黑樹結(jié)構(gòu)
// 通過紅黑樹結(jié)點(diǎn)的方式獲取對應(yīng)key結(jié)點(diǎn)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {// 當(dāng)前位置不是紅黑樹，則證明是單鏈表
// 遍歷單鏈表，逐一比較鏈表結(jié)點(diǎn)
// 鏈表結(jié)點(diǎn)的key的hash值 和 要獲取的key的hash值相等
// 并且 鏈表結(jié)點(diǎn)的key本身 和要獲取的 key 相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 找到對應(yīng)的結(jié)點(diǎn)則返回
return e;
} while ((e = e.next) != null);
}
}
// 通過上述查找均無找到，則返回null
return null;
}
- 調(diào)用
remove(Object key)操作根據(jù)鍵key刪除對應(yīng)的key-value鍵值對時(shí)，進(jìn)行了如下操作：
先調(diào)用
hash(key)方法計(jì)算出key的hash值根據(jù)查找的鍵值
key的hash值，通過(n - 1) & hash當(dāng)前元素的hash值 &hash表長度 - 1（實(shí)際就是hash值 %hash表長度） 計(jì)算出存儲(chǔ)位置table[i]，判斷存儲(chǔ)位置是否有元素存在 。
如果存儲(chǔ)位置有元素存放，則首先比較頭結(jié)點(diǎn)元素，如果頭結(jié)點(diǎn)的
key的hash值 和 要獲取的key的hash值相等，并且 頭結(jié)點(diǎn)的key本身 和要獲取的key相等，則該位置的頭結(jié)點(diǎn)即為要?jiǎng)h除的結(jié)點(diǎn)，記錄此結(jié)點(diǎn)至變量node中。如果存儲(chǔ)位置沒有元素存放，則沒有找到對應(yīng)要?jiǎng)h除的結(jié)點(diǎn)，則返回
null。
如果存儲(chǔ)位置有元素存放，但是頭結(jié)點(diǎn)元素不是要?jiǎng)h除的元素，則需要遍歷該位置進(jìn)行查找。
先判斷頭結(jié)點(diǎn)是否是
treeNode，如果是treeNode則證明此位置的結(jié)構(gòu)是紅黑樹，以紅色樹的方式遍歷查找并刪除該結(jié)點(diǎn)，沒有則返回null。如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)的
key的hash值 和 要獲取的key的hash值相等，并且 鏈表結(jié)點(diǎn)的key本身 和要獲取的key相等，則此為要?jiǎng)h除的結(jié)點(diǎn)，記錄此結(jié)點(diǎn)至變量node中，遍歷結(jié)束仍未找到對應(yīng)key的結(jié)點(diǎn)，則返回null。如果找到要?jiǎng)h除的結(jié)點(diǎn)
node，則判斷是否需要比較value也是否一致，如果value值一致或者不需要比較value值，則執(zhí)行刪除結(jié)點(diǎn)操作，刪除操作根據(jù)不同的情況與結(jié)構(gòu)進(jìn)行不同的處理。
如果當(dāng)前結(jié)點(diǎn)是樹結(jié)點(diǎn)，則證明當(dāng)前位置的鏈表已變成紅黑樹結(jié)構(gòu)，通過紅黑樹結(jié)點(diǎn)的方式刪除對應(yīng)結(jié)點(diǎn)。
如果不是紅黑樹，則證明是單鏈表。如果要?jiǎng)h除的是頭結(jié)點(diǎn)，則當(dāng)前存儲(chǔ)位置
table[i]的頭結(jié)點(diǎn)指向刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。如果要?jiǎng)h除的結(jié)點(diǎn)不是頭結(jié)點(diǎn)，則將要?jiǎng)h除的結(jié)點(diǎn)的后繼結(jié)點(diǎn)
node.next賦值給要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next域，即p.next = node.next;。
-
HashMap當(dāng)前存儲(chǔ)鍵值對的數(shù)量 - 1，并返回刪除結(jié)點(diǎn)。
示例代碼：
/**
* 從此映射中移除指定鍵的映射關(guān)系（如果存在）。
*
* @param key 其映射關(guān)系要從映射中移除的鍵
* @return 與 key 關(guān)聯(lián)的舊值；如果 key 沒有任何映射關(guān)系，則返回 null。
* （返回 null 還可能表示該映射之前將 null 與 key 關(guān)聯(lián)。）
*/
public V remove(Object key) {
Node<K,V> e;
// 1.先調(diào)用 hash(key)方法計(jì)算出 key 的 hash值
// 2.隨后調(diào)用removeNode方法刪除對應(yīng)key所映射的結(jié)點(diǎn)
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 刪除哈希表結(jié)點(diǎn)的方法實(shí)現(xiàn)
*
* @param hash 鍵的hash值
* @param key 鍵
* @param value 用于比較的value值，當(dāng)matchValue 是 true時(shí)才有效, 否則忽略
* @param matchValue 如果是 true 只有當(dāng)value相等時(shí)才會(huì)移除
* @param movable 如果是 false當(dāng)執(zhí)行移除操作時(shí)，不刪除其他結(jié)點(diǎn)
* @return 返回刪除結(jié)點(diǎn)node，不存在則返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 用于記錄當(dāng)前的hash表
Node<K,V>[] tab;
// 用于記錄當(dāng)前的鏈表結(jié)點(diǎn)
Node<K,V> p;
// n用于記錄hash表的長度，index用于記錄當(dāng)前操作索引index
int n, index;
// 通過 (n - 1) & hash 當(dāng)前元素的hash值 & hash表長度 - 1
// 判斷當(dāng)前元素的存儲(chǔ)位置是否有元素存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {// 元素存在的情況
// node 用于記錄找到的結(jié)點(diǎn)，e為工作結(jié)點(diǎn)
Node<K,V> node = null, e;
K k; V v;
// 如果頭結(jié)點(diǎn)的key的hash值 和 要獲取的key的hash值相等
// 并且 頭結(jié)點(diǎn)的key本身 和要獲取的 key 相等
// 則證明此頭結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 記錄要?jiǎng)h除的結(jié)點(diǎn)的引用地址至node中
node = p;
else if ((e = p.next) != null) {// 頭結(jié)點(diǎn)不相等
if (p instanceof TreeNode)// 如果當(dāng)前結(jié)點(diǎn)是樹結(jié)點(diǎn)
// 則證明當(dāng)前位置的鏈表已變成紅黑樹結(jié)構(gòu)
// 通過紅黑樹結(jié)點(diǎn)的方式獲取對應(yīng)key結(jié)點(diǎn)
// 記錄要?jiǎng)h除的結(jié)點(diǎn)的引用地址至node中
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {// 當(dāng)前位置不是紅黑樹，則證明是單鏈表
do {
// 遍歷單鏈表，逐一比較鏈表結(jié)點(diǎn)
// 鏈表結(jié)點(diǎn)的key的hash值 和 要獲取的key的hash值相等
// 并且 鏈表結(jié)點(diǎn)的key本身 和要獲取的 key 相等
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
// 找到則記錄要?jiǎng)h除的結(jié)點(diǎn)的引用地址至node中，中斷遍歷
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 如果找到要?jiǎng)h除的結(jié)點(diǎn)，則判斷是否需要比較value也是否一致
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// value值一致或者不需要比較value值，則執(zhí)行刪除結(jié)點(diǎn)操作
if (node instanceof TreeNode) // 如果當(dāng)前結(jié)點(diǎn)是樹結(jié)點(diǎn)
// 則證明當(dāng)前位置的鏈表已變成紅黑樹結(jié)構(gòu)
// 通過紅黑樹結(jié)點(diǎn)的方式刪除對應(yīng)結(jié)點(diǎn)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // node 和 p相等，則證明刪除的是頭結(jié)點(diǎn)
// 當(dāng)前存儲(chǔ)位置的頭結(jié)點(diǎn)指向刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
tab[index] = node.next;
else // 刪除的不是頭結(jié)點(diǎn)
// p是刪除結(jié)點(diǎn)node的前驅(qū)結(jié)點(diǎn)，p的next改為記錄要?jiǎng)h除結(jié)點(diǎn)node的后繼結(jié)點(diǎn)
p.next = node.next;
++modCount;
// 當(dāng)前存儲(chǔ)鍵值對的數(shù)量 - 1
--size;
afterNodeRemoval(node);
// 返回刪除結(jié)點(diǎn)
return node;
}
}
// 不存在要?jiǎng)h除的結(jié)點(diǎn)，則返回null
return null;
}
- 調(diào)用
replace(K key, V value)操作根據(jù)鍵key查找對應(yīng)的key-value鍵值對，隨后替換對應(yīng)的值value，進(jìn)行了如下操作：
先調(diào)用
hash(key)方法計(jì)算出key的hash值隨后調(diào)用
getNode方法獲取對應(yīng)key所映射的value值 。記錄元素舊值，將新值賦值給元素，返回元素舊值，如果沒有找到元素，則返回
null。
示例代碼：
/**
* 替換指定 key 所映射的 value 值
*
* @param key 對應(yīng)要替換value值元素的key鍵
* @param value 要替換對應(yīng)元素的新value值
* @return 返回原本的舊值，如果沒有找到key對應(yīng)的元素，則返回null
* @since 1.8 JDK1.8新增方法
*/
public V replace(K key, V value) {
Node<K,V> e;
// 1.先調(diào)用 hash(key)方法計(jì)算出 key 的 hash值
// 2.隨后調(diào)用getNode方法獲取對應(yīng)key所映射的value值
if ((e = getNode(hash(key), key)) != null) {// 如果找到對應(yīng)的元素
// 元素舊值
V oldValue = e.value;
// 將新值賦值給元素
e.value = value;
afterNodeAccess(e);
// 返回元素舊值
return oldValue;
}
// 沒有找到元素，則返回null
return null;
}
3.
問 1：您上面說，存放一個(gè)元素時(shí)，先計(jì)算它的hash值確定它的存儲(chǔ)位置，然后再把這個(gè)元素放到對應(yīng)的位置上，那萬一這個(gè)位置上面已經(jīng)有元素存在呢，新增的這個(gè)元素怎么辦？
問 2：hash沖突（或者叫hash碰撞）是什么？為什么會(huì)出現(xiàn)這種現(xiàn)象，如何解決hash沖突？
答：
hash沖突： 當(dāng)我們調(diào)用put(K key, V value)操作添加key-value鍵值對，這個(gè)key-value鍵值對存放在的位置是通過擾動(dòng)函數(shù)(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)計(jì)算鍵key的hash值。隨后將 這個(gè)hash值 % 模上 哈希表Node<K,V>[] table的長度 得到具體的存放位置。所以put(K key, V value)多個(gè)元素，是有可能計(jì)算出相同的存放位置。此現(xiàn)象就是hash沖突或者叫hash碰撞。例子如下：
元素 A 的hash值 為 9，元素 B 的hash值 為 17。哈希表Node<K,V>[] table的長度為8。則元素 A 的存放位置為9 % 8 = 1，元素 B 的存放位置為17 % 8 = 1。兩個(gè)元素的存放位置均為table[1]，發(fā)生了hash沖突。hash沖突的避免：既然會(huì)發(fā)生hash沖突，我們就應(yīng)該想辦法避免此現(xiàn)象的發(fā)生，解決這個(gè)問題最關(guān)鍵就是如果生成元素的hash值。Java是使用“擾動(dòng)函數(shù)”生成元素的hash值。
示例代碼：
/**
* JDK 7 的 hash方法
*/
final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* JDK 8 的 hash方法
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Java7做了4次16位右位移異或混合，Java 8中這步已經(jīng)簡化了，只做一次16位右位移異或混合，而不是四次，但原理是不變的。例子如下：
右位移16位，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
上述擾動(dòng)函數(shù)的解釋參考自：JDK 源碼中 HashMap 的 hash 方法原理是什么？
-
hash沖突解決：解決hash沖突的方法有很多，常見的有：開發(fā)定址法，
再散列法，鏈地址法，公共溢出區(qū)法（詳細(xì)說明請查看我的文章JAVA基礎(chǔ)-自問自答學(xué)hashCode和equals）。HashMap是使用鏈地址法解決hash沖突的，當(dāng)有沖突元素放進(jìn)來時(shí)，會(huì)將此元素插入至此位置鏈表的最后一位，形成單鏈表。但是由于是單鏈表的緣故，每當(dāng)通過hash % length找到該位置的元素時(shí)，均需要從頭遍歷鏈表，通過逐一比較hash值，找到對應(yīng)元素。如果此位置元素過多，造成鏈表過長，遍歷時(shí)間會(huì)大大增加，最壞情況下的時(shí)間復(fù)雜度為O(N)，造成查找效率過低。所以當(dāng)存在位置的鏈表長度 大于等于 8 時(shí)，HashMap會(huì)將鏈表 轉(zhuǎn)變?yōu)?紅黑樹，紅黑樹最壞情況下的時(shí)間復(fù)雜度為O(logn)。以此提高查找效率。
4.
問：HashMap的容量為什么一定要是2的n次方？
答：
因?yàn)檎{(diào)用
put(K key, V value)操作添加key-value鍵值對時(shí)，具體確定此元素的位置是通過hash值 % 模上 哈希表Node<K,V>[] table的長度hash % length計(jì)算的。但是"模"運(yùn)算的消耗相對較大，通過位運(yùn)算h & (length-1)也可以得到取模后的存放位置，而位運(yùn)算的運(yùn)行效率高，但只有length的長度是2的n次方時(shí)，h & (length-1)才等價(jià)于h % length。而且當(dāng)數(shù)組長度為2的n次冪的時(shí)候，不同的key算出的index相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時(shí)候就不用遍歷某個(gè)位置上的鏈表，這樣查詢效率也就較高了。
例子：
上圖中，左邊兩組的數(shù)組長度是16（2的4次方），右邊兩組的數(shù)組長度是15。兩組的
hash值均為8和9。當(dāng)數(shù)組長度是15時(shí)，當(dāng)它們和
1110進(jìn)行&與運(yùn)算（相同為1，不同為0）時(shí)，計(jì)算的結(jié)果都是1000，所以他們都會(huì)存放在相同的位置table[8]中，這樣就發(fā)生了hash沖突，那么查詢時(shí)就要遍歷鏈表，逐一比較hash值，降低了查詢的效率。同時(shí)，我們可以發(fā)現(xiàn)，當(dāng)數(shù)組長度為15的時(shí)候，
hash值均會(huì)與14（1110）進(jìn)行&與運(yùn)算，那么最后一位永遠(yuǎn)是0，而0001，0011，0101，1001，1011，0111，1101這幾個(gè)位置永遠(yuǎn)都不能存放元素了，空間浪費(fèi)相當(dāng)大，更糟的是這種情況中，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進(jìn)一步增加了碰撞的幾率，減慢了查詢的效率。
- 所以，
HashMap的容量是2的n次方，有利于提高計(jì)算元素存放位置時(shí)的效率，也降低了hash沖突的幾率。因此，我們使用HashMap存儲(chǔ)大量數(shù)據(jù)的時(shí)候，最好先預(yù)先指定容器的大小為2的n次方，即使我們不指定為2的n次方，HashMap也會(huì)把容器的大小設(shè)置成最接近設(shè)置數(shù)的2的n次方，如，設(shè)置HashMap的大小為 7 ，則HashMap會(huì)將容器大小設(shè)置成最接近7的一個(gè)2的n次方數(shù)，此值為 8 。
上述回答參考自：深入理解HashMap
示例代碼：
/**
* 返回一個(gè)比指定數(shù)cap大的，并且大小是2的n次方的數(shù)
* Returns a power of two size for the given target capacity.
*/
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;
}
5.
問：HashMap的負(fù)載因子是什么，有什么作用？
答：負(fù)載因子表示哈希表空間的使用程度（或者說是哈希表空間的利用率）。
例子如下：
底層哈希表Node<K,V>[] table的容量大小capacity為 16，負(fù)載因子load factor為 0.75，則當(dāng)存儲(chǔ)的元素個(gè)數(shù)size = capacity 16 * load factor 0.75等于 12 時(shí)，則會(huì)觸發(fā)HashMap的擴(kuò)容機(jī)制，調(diào)用resize()方法進(jìn)行擴(kuò)容。當(dāng)負(fù)載因子越大，則
HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發(fā)生hash碰撞的幾率就會(huì)加大，從而鏈表就會(huì)拉長，此時(shí)的查詢效率就會(huì)降低。當(dāng)負(fù)載因子越小，則鏈表中的數(shù)據(jù)量就越稀疏，此時(shí)會(huì)對空間造成浪費(fèi)，但是此時(shí)查詢效率高。
我們可以在創(chuàng)建
HashMap時(shí)根據(jù)實(shí)際需要適當(dāng)?shù)卣{(diào)整load factor的值；如果程序比較關(guān)心空間開銷、內(nèi)存比較緊張，可以適當(dāng)?shù)卦黾迂?fù)載因子；如果程序比較關(guān)心時(shí)間開銷，內(nèi)存比較寬裕則可以適當(dāng)?shù)臏p少負(fù)載因子。通常情況下，默認(rèn)負(fù)載因子 (0.75) 在時(shí)間和空間成本上尋求一種折衷，程序員無需改變負(fù)載因子的值。因此，如果我們在初始化
HashMap時(shí)，就預(yù)估知道需要裝載key-value鍵值對的容量size，我們可以通過size / load factor計(jì)算出我們需要初始化的容量大小initialCapacity，這樣就可以避免HashMap因?yàn)榇娣诺脑剡_(dá)到閾值threshold而頻繁調(diào)用resize()方法進(jìn)行擴(kuò)容。從而保證了較好的性能。
6.
問：您能說說HashMap和HashTable的區(qū)別嗎？
答：HashMap和HashTable有如下區(qū)別：
1）容器整體結(jié)構(gòu)：
HashMap的key和value都允許為null，HashMap遇到key為null的時(shí)候，調(diào)用putForNullKey方法進(jìn)行處理，而對value沒有處理。Hashtable的key和value都不允許為null。Hashtable遇到null，直接返回NullPointerException。
2） 容量設(shè)定與擴(kuò)容機(jī)制：
HashMap默認(rèn)初始化容量為 16，并且容器容量一定是2的n次方，擴(kuò)容時(shí)，是以原容量 2倍 的方式 進(jìn)行擴(kuò)容。Hashtable默認(rèn)初始化容量為 11，擴(kuò)容時(shí)，是以原容量 2倍 再加 1的方式進(jìn)行擴(kuò)容。即int newCapacity = (oldCapacity << 1) + 1;。
3） 散列分布方式（計(jì)算存儲(chǔ)位置）：
HashMap是先將key鍵的hashCode經(jīng)過擾動(dòng)函數(shù)擾動(dòng)后得到hash值，然后再利用hash & (length - 1)的方式代替取模，得到元素的存儲(chǔ)位置。Hashtable則是除留余數(shù)法進(jìn)行計(jì)算存儲(chǔ)位置的（因?yàn)槠淠J(rèn)容量也不是2的n次方。所以也無法用位運(yùn)算替代模運(yùn)算），int index = (hash & 0x7FFFFFFF) % tab.length;。由于
HashMap的容器容量一定是2的n次方，所以能使用hash & (length - 1)的方式代替取模的方式計(jì)算元素的位置提高運(yùn)算效率，但Hashtable的容器容量不一定是2的n次方，所以不能使用此運(yùn)算方式代替。
4）線程安全（最重要）：
HashMap不是線程安全，如果想線程安全，可以通過調(diào)用synchronizedMap(Map<K,V> m)使其線程安全。但是使用時(shí)的運(yùn)行效率會(huì)下降，所以建議使用ConcurrentHashMap容器以此達(dá)到線程安全。Hashtable則是線程安全的，每個(gè)操作方法前都有synchronized修飾使其同步，但運(yùn)行效率也不高，所以還是建議使用ConcurrentHashMap容器以此達(dá)到線程安全。
因此，Hashtable是一個(gè)遺留容器，如果我們不需要線程同步，則建議使用HashMap，如果需要線程同步，則建議使用ConcurrentHashMap。
此處不再對Hashtable的源碼進(jìn)行逐一分析了，如果想深入了解的同學(xué)，可以參考此文章
Hashtable源碼剖析
7.
問：您說HashMap不是線程安全的，那如果多線程下，它是如何處理的？并且什么情況下會(huì)發(fā)生線程不安全的情況？
答：
HashMap不是線程安全的，如果多個(gè)線程同時(shí)對同一個(gè)HashMap更改數(shù)據(jù)的話，會(huì)導(dǎo)致數(shù)據(jù)不一致或者數(shù)據(jù)污染。如果出現(xiàn)線程不安全的操作時(shí)，HashMap會(huì)盡可能的拋出ConcurrentModificationException防止數(shù)據(jù)異常，當(dāng)我們在對一個(gè)HashMap進(jìn)行遍歷時(shí)，在遍歷期間，我們是不能對HashMap進(jìn)行添加，刪除等更改數(shù)據(jù)的操作的，否則也會(huì)拋出ConcurrentModificationException異常，此為fail-fast（快速失敗）機(jī)制。從源碼上分析，我們在put,remove等更改HashMap數(shù)據(jù)時(shí)，都會(huì)導(dǎo)致modCount的改變，當(dāng)expectedModCount != modCount時(shí)，則拋出ConcurrentModificationException。如果想要線程安全，可以考慮使用ConcurrentHashMap。而且，在多線程下操作
HashMap，由于存在擴(kuò)容機(jī)制，當(dāng)HashMap調(diào)用resize()進(jìn)行自動(dòng)擴(kuò)容時(shí)，可能會(huì)導(dǎo)致死循環(huán)的發(fā)生。
由于時(shí)間關(guān)系，我暫不帶著大家一起去分析resize()方法導(dǎo)致死循環(huán)發(fā)生的現(xiàn)象造成原因了，遲點(diǎn)有空我會(huì)再補(bǔ)充上去，請見諒，大家可以參考如下文章：
Java 8系列之重新認(rèn)識(shí)HashMap
8.
問：我們在使用HashMap時(shí)，選取什么對象作為key鍵比較好，為什么？
答：
可變對象：指創(chuàng)建后自身狀態(tài)能改變的對象。換句話說，可變對象是該對象在創(chuàng)建后它的哈希值可能被改變。
我們在使用
HashMap時(shí)，最好選擇不可變對象作為key。例如String，Integer等不可變類型作為key是非常明智的。如果
key對象是可變的，那么key的哈希值就可能改變。在HashMap中可變對象作為Key會(huì)造成數(shù)據(jù)丟失。因?yàn)槲覀冊龠M(jìn)行hash & (length - 1)取模運(yùn)算計(jì)算位置查找對應(yīng)元素時(shí)，位置可能已經(jīng)發(fā)生改變，導(dǎo)致數(shù)據(jù)丟失。
詳細(xì)例子說明請參考：危險(xiǎn)！在HashMap中將可變對象用作Key
總結(jié)
HashMap是基于Map接口實(shí)現(xiàn)的一種鍵-值對<key,value>的存儲(chǔ)結(jié)構(gòu)，允許null值，同時(shí)非有序，非同步(即線程不安全)。HashMap的底層實(shí)現(xiàn)是數(shù)組 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分）。HashMap定位元素位置是通過鍵key經(jīng)過擾動(dòng)函數(shù)擾動(dòng)后得到hash值，然后再通過hash & (length - 1)代替取模的方式進(jìn)行元素定位的。HashMap是使用鏈地址法解決hash沖突的，當(dāng)有沖突元素放進(jìn)來時(shí)，會(huì)將此元素插入至此位置鏈表的最后一位，形成單鏈表。當(dāng)存在位置的鏈表長度 大于等于 8 時(shí)，HashMap會(huì)將鏈表 轉(zhuǎn)變?yōu)?紅黑樹，以此提高查找效率。HashMap的容量是2的n次方，有利于提高計(jì)算元素存放位置時(shí)的效率，也降低了hash沖突的幾率。因此，我們使用HashMap存儲(chǔ)大量數(shù)據(jù)的時(shí)候，最好先預(yù)先指定容器的大小為2的n次方，即使我們不指定為2的n次方，HashMap也會(huì)把容器的大小設(shè)置成最接近設(shè)置數(shù)的2的n次方，如，設(shè)置HashMap的大小為 7 ，則HashMap會(huì)將容器大小設(shè)置成最接近7的一個(gè)2的n次方數(shù)，此值為 8 。HashMap的負(fù)載因子表示哈希表空間的使用程度（或者說是哈希表空間的利用率）。當(dāng)負(fù)載因子越大，則HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發(fā)生hash碰撞的幾率就會(huì)加大，從而鏈表就會(huì)拉長，此時(shí)的查詢效率就會(huì)降低。當(dāng)負(fù)載因子越小，則鏈表中的數(shù)據(jù)量就越稀疏，此時(shí)會(huì)對空間造成浪費(fèi)，但是此時(shí)查詢效率高。HashMap不是線程安全的，Hashtable則是線程安全的。但Hashtable是一個(gè)遺留容器，如果我們不需要線程同步，則建議使用HashMap，如果需要線程同步，則建議使用ConcurrentHashMap。在多線程下操作
HashMap，由于存在擴(kuò)容機(jī)制，當(dāng)HashMap調(diào)用resize()進(jìn)行自動(dòng)擴(kuò)容時(shí)，可能會(huì)導(dǎo)致死循環(huán)的發(fā)生。我們在使用
HashMap時(shí)，最好選擇不可變對象作為key。例如String，Integer等不可變類型作為key是非常明智的。
- 由于最近工作較忙，也有拖延癥發(fā)作的問題，所以文章遲遲未能完成發(fā)布，現(xiàn)時(shí)完成的文章其實(shí)對我而言，也不算太好，但還是打算先發(fā)出來讓大家看看，一起學(xué)習(xí)學(xué)習(xí)，看有什么不好的地方，我再慢慢改進(jìn)，如果此文對你有幫助，請給個(gè)贊，謝謝大家。
參考文章
Java 8系列之重新認(rèn)識(shí)HashMap
JDK 源碼中 HashMap 的 hash 方法原理是什么？
深入理解HashMap
HashMap負(fù)載因子
Hashtable源碼剖析
危險(xiǎn)！在HashMap中將可變對象用作Key
談?wù)凥ashMap線程不安全的體現(xiàn)
