感謝 shixinzhang的文章, 參考此:?https://blog.csdn.net/u011240877/article/details/53351188 文章
一. HashMap的12個(gè)成員變量含義:
/**
* 初始容量為16
*/
static final int DEFAULT_INITIAL_CAPACITY =1 <<4; // aka 16
/**
* 最大容量為2的三十次方
*/
static final int MAXIMUM_CAPACITY =1 <<30;
/**
* 加載因子: 0.75f
* 分成四等份, 0.25 , 0.25 * 3 = 0.75, 在容量3/4時(shí)(0.75)進(jìn)行擴(kuò)容
*/
static final float DEFAULT_LOAD_FACTOR =0.75f;
/**
* 1. 當(dāng)前槽位Entry（也就是Node節(jié)點(diǎn)數(shù) >= TREEIFY_THRESHOLD此值, 并且當(dāng)前table數(shù)組的長(zhǎng)度 >= MIN_TREEIFY_CAPACITY, 則將鏈表轉(zhuǎn)成紅黑樹(shù).
* 2. 當(dāng)前槽位Entry（也就是Node）節(jié)點(diǎn)數(shù) >=TREEIFY_THRESHOLD, ?并且當(dāng)前table數(shù)組的長(zhǎng)度 < MIN_TREEIFY_CAPACITY, 則進(jìn)行擴(kuò)容,不發(fā)生樹(shù)化
*/
static final int TREEIFY_THRESHOLD =8;
/**
* 當(dāng)前槽位Entry（也就是Node）節(jié)點(diǎn)數(shù)小于等于6時(shí), 由紅黑樹(shù)轉(zhuǎn)成鏈表
*/
static final int UNTREEIFY_THRESHOLD =6;
/**
* 最小的元素容量, 結(jié)合?TREEIFY_THRESHOLD 使用, 判斷什么轉(zhuǎn)成樹(shù)和擴(kuò)容
*/
static final int MIN_TREEIFY_CAPACITY =64;
/**
*哈希表中的鏈表數(shù)組
*/
transient Node[] table;
/**
*鍵值對(duì)集合
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 鍵值對(duì)
*/
transient int size;
/**
*?當(dāng)前 HashMap 修改的次數(shù)座哩，這個(gè)變量用來(lái)保證?fail-fast?機(jī)制
fail-fast?機(jī)制 :?https://blog.csdn.net/zymx14/article/details/78394464
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
* 閾值, 下一次擴(kuò)容的值（容量*負(fù)載系數(shù)）
int threshold;
/**
* 哈希表的加載因子
*/
final float loadFactor;
HashMap本身就是Entry數(shù)組兜粘，每個(gè)槽位就是第一個(gè)Entry節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)就是由前一個(gè) next指向下一個(gè)節(jié)點(diǎn)寒砖， 所以同一個(gè)鏈表的hash相同
二.?HashMap 的初始容量和加載因子
由于 HashMap 擴(kuò)容開(kāi)銷很大（需要?jiǎng)?chuàng)建新數(shù)組唆涝、重新哈希、分配等等），因此與擴(kuò)容相關(guān)的兩個(gè)因素：
????1.容量：數(shù)組的數(shù)量
? ? 2. 加載因子：決定了 HashMap 中的元素占有多少比例時(shí)擴(kuò)容
成為了 HashMap 最重要的部分之一明刷，它們決定了 HashMap 什么時(shí)候擴(kuò)容。
HashMap 的默認(rèn)加載因子為 0.75满粗，這是在時(shí)間辈末、空間兩方面均衡考慮下的結(jié)果：
????1. 加載因子太大的話發(fā)生沖突的可能就會(huì)大，查找的效率反而變低
????2. 太小的話頻繁 rehash映皆，導(dǎo)致性能降低
當(dāng)設(shè)置初始容量時(shí)挤聘，需要提前考慮 Map 中可能有多少對(duì)鍵值對(duì)，設(shè)計(jì)合理的加載因子捅彻，盡可能避免進(jìn)行擴(kuò)容组去。
如果存儲(chǔ)的鍵值對(duì)很多，干脆設(shè)置個(gè)大點(diǎn)的容量步淹，這樣可以少擴(kuò)容幾次从隆。
三. HashMap四個(gè)構(gòu)造方法
? ? 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;
? ? ? ? //根據(jù)指定容量設(shè)置閾值
? ? ? ? this.threshold = tableSizeFor(initialCapacity);
? ? }
// 這個(gè)閾值經(jīng)過(guò)?無(wú)符號(hào)右移、求異運(yùn)算;
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;
}
? ? public HashMap(int initialCapacity) {
? ? ? ? this(initialCapacity, DEFAULT_LOAD_FACTOR);
? ? }
? ? public HashMap() {
? ? ? ? this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
? ? }
? ? public HashMap(Map<? extends K, ? extends V> m) {
? ? ? ? this.loadFactor = DEFAULT_LOAD_FACTOR;
? ? ? ? putMapEntries(m, false);
? ? }
/**
* 向哈希表中添加整個(gè)集合
*/
final void putMapEntries(Map 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);
? ? ? ? }
// 數(shù)組不為空, 超過(guò)閾值,則進(jìn)行擴(kuò)容
? ? ? ? else if (s > threshold)
resize();
? ? ? ? for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
? ? ? ? ? ? V value = e.getValue();
? ? ? ? ? ? // copy添加集合的值
? ? ? ? ? ? putVal(hash(key), key, value, false, evict);
? ? ? ? }
}
}
五.? 鏈表節(jié)點(diǎn)Node
static class Nodeimplements Map.Entry {
final int hash; // 哈希值,
? ? final K key; // 鍵
? ? V value; // 值
? ? Node next; // 指向下一個(gè)node
? ? Node(int hash, K key, V value, Node next) {
this.hash = hash;
? ? ? ? this.key = key;
? ? ? ? this.value = value;
? ? ? ? this.next = next;
? ? }
public final K getKey()? ? ? ? {return key; }
public final V getValue()? ? ? {return value; }
public final String toString() {return key +"=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
? ? }
public final V setValue(V newValue) {
V oldValue = value;
? ? ? ? value = newValue;
? ? ? ? return oldValue;
? ? }
public final boolean equals(Object o) {
if (o ==this)
return true;
? ? ? ? if (oinstanceof Map.Entry) {
//? Map.Entry 相等的條件: 鍵相等, 值相等, 個(gè)數(shù)相等, 順序相等.
? ? ? ? ? ? Map.Entry e = (Map.Entry)o;
? ? ? ? ? ? if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
? ? ? ? }
return false;
? ? }
}
六. putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
? ? ? ? ? ? ? boolean evict) {
// 如果當(dāng)前table為空, 則新建; n:指向最后一個(gè)桶的位置; tab: 新哈希表
? ? Node[] tab; Node p; int n, i;
? ? if ((tab = table) ==null || (n = tab.length) ==0)
n = (tab = resize()).length;
? ? // 如果要插入的位置沒(méi)有元素, 新建個(gè)節(jié)點(diǎn)放進(jìn)去
? ? if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value, null);
? ? else {
// 如果要插入的桶已經(jīng)有元素,替換
// e : 指向被替換的元素
? ? ? ? Node e; K k;
? ? ? ? if (p.hash == hash &&
((k = p.key) == key || (key !=null && key.equals(k))))
// p: 指向要插入的桶第一個(gè)元素的位置, 如果p 的哈希值,鍵,值和要添加的一樣, 就停止找, e指向p;
? ? ? ? ? ? e = p;
? ? ? ? else if (pinstanceof TreeNode)
// 如果桶第一個(gè)元素是樹(shù)形node, 則在樹(shù)中插入
? ? ? ? ? ? e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
? ? ? ? else {
// 進(jìn)行鏈表查找,替換
? ? ? ? ? ? for (int binCount =0; ; ++binCount) {
// 如果下個(gè)元素為空, 則插入后面
? ? ? ? ? ? ? ? if ((e = p.next) ==null) {
p.next = newNode(hash, key, value, null);
? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD -1)// -1 for 1st
// 當(dāng)這個(gè)桶內(nèi)鏈表個(gè)數(shù)大于等于8, 就要樹(shù)形化
? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
break;
? ? ? ? ? ? ? ? }
// 如果找到要替換的節(jié)點(diǎn), 就停止,
? ? ? ? ? ? ? ? if (e.hash == hash &&
((k = e.key) == key || (key !=null && key.equals(k))))
break;
? ? ? ? ? ? ? ? p = e;
? ? ? ? ? ? }
}
// 存在要替換的節(jié)點(diǎn)
? ? ? ? if (e !=null) {// existing mapping for key
? ? ? ? ? ? V oldValue = e.value;
? ? ? ? ? ? // 替換, 返回
? ? ? ? ? ? if (!onlyIfAbsent || oldValue ==null)
e.value = value;
? ? ? ? ? ? afterNodeAccess(e);
? ? ? ? ? ? return oldValue;
? ? ? ? }
}
++modCount;
? ? // 如果超過(guò)閾值, 擴(kuò)容
? ? if (++size > threshold)
resize();
? ? afterNodeInsertion(evict);
return null;
}
添加方法的邏輯概括為:
七.? 計(jì)算hash()方法
static final int hash(Object key) {
? ? int h;
? ? return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 右移位是去掉低位, 然后異或之后, 高低位結(jié)合, 減少碰撞率;
八.resize() 擴(kuò)容方法
當(dāng)集合所有元素 > threshold 時(shí);
final Node[] resize() {
// 復(fù)制一份當(dāng)前的數(shù)據(jù)
? ? Node[] oldTab = table;
? ? // 保存舊的元素個(gè)數(shù), 閾值
? ? int oldCap = (oldTab ==null) ?0 : oldTab.length;
? ? int oldThr = threshold;
? ? int newCap, newThr =0;
? ? if (oldCap >0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
? ? ? ? ? ? return oldTab;
? ? ? ? }
// 新的容量為舊的兩部
? ? ? ? else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果舊容量大于等于16, 新的閾值就是舊閾值的兩倍
? ? ? ? ? ? newThr = oldThr <<1; // double threshold
? ? }
// 如果舊容量為0, 并且舊閾值>0,說(shuō)明之前創(chuàng)建了哈希表但沒(méi)有添加元素,初始化容量等于閾值
? ? else if (oldThr >0)// initial capacity was placed in threshold
? ? ? ? newCap = oldThr;
? ? else {// zero initial threshold signifies using defaults
// 舊容量,舊閾值都是0,說(shuō)明還沒(méi)有創(chuàng)建哈希表,容量為默認(rèn)容量,閾值為 容量*加載因子
? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;
? ? ? ? newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
? ? }
// 如果新的閾值為0, 就得用 新容量 * 加載因子
? ? if (newThr ==0) {
float ft = (float)newCap * loadFactor;
? ? ? ? newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
? ? }
// 更新閾值
? ? threshold = newThr;
? ? // 創(chuàng)建新鏈表數(shù)組, 容量是原來(lái)的兩倍
? ? @SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
? ? table = newTab;
? ? // 接下來(lái)就得遍歷復(fù)制了
? ? if (oldTab !=null) {
for (int j =0; j < oldCap; ++j) {
Node e;
? ? ? ? ? ? if ((e = oldTab[j]) !=null) {
// 舊的桶置為空
? ? ? ? ? ? ? ? oldTab[j] =null;
? ? ? ? ? ? ? ? // 當(dāng)前 桶只有一個(gè)元素, 直接賦值給對(duì)應(yīng)的位置
? ? ? ? ? ? ? ? if (e.next ==null)
newTab[e.hash & (newCap -1)] = e;
? ? ? ? ? ? ? ? else if (einstanceof TreeNode)
// 如果舊哈希表中這個(gè)位置的桶是樹(shù)形, 把新哈希表里當(dāng)前桶也變成樹(shù)形
? ? ? ? ? ? ? ? ? ? ((TreeNode)e).split(this, newTab, j, oldCap);
? ? ? ? ? ? ? ? else {// preserve order
// 保留舊哈希表桶中鏈表的順序
? ? ? ? ? ? ? ? ? ? Node loHead =null, loTail =null;
? ? ? ? ? ? ? ? ? ? Node hiHead =null, hiTail =null;
? ? ? ? ? ? ? ? ? ? Node next;
? ? ? ? ? ? ? ? ? ? do {
next = e.next;
? ? ? ? ? ? ? ? ? ? ? ? if ((e.hash & oldCap) ==0) {
if (loTail ==null)
loHead = e;
else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ? ? }
else {
if (hiTail ==null)
hiHead = e;
else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ? ? }
}while ((e = next) !=null);
? ? ? ? ? ? ? ? ? ? if (loTail !=null) {
loTail.next =null;
? ? ? ? ? ? ? ? ? ? ? ? newTab[j] = loHead;
? ? ? ? ? ? ? ? ? ? }
if (hiTail !=null) {
hiTail.next =null;
? ? ? ? ? ? ? ? ? ? ? ? newTab[j + oldCap] = hiHead;
? ? ? ? ? ? ? ? ? ? }
}
}
}
}
return newTab;
}
擴(kuò)容過(guò)程中幾個(gè)關(guān)鍵的點(diǎn)：
新初始化哈希表時(shí)缭裆，容量為默認(rèn)容量键闺，閾值為 容量*加載因子
已有哈希表擴(kuò)容時(shí)，容量澈驼、閾值均翻倍
如果之前這個(gè)桶的節(jié)點(diǎn)類型是樹(shù)辛燥，需要把新哈希表里當(dāng)前桶也變成樹(shù)形結(jié)構(gòu)
復(fù)制給新哈希表中需要重新索引（rehash），這里采用的計(jì)算方法是
e.hash & (newCap - 1)盅藻，等價(jià)于 e.hash % newCap
結(jié)合擴(kuò)容源碼可以發(fā)現(xiàn)擴(kuò)容的確開(kāi)銷很大购桑，需要迭代所有的元素，rehash氏淑、賦值勃蜘，還得保留原來(lái)的數(shù)據(jù)結(jié)構(gòu)。
所以在使用的時(shí)候假残，最好在初始化的時(shí)候就指定好 HashMap 的長(zhǎng)度缭贡，盡量避免頻繁 resize()。
