HashMap 是 Java 面試必考的知識(shí)點(diǎn)，面試官?gòu)倪@個(gè)小知識(shí)點(diǎn)就可以了解我們對(duì) Java 基礎(chǔ)的掌握程度映企。網(wǎng)上的源碼分析總結(jié)太多太多了，現(xiàn)飯炒了三遍也還是要吃的，所以我在這里做一些整理和總結(jié)分享給大家要拂，也便于自己為明年實(shí)習(xí)生面試做準(zhǔn)備。
HashMap 簡(jiǎn)介
一句話概括之：HashMap 是一個(gè)散列表站楚，它存儲(chǔ)的內(nèi)容是鍵值對(duì) (key-value) 映射脱惰。
它根據(jù)鍵的 hashCode 值存儲(chǔ)數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值窿春，因而具有很快的訪問(wèn)速度拉一，但遍歷順序卻是不確定的。
HashMap 最多只允許一條記錄的鍵為 null旧乞，允許多條記錄的值為 null蔚润。
HashMap 使用 hash 算法進(jìn)行數(shù)據(jù)的存儲(chǔ)和查詢(xún)。
內(nèi)部使用一個(gè) Entry 表示鍵值對(duì) key-value尺栖。
用 Entry 的數(shù)組保存所有鍵值對(duì), Entry 通過(guò)鏈表的方式鏈接后續(xù)的節(jié)點(diǎn) (1.8 后會(huì)根據(jù)鏈表長(zhǎng)度決定是否轉(zhuǎn)換成一棵樹(shù)類(lèi)似 TreeMap 來(lái)節(jié)省查詢(xún)時(shí)間) Entry 通過(guò)計(jì)算 key 的 hash 值來(lái)決定映射到具體的哪個(gè)數(shù)組（也叫 Bucket) 中嫡纠。
HashMap 非線程安全，即任一時(shí)刻可以有多個(gè)線程同時(shí)寫(xiě) HashMap延赌，可能會(huì)導(dǎo)致數(shù)據(jù)的不一致除盏。如果需要滿(mǎn)足線程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有線程安全的能力挫以，或者使用 ConcurrentHashMap者蠕。
HashMap 特性
- Hash 相關(guān)的數(shù)據(jù)結(jié)構(gòu)本質(zhì)上都是 key value pair
- Hash 中不能存在 duplicate key
- HashMap 提供非常快速查找時(shí)間復(fù)雜度
- HashMap 具體實(shí)現(xiàn)中掐松，null 可以作為 key 或者 value 存在
- HashMap 不是線程安全
HashMap 實(shí)現(xiàn)
HashMap 1.7 版本
HashMap 1.8 版本
存儲(chǔ)結(jié)構(gòu)
從結(jié)構(gòu)實(shí)現(xiàn)來(lái)講蠢棱，HashMap 是數(shù)組 + 鏈表 + 紅黑樹(shù)（JDK1.8 增加了紅黑樹(shù)部分）實(shí)現(xiàn)的锌杀。
HashMap 常量定義：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/**
* HashMap 的默認(rèn)初始容量為 16，必須為 2 的 n 次方 (一定是合數(shù))
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* HashMap 的最大容量為 2 的 30 次冪
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* HashMap 的默認(rèn)負(fù)載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表轉(zhuǎn)成紅黑樹(shù)的閾值泻仙。即在哈希表擴(kuò)容時(shí)糕再，當(dāng)鏈表的長(zhǎng)度(桶中元素個(gè)數(shù))超過(guò)這個(gè)值的時(shí)候，進(jìn)行鏈表到紅黑樹(shù)的轉(zhuǎn)變
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 紅黑樹(shù)轉(zhuǎn)為鏈表的閾值玉转。即在哈希表擴(kuò)容時(shí)突想，如果發(fā)現(xiàn)鏈表長(zhǎng)度(桶中元素個(gè)數(shù))小于 6，則會(huì)由紅黑樹(shù)重新退化為鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* HashMap 的最小樹(shù)形化容量究抓。這個(gè)值的意義是：位桶（bin）處的數(shù)據(jù)要采用紅黑樹(shù)結(jié)構(gòu)進(jìn)行存儲(chǔ)時(shí)猾担，整個(gè)Table的最小容量（存儲(chǔ)方式由鏈表轉(zhuǎn)成紅黑樹(shù)的容量的最小閾值）
* 當(dāng)哈希表中的容量大于這個(gè)值時(shí)，表中的桶才能進(jìn)行樹(shù)形化刺下，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容绑嘹，而不是樹(shù)形化
* 為了避免進(jìn)行擴(kuò)容、樹(shù)形化選擇的沖突橘茉，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Node 是 HashMap 的一個(gè)內(nèi)部類(lèi)工腋，實(shí)現(xiàn)了 Map.Entry 接口，本質(zhì)是就是一個(gè)映射 (鍵值對(duì))
* Basic hash bin node, used for most entries.
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 用來(lái)定位數(shù)組索引位置
final K key;
V value;
Node<K,V> next; // 鏈表的下一個(gè)node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey() { ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
/**
* 哈希桶數(shù)組畅卓，分配的時(shí)候擅腰，table的長(zhǎng)度總是2的冪
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* HashMap 中實(shí)際存儲(chǔ)的 key-value 鍵值對(duì)數(shù)量
*/
transient int size;
/**
* 用來(lái)記錄 HashMap 內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，主要用于迭代的快速失敗機(jī)制
*/
transient int modCount;
/**
* HashMap 的門(mén)限閥值/擴(kuò)容閾值翁潘，所能容納的 key-value 鍵值對(duì)極限趁冈，當(dāng)size>=threshold時(shí)，就會(huì)擴(kuò)容
* 計(jì)算方法：容量capacity * 負(fù)載因子load factor
*/
int threshold;
/**
* HashMap 的負(fù)載因子
*/
final float loadFactor;
}
Node[] table 的初始化長(zhǎng)度 length(默認(rèn)值是 16)拜马，loadFactor 為負(fù)載因子 (默認(rèn)值 DEFAULT_LOAD_FACTOR 是 0.75)渗勘，threshold 是 HashMap 所能容納的最大數(shù)據(jù)量的 Node(鍵值對(duì)) 個(gè)數(shù)。
threshold = length * loadFactor俩莽。也就是說(shuō)旺坠，在數(shù)組定義好長(zhǎng)度之后，負(fù)載因子越大豹绪，所能容納的鍵值對(duì)個(gè)數(shù)越多价淌。
這里我們需要加載因子 (load_factor)，加載因子默認(rèn)為 0.75瞒津，當(dāng) HashMap 中存儲(chǔ)的元素的數(shù)量大于 (容量 × 加載因子)蝉衣，也就是默認(rèn)大于 16*0.75=12 時(shí)，HashMap 會(huì)進(jìn)行擴(kuò)容的操作巷蚪。
size 這個(gè)字段其實(shí)很好理解病毡，就是 HashMap 中實(shí)際存在的鍵值對(duì)數(shù)量。注意和 table 的長(zhǎng)度 length屁柏、容納最大鍵值對(duì)數(shù)量 threshold 的區(qū)別啦膜。而 modCount 字段主要用來(lái)記錄 HashMap 內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)有送，主要用于迭代的快速失敗。強(qiáng)調(diào)一點(diǎn)僧家，內(nèi)部結(jié)構(gòu)發(fā)生變化指的是結(jié)構(gòu)發(fā)生變化雀摘，例如 put 新鍵值對(duì)，但是某個(gè) key 對(duì)應(yīng)的 value 值被覆蓋不屬于結(jié)構(gòu)變化八拱。
在 HashMap 中阵赠，哈希桶數(shù)組 table 的長(zhǎng)度 length 大小必須為 2 的 n 次方 (一定是合數(shù))，這是一種非常規(guī)的設(shè)計(jì)肌稻，常規(guī)的設(shè)計(jì)是把桶的大小設(shè)計(jì)為素?cái)?shù)清蚀。相對(duì)來(lái)說(shuō)素?cái)?shù)導(dǎo)致沖突的概率要小于合數(shù)，具體證明可以參考 http://blog.csdn.net/liuqiyao_01/article/details/14475159爹谭，Hashtable 初始化桶大小為 11枷邪，就是桶大小設(shè)計(jì)為素?cái)?shù)的應(yīng)用（Hashtable 擴(kuò)容后不能保證還是素?cái)?shù)）。HashMap 采用這種非常規(guī)設(shè)計(jì)诺凡，主要是為了在取模和擴(kuò)容時(shí)做優(yōu)化东揣，同時(shí)為了減少?zèng)_突，HashMap 定位哈希桶索引位置時(shí)绑洛，也加入了高位參與運(yùn)算的過(guò)程救斑。
這里存在一個(gè)問(wèn)題童本，即使負(fù)載因子和 Hash 算法設(shè)計(jì)的再合理真屯，也免不了會(huì)出現(xiàn)拉鏈過(guò)長(zhǎng)的情況，一旦出現(xiàn)拉鏈過(guò)長(zhǎng)穷娱，則會(huì)嚴(yán)重影響 HashMap 的性能绑蔫。于是，在 JDK1.8 版本中泵额，對(duì)數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化配深，引入了紅黑樹(shù)。而當(dāng)鏈表長(zhǎng)度太長(zhǎng)（默認(rèn)超過(guò) 8）時(shí)嫁盲，鏈表就轉(zhuǎn)換為紅黑樹(shù)篓叶，利用紅黑樹(shù)快速增刪改查的特點(diǎn)提高 HashMap 的性能，其中會(huì)用到紅黑樹(shù)的插入羞秤、刪除缸托、查找等算法。本文不再對(duì)紅黑樹(shù)展開(kāi)討論瘾蛋，想了解更多紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)的工作原理可以參考：http://blog.csdn.net/v_july_v/article/details/6105630。
功能實(shí)現(xiàn)
HashMap 的內(nèi)部功能實(shí)現(xiàn)很多，本文主要從根據(jù) key 獲取哈希桶數(shù)組索引位置凭戴、put 方法的詳細(xì)執(zhí)行、擴(kuò)容過(guò)程等具有代表性的點(diǎn)深入展開(kāi)講解叼风。
解決 Hash 的的沖突的hash()方法
HashMap 的 hash 計(jì)算時(shí)先計(jì)算 hashCode(), 然后進(jìn)行二次 hash。
// 計(jì)算二次Hash
int hash = hash(key.hashCode());
// 通過(guò)Hash找數(shù)組索引
int i = hash & (tab.length-1);
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這個(gè)方法非常巧妙棍苹，它總是通過(guò) h &(table.length -1) 來(lái)得到該對(duì)象的保存位置无宿，而 HashMap 底層數(shù)組的長(zhǎng)度總是 2 的 n 次方。
當(dāng) length 總是 2 的倍數(shù)時(shí)枢里，h & (length-1) 將是一個(gè)非常巧妙的設(shè)計(jì)：
假設(shè) h=5,length=16, 那么 h & length - 1 將得到 5懈贺；
如果 h=6,length=16, 那么 h & length - 1 將得到 6
如果 h=15,length=16, 那么 h & length - 1 將得到 15；
但是當(dāng) h=16 時(shí) , length=16 時(shí)坡垫，那么 h & length - 1 將得到 0 了梭灿；
當(dāng) h=17 時(shí) , length=16 時(shí)，那么 h & length - 1 將得到 1 了冰悠。
這樣保證計(jì)算得到的索引值總是位于 table 數(shù)組的索引之內(nèi)堡妒。
put()方法
視頻講解：How HashMap works in Java? With Animation!! whats new in java8 tutorial
put()方法大致的思路為：
- 對(duì) key 的 hashCode() 做 hash，然后再計(jì)算 index;
- 如果沒(méi)碰撞直接放到 bucket 里溉卓；
- 如果碰撞了皮迟，以鏈表的形式存在 buckets 后；
- 如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng) (大于等于 TREEIFY_THRESHOLD=8)桑寨，就把鏈表轉(zhuǎn)換成紅黑樹(shù)伏尼；
- 如果節(jié)點(diǎn)已經(jīng)存在就替換 old value(保證 key 的唯一性)
- 如果 bucket 滿(mǎn)了 (超過(guò) load factor*current capacity)，就要 resize尉尾。
具體步驟為：
- 如果 table 沒(méi)有使用過(guò)的情況(tab=table)==null || (n=tab.length) == 0爆阶，則以默認(rèn)大小進(jìn)行一次 resize
- 計(jì)算 key 的 hash 值，然后獲取底層 table 數(shù)組的第 (n-1)&hash 的位置的數(shù)組索引 tab[i] 處的數(shù)據(jù)沙咏，即 hash 對(duì) n 取模的位置辨图，依賴(lài)的是 n 為 2 的次方這一條件
- 先檢查該 bucket 第一個(gè)元素是否是和插入的 key 相等 (如果是同一個(gè)對(duì)象則肯定 equals)
- 如果不相等并且是 TreeNode 的情況，調(diào)用 TreeNode 的 put 方法
- 否則循環(huán)遍歷鏈表肢藐，如果找到相等的 key 跳出循環(huán)否則達(dá)到最后一個(gè)節(jié)點(diǎn)時(shí)將新的節(jié)點(diǎn)添加到鏈表最后, 當(dāng)前面找到了相同的 key 的情況下替換這個(gè)節(jié)點(diǎn)的 value 為新的 value故河。
- 最后如果新增了 key-value 對(duì)，則增加 size 并且判斷是否超過(guò)了 threshold, 如果超過(guò)則需要進(jìn)行 resize 擴(kuò)容
put(K key, V val);
index = hash(key) & (n-1)
V val = get(Object key);
index = hash(key) & (n-1)
比較hashCode...
public V put(K key, V value) {
// 對(duì)key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table為空或者length=0時(shí)吆豹，以默認(rèn)大小擴(kuò)容鱼的，n為table的長(zhǎng)度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計(jì)算index，并對(duì)null做處理痘煤，table[i]==null
if ((p = tab[i = (n - 1) & hash]) == null)
// (n-1)&hash 與Java7中indexFor方法的實(shí)現(xiàn)相同凑阶，若i位置上的值為空，則新建一個(gè)Node速勇，table[i]指向該Node晌砾。
// 直接插入
tab[i] = newNode(hash, key, value, null);
else {
// 若i位置上的值不為空，判斷當(dāng)前位置上的Node p 是否與要插入的key的hash和key相同
Node<K,V> e; K k;
// 若節(jié)點(diǎn)key存在烦磁，直接覆蓋value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷table[i]該鏈?zhǔn)欠袷羌t黑樹(shù)养匈，如果是紅黑樹(shù)哼勇，則直接在樹(shù)中插入鍵值對(duì)
else if (p instanceof TreeNode)
// 不同，且當(dāng)前位置上的的node p已經(jīng)是TreeNode的實(shí)例呕乎，則再該樹(shù)上插入新的node
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// table[i]該鏈?zhǔn)瞧胀ㄦ湵砘＃M(jìn)行鏈表的插入操作
else {
// 在i位置上的鏈表中找到p.next為null的位置，binCount計(jì)算出當(dāng)前鏈表的長(zhǎng)度猬仁，如果繼續(xù)將沖突的節(jié)點(diǎn)插入到該鏈表中帝璧，會(huì)使鏈表的長(zhǎng)度大于tree化的閾值，則將鏈表轉(zhuǎn)換成tree湿刽。
for (int binCount = 0; ; ++binCount) {
// 如果遍歷到了最后一個(gè)節(jié)點(diǎn)的烁，說(shuō)明沒(méi)有匹配的key，則創(chuàng)建一個(gè)新的節(jié)點(diǎn)并添加到最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表長(zhǎng)度大于8轉(zhuǎn)換為紅黑樹(shù)進(jìn)行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍歷過(guò)程中若發(fā)現(xiàn) key 已經(jīng)存在直接覆蓋 value 并跳出循環(huán)即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 已經(jīng)存在該key的情況時(shí)诈闺，將對(duì)應(yīng)的節(jié)點(diǎn)的value設(shè)置為新的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入成功后渴庆，判斷實(shí)際存在的鍵值對(duì)數(shù)量 size 是否超多了最大容量 threshold，如果超過(guò)雅镊，進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
紅黑樹(shù)結(jié)構(gòu)的putVal方法：
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
get()方法
get(key) 方法時(shí)獲取 key 的 hash 值襟雷，計(jì)算 hash&(n-1) 得到在鏈表數(shù)組中的位置 first=tab[hash&(n-1)], 先判斷 first 的 key 是否與參數(shù) key 相等，不等就遍歷后面的鏈表找到相同的 key 值返回對(duì)應(yīng)的 Value 值即可仁烹。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 根據(jù)哈希表元素個(gè)數(shù)與哈希值求模（使用的公式是 (n - 1) &hash）得到 key 所在的桶的頭結(jié)點(diǎn)耸弄，如果頭節(jié)點(diǎn)恰好是紅黑樹(shù)節(jié)點(diǎn)，就調(diào)用紅黑樹(shù)節(jié)點(diǎn)的 getTreeNode() 方法卓缰，否則就遍歷鏈表節(jié)點(diǎn)
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) {
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;
}
resize()方法
擴(kuò)容 (resize) 就是重新計(jì)算容量计呈，向 HashMap 對(duì)象里不停的添加元素，而 HashMap 對(duì)象內(nèi)部的數(shù)組無(wú)法裝載更多的元素時(shí)僚饭，對(duì)象就需要擴(kuò)大數(shù)組的長(zhǎng)度震叮，以便能裝入更多的元素胧砰。當(dāng)然 Java 里的數(shù)組是無(wú)法自動(dòng)擴(kuò)容的鳍鸵，方法是使用一個(gè)新的數(shù)組代替已有的容量小的數(shù)組，就像我們用一個(gè)小桶裝水尉间，如果想裝更多的水偿乖，就得換大水桶。
由于需要考慮 hash 沖突解決時(shí)采用的可能是鏈表也可能是紅黑樹(shù)的方式哲嘲，因此 resize 方法相比 JDK7 中復(fù)雜了一些贪薪。
rehashing 觸發(fā)的條件：1、超過(guò)默認(rèn)容量 * 加載因子眠副；2画切、加載因子不靠譜，比如遠(yuǎn)大于 1囱怕。
在 HashMap 進(jìn)行擴(kuò)容時(shí)霍弹，會(huì)進(jìn)行 2 倍擴(kuò)容毫别，而且會(huì)將哈希碰撞處的數(shù)據(jù)再次分散開(kāi)來(lái)，一部分依照新的 hash 索引值呆在 “原處”典格，一部分加上偏移量移動(dòng)到新的地方岛宦。
具體步驟為：
- 首先計(jì)算 resize() 后的新的 capacity 和 threshold 值。如果原有的 capacity 大于零則將 capacity 增加一倍耍缴，否則設(shè)置成默認(rèn)的 capacity砾肺。
- 創(chuàng)建新的數(shù)組，大小是新的 capacity
- 將舊數(shù)組的元素放置到新數(shù)組中
final Node<K,V>[] resize() {
// 將字段引用copy到局部變量表防嗡，這樣在之后的使用時(shí)可以減少getField指令的調(diào)用
Node<K,V>[] oldTab = table;
// oldCap為原數(shù)組的大小或當(dāng)空時(shí)為0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果超過(guò)最大容量1>>30变汪，無(wú)法再擴(kuò)充table，只能改變閾值
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的數(shù)組的大小是舊數(shù)組的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 當(dāng)舊的的數(shù)組大小大于等于默認(rèn)大小時(shí)蚁趁，threshold也擴(kuò)大一倍
newThr = oldThr << 1;
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 初始化操作
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 創(chuàng)建容量為newCap的newTab疫衩，并將oldTab中的Node遷移過(guò)來(lái)，這里需要考慮鏈表和tree兩種情況荣德。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 將原數(shù)組中的數(shù)組復(fù)制到新數(shù)組中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果e是該bucket唯一的一個(gè)元素闷煤，則直接賦值到新數(shù)組中
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// split方法會(huì)將樹(shù)分割為lower 和upper tree兩個(gè)樹(shù)，如果子樹(shù)的節(jié)點(diǎn)數(shù)小于了UNTREEIFY_THRESHOLD閾值涮瞻，則將樹(shù)untreeify鲤拿，將節(jié)點(diǎn)都存放在newTab中。
// TreeNode的情況則使用TreeNode中的split方法將這個(gè)樹(shù)分成兩個(gè)小樹(shù)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 保持順序
// 否則則創(chuàng)建兩個(gè)鏈表用來(lái)存放要放的數(shù)據(jù)署咽，hash值&oldCap為0的(即oldCap的1的位置的和hash值的同樣的位置都是1近顷，同樣是基于capacity是2的次方這一前提)為low鏈表，反之為high鏈表, 通過(guò)這種方式將舊的數(shù)據(jù)分到兩個(gè)鏈表中再放到各自對(duì)應(yīng)余數(shù)的位置
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 按照e.hash值區(qū)分放在loTail后還是hiTail后
if ((e.hash & oldCap) == 0) {
// 運(yùn)算結(jié)果為0的元素宁否，用lo記錄并連接成新的鏈表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 運(yùn)算結(jié)果不為0的數(shù)據(jù)窒升，用li記錄
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 處理完之后放到新數(shù)組中
if (loTail != null) {
loTail.next = null;
// lo仍然放在“原處”，這個(gè)“原處”是根據(jù)新的hash值算出來(lái)的
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// li放在j+oldCap位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
下面舉個(gè)例子說(shuō)明下擴(kuò)容過(guò)程慕匠。
假設(shè)了我們的 hash 算法就是簡(jiǎn)單的用 key mod 一下表的大斜バ搿（也就是數(shù)組的長(zhǎng)度）。其中的哈希桶數(shù)組 table 的 size=2台谊， 所以 key = 3蓉媳、7、5锅铅，put 順序依次為 5酪呻、7、3盐须。在 mod 2 以后都沖突在 table[1] 這里了玩荠。這里假設(shè)負(fù)載因子 loadFactor=1，即當(dāng)鍵值對(duì)的實(shí)際大小 size 大于 table 的實(shí)際大小時(shí)進(jìn)行擴(kuò)容。接下來(lái)的三個(gè)步驟是哈希桶數(shù)組 resize 成 4阶冈，然后所有的 Node 重新 rehash 的過(guò)程屉凯。
下面我們講解下 JDK1.8 做了哪些優(yōu)化。
經(jīng)過(guò)觀測(cè)可以發(fā)現(xiàn)眼溶，我們使用的是 2 次冪的擴(kuò)展 (指長(zhǎng)度擴(kuò)為原來(lái) 2 倍)悠砚，所以，元素的位置要么是在原位置堂飞，要么是在原位置再移動(dòng) 2 次冪的位置灌旧。看下圖可以明白這句話的意思绰筛，n 為 table 的長(zhǎng)度枢泰，圖（a）表示擴(kuò)容前的 key1 和 key2 兩種 key 確定索引位置的示例，圖（b）表示擴(kuò)容后 key1 和 key2 兩種 key 確定索引位置的示例铝噩，其中 hash1 是 key1 對(duì)應(yīng)的哈希與高位運(yùn)算結(jié)果衡蚂。
元素在重新計(jì)算 hash 之后，因?yàn)?n 變?yōu)?2 倍骏庸，那么 n-1 的 mask 范圍在高位多 1bit(紅色)毛甲，因此新的 index 就會(huì)發(fā)生這樣的變化：
因此，我們?cè)跀U(kuò)充 HashMap 的時(shí)候具被，不需要像 JDK1.7 的實(shí)現(xiàn)那樣重新計(jì)算 hash玻募，只需要看看原來(lái)的 hash 值新增的那個(gè) bit 是 1 還是 0 就好了，是 0 的話索引沒(méi)變一姿，是 1 的話索引變成 “原索引 + oldCap”七咧，可以看看下圖為 16 擴(kuò)充為 32 的 resize 示意圖：
這個(gè)設(shè)計(jì)確實(shí)非常的巧妙，既省去了重新計(jì)算 hash 值的時(shí)間叮叹，而且同時(shí)艾栋，由于新增的 1bit 是 0 還是 1 可以認(rèn)為是隨機(jī)的，因此 resize 的過(guò)程蛉顽，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的 bucket 了蝗砾。這一塊就是 JDK1.8 新增的優(yōu)化點(diǎn)。
紅黑樹(shù)結(jié)構(gòu)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links 父節(jié)點(diǎn)
TreeNode<K,V> left; // 左子樹(shù)
TreeNode<K,V> right; // 右子樹(shù)
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 顏色屬性
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
樹(shù)形化操作
- 根據(jù)哈希表中元素個(gè)數(shù)確定是擴(kuò)容還是樹(shù)形化
- 如果是樹(shù)形化遍歷桶中的元素蜂林，創(chuàng)建相同個(gè)數(shù)的樹(shù)形節(jié)點(diǎn)遥诉，復(fù)制內(nèi)容，建立起聯(lián)系
- 然后讓桶第一個(gè)元素指向新建的樹(shù)頭結(jié)點(diǎn)噪叙，替換桶的鏈表內(nèi)容為樹(shù)形內(nèi)容
// MIN_TREEIFY_CAPACITY 的值為64，若當(dāng)前table的length不夠霉翔，則resize()
// 將桶內(nèi)所有的 鏈表節(jié)點(diǎn) 替換成 紅黑樹(shù)節(jié)點(diǎn)
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果當(dāng)前哈希表為空睁蕾，或者哈希表中元素的個(gè)數(shù)小于樹(shù)形化閾值(默認(rèn)為 64)，就去新建(擴(kuò)容)
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 如果哈希表中的元素個(gè)數(shù)超過(guò)了樹(shù)形化閾值，則進(jìn)行樹(shù)形化
// e 是哈希表中指定位置桶里的鏈表節(jié)點(diǎn)子眶，從第一個(gè)開(kāi)始
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 紅黑樹(shù)的頭瀑凝、尾節(jié)點(diǎn)
TreeNode<K,V> hd = null, tl = null;
do {
// 新建一個(gè)樹(shù)形節(jié)點(diǎn)，內(nèi)容和當(dāng)前鏈表節(jié)點(diǎn) e 一致
TreeNode<K,V> p = replacementTreeNode(e, null);
// 確定樹(shù)頭節(jié)點(diǎn)
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 讓桶的第一個(gè)元素指向新建的紅黑樹(shù)頭結(jié)點(diǎn)臭杰，以后這個(gè)桶里的元素就是紅黑樹(shù)而不是鏈表了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
size()方法
HashMap 的大小很簡(jiǎn)單粤咪，不是實(shí)時(shí)計(jì)算的，而是每次新增加 Entry 的時(shí)候渴杆，size 就遞增寥枝。刪除的時(shí)候就遞減〈沤保空間換時(shí)間的做法囊拜。因?yàn)樗皇蔷€程安全的。完全可以這么做比搭，效率高冠跷。
面試問(wèn)題
HashMap 的實(shí)現(xiàn)原理
HashMap 是典型的空間換時(shí)間的一種技術(shù)手段。
- 如何解決 hash 沖突
- loadFactor 等核心概念
- 擴(kuò)容機(jī)制
構(gòu)造函數(shù)中 initialCapacity 與 loadFactor 兩個(gè)參數(shù)
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個(gè)指定容量和加載因子的空 HashMap
在這里提到了兩個(gè)參數(shù)：初始容量身诺，加載因子蜜托。這兩個(gè)參數(shù)是影響 HashMap 性能的重要參數(shù)，其中容量表示哈希表中桶的數(shù)量霉赡，初始容量是創(chuàng)建哈希表時(shí)的容量盗冷，加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿(mǎn)的一種尺度，它衡量的是一個(gè)散列表的空間的使用程度同廉，負(fù)載因子越大表示散列表的裝填程度越高仪糖，反之愈小。對(duì)于使用鏈表法的散列表來(lái)說(shuō)迫肖，查找一個(gè)元素的平均時(shí)間是 O(1+a)锅劝，因此如果負(fù)載因子越大，對(duì)空間的利用更充分蟆湖，然而后果是查找效率的降低故爵；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過(guò)于稀疏隅津，對(duì)空間造成嚴(yán)重浪費(fèi)诬垂。系統(tǒng)默認(rèn)負(fù)載因子為 0.75，一般情況下我們是無(wú)需修改的伦仍。
initialCapacity 和 loadFactor 參數(shù)設(shè)什么樣的值好呢结窘？
initialCapacity 的默認(rèn)值是 16，有些人可能會(huì)想如果內(nèi)存足夠充蓝，是不是可以將 initialCapacity 設(shè)大一些隧枫，即使用不了這么大喉磁，就可避免擴(kuò)容導(dǎo)致的效率的下降，反正無(wú)論 initialCapacity 大小官脓，我們使用的 get 和 put 方法都是常數(shù)復(fù)雜度的协怒。這么說(shuō)沒(méi)什么不對(duì)，但是可能會(huì)忽略一點(diǎn)卑笨，實(shí)際的程序可能不僅僅使用 get 和 put 方法孕暇，也有可能使用迭代器，如 initialCapacity 容量較大赤兴，那么會(huì)使迭代器效率降低妖滔。所以理想的情況還是在使用 HashMap 前估計(jì)一下數(shù)據(jù)量。
加載因子默認(rèn)值是 0.75搀缠，是 JDK 權(quán)衡時(shí)間和空間效率之后得到的一個(gè)相對(duì)優(yōu)良的數(shù)值铛楣。如果這個(gè)值過(guò)大，雖然空間利用率是高了艺普，但是對(duì)于 HashMap 中的一些方法的效率就下降了簸州，包括 get 和 put 方法，會(huì)導(dǎo)致每個(gè) hash 桶所附加的鏈表增長(zhǎng)歧譬，影響存取效率岸浑。如果比較小，除了導(dǎo)致空間利用率較低外沒(méi)有什么壞處瑰步，只要有的是內(nèi)存矢洲，畢竟現(xiàn)在大多數(shù)人把時(shí)間看的比空間重要。但是實(shí)際中還是很少有人會(huì)將這個(gè)值設(shè)置的低于 0.5缩焦。
size 為什么必須是 2 的整數(shù)次冪
Java 編程：淺析 HashMap 中數(shù)組的 size 為什么必須是 2 的整數(shù)次冪
這是為了服務(wù)key映射到index的Hash算法的读虏，公式index=hashcode(key)&(length-1)，初始長(zhǎng)度(16-1)袁滥，二進(jìn)制為1111&hashcode結(jié)果為hashcode最后四位盖桥，能最大程度保持平均，二的冪數(shù)保證二進(jìn)制為1题翻，保持hashcode最后四位揩徊。這種算法在保持分布均勻之外，效率也非常高嵌赠。
HashMap 的 key 為什么一般用字符串比較多塑荒，能用其他對(duì)象，或者自定義的對(duì)象嗎姜挺？為什么齿税？
能用其他對(duì)象，必須是immutable的初家，但是自實(shí)現(xiàn)的類(lèi)必須Override兩個(gè)方法：equals()和hashCode()偎窘。否則會(huì)調(diào)用默認(rèn)的Object類(lèi)的對(duì)應(yīng)方法乌助。
為什么HashMap要允許key和value都能為null呢溜在？
解釋一：首先陌知，HashTable 是一個(gè)過(guò)時(shí)的類(lèi)，不應(yīng)該再使用了掖肋。
當(dāng)時(shí)不允許是因?yàn)橄Ｍ總€(gè) key 都會(huì)實(shí)現(xiàn) hashCode 和 equals 方法仆葡。而 null 顯然沒(méi)有。后來(lái)志笼，大家都意識(shí)到 null 值的重要性沿盅，所以 HashMap 允許 null 值的 key 和 value。當(dāng) key 為 null 時(shí)纫溃，HashMap 將會(huì)把 key-value pair 存放在一個(gè)特殊的位置腰涧，比如第一個(gè)槽位里。
解釋二：ConcurrentHashmap 和 Hashtable 都是支持并發(fā)的紊浩，這樣會(huì)有一個(gè)問(wèn)題窖铡，當(dāng)你通過(guò) get(k) 獲取對(duì)應(yīng)的 value 時(shí)，如果獲取到的是 null 時(shí)坊谁，你無(wú)法判斷费彼，它是 put() 的時(shí)候 value 為 null，還是這個(gè) key 從來(lái)沒(méi)有做過(guò)映射口芍。HashMap 是非并發(fā)的箍铲，可以通過(guò) contains(key) 來(lái)做這個(gè)判斷。而支持并發(fā)的 Map 在調(diào)用 m.contains（key）和 m.get(key),m 可能已經(jīng)不同了鬓椭。
為什么需要使用加載因子颠猴，為什么需要擴(kuò)容呢？
因?yàn)槿绻畛浔群艽笮∪荆f(shuō)明利用的空間很多翘瓮，如果一直不進(jìn)行擴(kuò)容的話，鏈表就會(huì)越來(lái)越長(zhǎng)氧映，這樣查找的效率很低春畔，因?yàn)殒湵淼拈L(zhǎng)度很大（當(dāng)然最新版本使用了紅黑樹(shù)后會(huì)改進(jìn)很多），擴(kuò)容之后岛都，將原來(lái)鏈表數(shù)組的每一個(gè)鏈表分成奇偶兩個(gè)子鏈表分別掛在新鏈表數(shù)組的散列位置律姨，這樣就減少了每個(gè)鏈表的長(zhǎng)度，增加查找效率臼疫。
HashMap 本來(lái)是以空間換時(shí)間择份，所以填充比沒(méi)必要太大。但是填充比太小又會(huì)導(dǎo)致空間浪費(fèi)烫堤。如果關(guān)注內(nèi)存荣赶，填充比可以稍大凤价，如果主要關(guān)注查找性能，填充比可以稍小拔创。
使用紅黑樹(shù)的改進(jìn)
在 java jdk8 中對(duì) HashMap 的源碼進(jìn)行了優(yōu)化利诺，在 jdk7 中，HashMap 處理 “碰撞” 的時(shí)候剩燥，都是采用鏈表來(lái)存儲(chǔ)慢逾，當(dāng)碰撞的結(jié)點(diǎn)很多時(shí)，查詢(xún)時(shí)間是 O(n)灭红。
在 jdk8 中侣滩，HashMap 處理 “碰撞” 增加了紅黑樹(shù)這種數(shù)據(jù)結(jié)構(gòu)，當(dāng)碰撞結(jié)點(diǎn)較少時(shí)变擒，采用鏈表存儲(chǔ)君珠，當(dāng)較大時(shí)（>8 個(gè)），采用紅黑樹(shù)（特點(diǎn)是查詢(xún)時(shí)間是 O(logn)）存儲(chǔ)（有一個(gè)閥值控制娇斑，大于閥值 (8 個(gè))策添，將鏈表存儲(chǔ)轉(zhuǎn)換成紅黑樹(shù)存儲(chǔ)）
問(wèn)題分析：
哈希碰撞會(huì)對(duì) hashMap 的性能帶來(lái)災(zāi)難性的影響。如果多個(gè) hashCode() 的值落到同一個(gè)桶內(nèi)的時(shí)候悠菜，這些值是存儲(chǔ)到一個(gè)鏈表中的舰攒。最壞的情況下，所有的 key 都映射到同一個(gè)桶中悔醋，這樣 hashmap 就退化成了一個(gè)鏈表——查找時(shí)間從 O(1) 到 O(n)摩窃。
隨著 HashMap 的大小的增長(zhǎng)，get() 方法的開(kāi)銷(xiāo)也越來(lái)越大芬骄。由于所有的記錄都在同一個(gè)桶里的超長(zhǎng)鏈表內(nèi)猾愿，平均查詢(xún)一條記錄就需要遍歷一半的列表。
JDK1.8HashMap 的紅黑樹(shù)是這樣解決的：
如果某個(gè)桶中的記錄過(guò)大的話（當(dāng)前是 TREEIFY_THRESHOLD = 8）账阻，HashMap 會(huì)動(dòng)態(tài)的使用一個(gè)專(zhuān)門(mén)的 treemap 實(shí)現(xiàn)來(lái)替換掉它蒂秘。這樣做的結(jié)果會(huì)更好，是 O(logn)淘太，而不是糟糕的 O(n)姻僧。
它是如何工作的？前面產(chǎn)生沖突的那些 KEY 對(duì)應(yīng)的記錄只是簡(jiǎn)單的追加到一個(gè)鏈表后面蒲牧，這些記錄只能通過(guò)遍歷來(lái)進(jìn)行查找撇贺。但是超過(guò)這個(gè)閾值后 HashMap 開(kāi)始將列表升級(jí)成一個(gè)二叉樹(shù)，使用哈希值作為樹(shù)的分支變量冰抢，如果兩個(gè)哈希值不等松嘶，但指向同一個(gè)桶的話，較大的那個(gè)會(huì)插入到右子樹(shù)里挎扰。如果哈希值相等翠订，HashMap 希望 key 值最好是實(shí)現(xiàn)了 Comparable 接口的巢音，這樣它可以按照順序來(lái)進(jìn)行插入。這對(duì) HashMap 的 key 來(lái)說(shuō)并不是必須的尽超，不過(guò)如果實(shí)現(xiàn)了當(dāng)然最好官撼。如果沒(méi)有實(shí)現(xiàn)這個(gè)接口，在出現(xiàn)嚴(yán)重的哈希碰撞的時(shí)候橙弱，你就并別指望能獲得性能提升了歧寺。
HashMap 的 key 和 value 都能為 null 么燥狰？如果 key 能為 null棘脐，那么它是怎么樣查找值的？
如果 key 為 null龙致，則直接從哈希表的第一個(gè)位置 table[0] 對(duì)應(yīng)的鏈表上查找,由 putForNullKey（）實(shí)現(xiàn)蛀缝。記住，key 為 null 的鍵值對(duì)永遠(yuǎn)都放在以 table[0] 為頭結(jié)點(diǎn)的鏈表中目代。
平時(shí)在使用 HashMap 時(shí)一般使用什么類(lèi)型的元素作為 Key屈梁？
面試者通常會(huì)回答，使用 String 或者 Integer 這樣的類(lèi)榛了。這個(gè)時(shí)候可以繼續(xù)追問(wèn)為什么使用 String在讶、Integer 呢？這些類(lèi)有什么特點(diǎn)霜大？如果面試者有很好的思考构哺，可以回答出這些類(lèi)是 Immutable 的，并且這些類(lèi)已經(jīng)很規(guī)范的覆寫(xiě)了 hashCode() 以及 equals() 方法战坤。作為不可變類(lèi)天生是線程安全的曙强，而且可以很好的優(yōu)化比如可以緩存 hash 值，避免重復(fù)計(jì)算等等途茫，那么基本上這道題算是過(guò)關(guān)了碟嘴。
在 HashMap 中使用可變對(duì)象作為 Key 帶來(lái)的問(wèn)題：如果 HashMap Key 的哈希值在存儲(chǔ)鍵值對(duì)后發(fā)生改變，Map 可能再也查找不到這個(gè) Entry 了囊卜。詳見(jiàn)：一道面試題看 HashMap 的存儲(chǔ)方式
Key對(duì)應(yīng)的hashCode()方法
對(duì)于非 String 類(lèi)型的 key娜扇，hash() 使用 key 的 hashCode() 計(jì)算出該 key-value pair 對(duì)應(yīng)在數(shù)組的索引 (String 類(lèi)型的 key 有另一套計(jì)算 hash() 的方法，再次不做贅述）栅组，在 get() 方法中會(huì)使用 key 的 equal() 方法判斷數(shù)組中的中的 key 是否與傳入的 key 相等雀瓢。由此可見(jiàn)，在 HashMap 的使用中笑窜，key 類(lèi)型中定義的 hashCode() 和 equal() 方法都是非常重要的致燥。假設(shè) key 內(nèi)部的值發(fā)生變化，導(dǎo)致 hashCode()/equal() 的結(jié)果改變排截，那么該 key 在 HashMap 中的存取則會(huì)產(chǎn)生問(wèn)題嫌蚤。
如何創(chuàng)建不可變類(lèi)(Immutable)/如果讓你實(shí)現(xiàn)一個(gè)自定義的 class 作為 HashMap 的 key 該如何實(shí)現(xiàn)辐益？
如何創(chuàng)建不可變（Immutable）的 Java 類(lèi)或?qū)ο?/a>
HashMap 的 key 可以是可變的對(duì)象嗎
危險(xiǎn)！在 HashMap 中將可變對(duì)象用作 Key
如何使用建造者模式 (Builder Pattern) 創(chuàng)建不可變類(lèi)
Immutable Objects 就是那些一旦被創(chuàng)建脱吱，它們的狀態(tài)就不能被改變的 Objects智政，每次對(duì)他們的改變都是產(chǎn)生了新的 immutable 的對(duì)象，而 mutable Objects 就是那些創(chuàng)建后箱蝠，狀態(tài)可以被改變的 Objects续捂。
舉個(gè)例子：String 是 immutable 的，每次對(duì)于 String 對(duì)象的修改都將產(chǎn)生一個(gè)新的 String 對(duì)象宦搬，而原來(lái)的對(duì)象保持不變牙瓢。而 StringBuilder 是 mutable，因?yàn)槊看螌?duì)于它的對(duì)象的修改都作用于該對(duì)象本身间校，并沒(méi)有產(chǎn)生新的對(duì)象矾克。
但有的時(shí)候 String 的 immutable 特性也會(huì)引起安全問(wèn)題，這就是密碼應(yīng)該存放在字符數(shù)組中而不是 String 中的原因憔足！
要寫(xiě)出這樣的類(lèi)胁附，需要遵循以下幾個(gè)原則：
- immutable 對(duì)象的狀態(tài)在創(chuàng)建之后就不能發(fā)生改變，任何對(duì)它的改變都應(yīng)該產(chǎn)生一個(gè)新的對(duì)象滓彰。
- Immutable 類(lèi)的所有的屬性都應(yīng)該是 final 的控妻。
- 對(duì)象必須被正確的創(chuàng)建，比如：對(duì)象引用在對(duì)象創(chuàng)建過(guò)程中不能泄露 (leak)揭绑。
- 對(duì)象應(yīng)該是 final 的弓候，以此來(lái)限制子類(lèi)繼承父類(lèi)，以避免子類(lèi)改變了父類(lèi)的 immutable 特性洗做。
- 如果類(lèi)中包含 mutable 類(lèi)對(duì)象弓叛，那么返回給客戶(hù)端的時(shí)候，返回該對(duì)象的一個(gè)拷貝诚纸，而不是該對(duì)象本身（該條可以歸為第一條中的一個(gè)特例）
public class MutableKey {
private int i;
private int j;
public MutableKey(int i, int j) {
this.i = i;
this.j = j;
}
public final int getI() {
return i;
}
public final void setI(int i) {
this.i = i;
}
public final int getJ() {
return j;
}
public final void setJ(int j) {
this.j = j;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + i;
result = prime * result + j;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (!(obj instanceof MutableKey)) {
return false;
}
MutableKey other = (MutableKey) obj;
if (i != other.i) {
return false;
}
if (j != other.j) {
return false;
}
return true;
}
public static void main(String[] args) {
// Object created
MutableKey key = new MutableKey(10, 20);
System.out.println("Hash code: " + key.hashCode());
// Object State is changed after object creation.
key.setI(30);
key.setJ(40);
System.out.println("Hash code: " + key.hashCode());
}
}
public class MutableSafeKey {
// Cannot be changed once object is created. No setter for this field.
private final int id;
private String name;
public MutableSafeKey(final int id) {
this.id = id;
}
public final String getName() {
return name;
}
public final void setName(final String name) {
this.name = name;
}
public int getId() {
return id;
}
// Hash code depends only on 'id' which cannot be
// changed once object is created. So hash code will not change
// on object's state change
@Override
public int hashCode() {
int result = 17;
result = 31 * result + id;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MutableSafeKey other = (MutableSafeKey) obj;
if (id != other.id)
return false;
return true;
}
}
你能設(shè)計(jì)一個(gè)算法（輸入是 java 源文件）撰筷，判斷一個(gè)類(lèi)是否是 Immutable 的嗎？
如何衡量一個(gè) hash 算法的好壞
hashCode 不要求唯一但是要盡可能的均勻分布畦徘，而且算法效率要盡可能的快毕籽。
HashMap 中 hash 函數(shù)怎么是是實(shí)現(xiàn)的？
高 16bit 不變井辆，低 16bit 和高 16bit 做了一個(gè)異或：（n - 1） & hash --> 得到下標(biāo)
拓展：為什么 h = 31 * h + val[off++]; 這一行使用31 关筒，而不是別的數(shù)字，這是一個(gè)魔術(shù)嗎杯缺？
HashMap 怎樣解決哈希沖突蒸播，講一下擴(kuò)容過(guò)程。
JDK 使用了鏈地址法，hash 表的每個(gè)元素又分別鏈接著一個(gè)單鏈表袍榆，元素為頭結(jié)點(diǎn)胀屿，如果不同的 key 映射到了相同的下標(biāo)，那么就使用頭插法包雀，插入到該元素對(duì)應(yīng)的鏈表宿崭。
擴(kuò)容過(guò)程：
- 將新節(jié)點(diǎn)加到鏈表后
- 容量擴(kuò)充為原來(lái)的兩倍，然后對(duì)每個(gè)節(jié)點(diǎn)重新計(jì)算哈希值才写。
- 這個(gè)值只可能在兩個(gè)地方葡兑，一個(gè)是原下標(biāo)的位置，另一種是在下標(biāo)為 <原下標(biāo) + 原容量> 的位置赞草。
哈希沖突的常見(jiàn)解決方法：
- 開(kāi)放定址法（線性探測(cè)再散列讹堤，二次探測(cè)再散列，偽隨機(jī)探測(cè)再散列）
- 再哈希法房资，就是在原 hash 函數(shù)的基礎(chǔ)蜕劝，再次執(zhí)行 hash 算法
- 鏈地址法，各種處理哈希碰撞的方法中轰异，這種最簡(jiǎn)單，也是 HashMap 中使用的方法
- 建立一個(gè)公共溢出區(qū)
failure case/resize()
Load factor(default to 75%) 和 Initial capacity(default to 16) 是 HashMap 表的兩個(gè)重要屬性暑始，如果 HashMap 中 entry 數(shù)量超過(guò)了 threshold(loadfactor *capacity) 搭独，那么 HashMap 就不得不擴(kuò)充 capacity（否則 hash collison 發(fā)生的概率就會(huì)大大增加，導(dǎo)致整個(gè) HashMap 性能下降）廊镜，擴(kuò)充 capacity 是一件比較麻煩的事情牙肝，因?yàn)閿?shù)組的連續(xù)性，HashMap 不得不開(kāi)辟一塊更大數(shù)組嗤朴，還要把原來(lái)的 entries 全部 transfer 到新的數(shù)組中配椭，在某些情況下還需要重新計(jì)算 key 的 hash() 結(jié)果。另一方面雹姊，HashMap 的 capacity 也不是越大越好股缸，事實(shí)上 HashMap 的遍歷本質(zhì)上是基于內(nèi)部數(shù)組的遍歷，如果內(nèi)部數(shù)組是無(wú)意義的大吱雏，那么遍歷 HashMap 相對(duì)來(lái)說(shuō)不是特別高效敦姻。
為什么 HashMap 是線程不安全的，實(shí)際會(huì)如何體現(xiàn)歧杏？
第一镰惦，如果多個(gè)線程同時(shí)使用 put 方法添加元素
假設(shè)正好存在兩個(gè) put 的 key 發(fā)生了碰撞 (hash 值一樣)，那么根據(jù) HashMap 的實(shí)現(xiàn)犬绒，這兩個(gè) key 會(huì)添加到數(shù)組的同一個(gè)位置旺入，這樣最終就會(huì)發(fā)生其中一個(gè)線程的 put 的數(shù)據(jù)被覆蓋。
第二凯力，如果多個(gè)線程同時(shí)檢測(cè)到元素個(gè)數(shù)超過(guò)數(shù)組大小 * loadFactor
這樣會(huì)發(fā)生多個(gè)線程同時(shí)對(duì) hash 數(shù)組進(jìn)行擴(kuò)容茵瘾，都在重新計(jì)算元素位置以及復(fù)制數(shù)據(jù)急膀，但是最終只有一個(gè)線程擴(kuò)容后的數(shù)組會(huì)賦給 table，也就是說(shuō)其他線程的都會(huì)丟失龄捡，并且各自線程 put 的數(shù)據(jù)也丟失卓嫂。且會(huì)引起死循環(huán)的錯(cuò)誤。
具體細(xì)節(jié)上的原因聘殖，可以參考：不正當(dāng)使用 HashMap 導(dǎo)致 cpu 100% 的問(wèn)題追究
HashMap 不是線程安全的晨雳，你怎么理解線程安全。原理是什么奸腺？幾種方式避免線程安全的問(wèn)題
- 直接使用 Hashtable餐禁，但是當(dāng)一個(gè)線程訪問(wèn) HashTable 的同步方法時(shí)，其他線程如果也要訪問(wèn)同步方法突照，會(huì)被阻塞住帮非。舉個(gè)例子，當(dāng)一個(gè)線程使用 put 方法時(shí)讹蘑，另一個(gè)線程不但不可以使用 put 方法末盔，連 get 方法都不可以，效率很低座慰，現(xiàn)在基本不會(huì)選擇它了陨舱。
- HashMap 可以通過(guò)下面的語(yǔ)句進(jìn)行同步：
Collections.synchronizeMap(hashMap); - 直接使用 JDK 5 之后的 ConcurrentHashMap显押。
HashTable 和 HashMap 的區(qū)別有哪些掖举？
HashMap 和 Hashtable 都實(shí)現(xiàn)了 Map 接口，但決定用哪一個(gè)之前先要弄清楚它們之間的分別痹兜。主要的區(qū)別有：線程安全性蛮粮，同步 (synchronization)益缎，以及速度。
理解 HashMap 是 Hashtable 的輕量級(jí)實(shí)現(xiàn)（非線程安全的實(shí)現(xiàn)然想，hashtable 是非輕量級(jí)莺奔，線程安全的），都實(shí)現(xiàn) Map 接口又沾，主要區(qū)別在于：
- 由于 HashMap 非線程安全弊仪，在只有一個(gè)線程訪問(wèn)的情況下，效率要高于 HashTable
- HashMap 允許將 null 作為一個(gè) entry 的 key 或者 value杖刷，而 Hashtable 不允許励饵。
- HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey滑燃。因?yàn)?contains 方法容易讓人引起誤解役听。
- Hashtable 繼承自陳舊的 Dictionary 類(lèi)，而 HashMap 是 Java1.2 引進(jìn)的 Map 的一個(gè)實(shí)現(xiàn)。
- Hashtable 和 HashMap 擴(kuò)容的方法不一樣典予，HashTable 中 hash 數(shù)組默認(rèn)大小 11甜滨，擴(kuò)容方式是 old*2+1。HashMap 中 hash 數(shù)組的默認(rèn)大小是 16瘤袖，而且一定是 2 的指數(shù)衣摩，增加為原來(lái)的 2 倍，沒(méi)有加 1捂敌。
- 兩者通過(guò) hash 值散列到 hash 表的算法不一樣艾扮，HashTbale 是古老的除留余數(shù)法，直接使用 hashcode占婉，而后者是強(qiáng)制容量為 2 的冪泡嘴，重新根據(jù) hashcode 計(jì)算 hash 值，在使用 hash 位與 （hash 表長(zhǎng)度 – 1）逆济，也等價(jià)取膜酌予，但更加高效，取得的位置更加分散奖慌，偶數(shù)抛虫，奇數(shù)保證了都會(huì)分散到。前者就不能保證升薯。
- 另一個(gè)區(qū)別是 HashMap 的迭代器 (Iterator) 是 fail-fast 迭代器莱褒，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的。所以當(dāng)有其它線程改變了 HashMap 的結(jié)構(gòu)（增加或者移除元素）涎劈，將會(huì)拋出 ConcurrentModificationException，但迭代器本身的 remove() 方法移除元素則不會(huì)拋出 ConcurrentModificationException 異常阅茶。但這并不是一個(gè)一定發(fā)生的行為蛛枚，要看 JVM。這條同樣也是 Enumeration 和 Iterator 的區(qū)別脸哀。
fail-fast 和 iterator 迭代器相關(guān)蹦浦。如果某個(gè)集合對(duì)象創(chuàng)建了 Iterator 或者 ListIterator，然后其它的線程試圖 “結(jié)構(gòu)上” 更改集合對(duì)象撞蜂，將會(huì)拋出 ConcurrentModificationException 異常盲镶。但其它線程可以通過(guò) set() 方法更改集合對(duì)象是允許的，因?yàn)檫@并沒(méi)有從 “結(jié)構(gòu)上” 更改集合蝌诡。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改溉贿，再調(diào)用 set() 方法，將會(huì)拋出 IllegalArgumentException 異常浦旱。
結(jié)構(gòu)上的更改指的是刪除或者插入一個(gè)元素宇色，這樣會(huì)影響到 map 的結(jié)構(gòu)。
該條說(shuō)白了就是在使用迭代器的過(guò)程中有其他線程在結(jié)構(gòu)上修改了 map，那么將拋出 ConcurrentModificationException宣蠕，這就是所謂 fail-fast 策略例隆。
引申擴(kuò)展：建議用 ConcurrentHashMap 代替 Hashtable。
為什么 HashTable 的默認(rèn)大小和 HashMap 不一樣抢蚀？
前面分析了镀层，Hashtable 的擴(kuò)容方法是乘 2 再 + 1，不是簡(jiǎn)單的乘 2皿曲，故 hashtable 保證了容量永遠(yuǎn)是奇數(shù)唱逢，結(jié)合之前分析 hashmap 的重算 hash 值的邏輯，就明白了谷饿，因?yàn)樵跀?shù)據(jù)分布在等差數(shù)據(jù)集合 (如偶數(shù)) 上時(shí)惶我，如果公差與桶容量有公約數(shù) n，則至少有 (n-1)/n 數(shù)量的桶是利用不到的博投，故之前的 hashmap 會(huì)在取模（使用位與運(yùn)算代替）哈希前先做一次哈希運(yùn)算绸贡，調(diào)整 hash 值。這里 hashtable 比較古老毅哗，直接使用了除留余數(shù)法听怕，那么就需要設(shè)置容量起碼不是偶數(shù)（除（近似）質(zhì)數(shù)求余的分散效果好）。而 JDK 開(kāi)發(fā)者選了 11虑绵。
參考資料
Java 8 系列之重新認(rèn)識(shí) HashMap - 美團(tuán)點(diǎn)評(píng)技術(shù)團(tuán)隊(duì)
通過(guò) HashMap尿瞭、HashSet 的源代碼分析其 Hash 存儲(chǔ)機(jī)制
HashMap 源碼分析
通過(guò)分析 JDK 源代碼研究 Hash 存儲(chǔ)機(jī)制
HashMap 深度分析
HashMap 源碼分析
HashMap 源碼分析
對(duì)比 HashMap 在 Java8 和 Java7 的源碼實(shí)現(xiàn)
深入理解 Java 之 HashMap 源碼解析
Java HashMap 源碼解析
JAVA 源碼分析 - HashMap 源碼分析 (一)
Java HashMap 工作原理及實(shí)現(xiàn)
遲到一年 HashMap 解讀
HashMap 實(shí)現(xiàn)原理分析
(轉(zhuǎn))Java HashMap 的死循環(huán)
【算法導(dǎo)論】紅黑樹(shù)詳解之一 (插入)
Hashes 10 Rehashing
