HashMap是一個由數(shù)組加鏈表（紅黑樹）組成的散列表低剔，可以非常方便的存儲KV數(shù)據(jù)，也可以插入K為null的信息，那么HashMap有哪些不足之處需要注意的呢襟齿？HashMap的擴(kuò)容機(jī)制又是如何姻锁；常見的put、get方法工作細(xì)節(jié)又是如何猜欺，帶著這一系列問題來學(xué)習(xí)一下JDK1.8里面的HashMap的源碼屋摔，了解其工作原理。
HashMap 構(gòu)造函數(shù)
HashMap get方法
HashMap put方法
HashMap resize方法
HashMap remove方法
HashMap 迭代器iterator
問題&總結(jié)
什么時候會創(chuàng)建table數(shù)組?
table數(shù)組長度可以為任意數(shù)字么替梨？
為什么table數(shù)組長度必須為2^n?
為什么默認(rèn)的負(fù)載因子0.75f钓试？
有什么缺點么？
先了解下HashMap中的幾個比較關(guān)鍵的成員變量副瀑，后續(xù)關(guān)于get和put的方法的細(xì)節(jié)都脫離不了這幾個參數(shù)的配合
// 默認(rèn)的HashMap table 數(shù)組大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 數(shù)組最大值弓熏，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)的負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表轉(zhuǎn)換為紅黑樹的節(jié)點最小個數(shù)（當(dāng)鏈表長度大于等于8時會從鏈表轉(zhuǎn)變?yōu)榧t黑樹）
static final int TREEIFY_THRESHOLD = 8;
// 紅黑樹經(jīng)過remove后節(jié)點個數(shù)小于等于該值時 從紅黑樹蛻變?yōu)殒湵?static final int UNTREEIFY_THRESHOLD = 6;
// HashMap的數(shù)組，是Node類型的糠睡，初始值為null
transient Node<K,V>[] table;
// 在迭代器中使用挽鞠，可依次遍歷Hashmap的節(jié)點
transient Set<Map.Entry<K,V>> entrySet;
// HashMap的節(jié)點個數(shù)
transient int size;
// HashMap的修改次數(shù)，主要用在fail-fast中
transient int modCount;
// HashMap閥值狈孔，當(dāng)size超過閥值時進(jìn)行擴(kuò)容操作信认，一般情況下閥值 = 數(shù)組的長度 * 負(fù)載因子
int threshold;
// 負(fù)載因子，默認(rèn)是0.75f均抽，可以認(rèn)為是限制HashMap的碰撞因子
final float loadFactor;
HashMap 構(gòu)造函數(shù)
public HashMap(int initialCapacity, float loadFactor) {
// 傳入默認(rèn)初始化的容量大小參數(shù)
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
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
// 同樣是傳入了自定義的容量大小以及默認(rèn)負(fù)載因子
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 所有的信息都是默認(rèn)的嫁赏，加載因子設(shè)置為0.75f
}
這有個疑問，initialCapacity 參數(shù)一般是當(dāng)做HashMap的初始化大小使用油挥，可是細(xì)看代碼得之并沒有設(shè)置成table的初始長度潦蝇，反而是通過tableSizeFor方法計算table默認(rèn)的閥值threshold的值
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;
}
>>> 含義是無符號的右移深寥，那么這整個函數(shù)的作用是什么呢？現(xiàn)在假設(shè)n對應(yīng)的二進(jìn)制是1XXX XXXX
右移動1位惋鹅，則有01XX XXXX,進(jìn)行一次異或運算 得到 11XX XXXX
再移動2位，則有0011 11XX,進(jìn)行一次異或運算 得到 1111 11XX
再移動4位闰集，則有0000 1111,進(jìn)行一次異或運算 得到 1111 1111
現(xiàn)在看下經(jīng)過了1，2妥泉，4三個運算，就相當(dāng)于把當(dāng)前已知最大的1右邊的1 + 2 + 4位全部改成了1盲链，變成了最大值
所以現(xiàn)在這幾次異或運算就是把當(dāng)前二進(jìn)制位最大的1右邊的0全部改成1(因為移動了1 + 2 + 4 + 8 + 16 = 31位)，現(xiàn)在計算出來的n就是0000 0000 0001 1111這種格式的數(shù)據(jù)刽沾，再進(jìn)行加一操作也就成為了 0010 0000（是個偶數(shù)）本慕，現(xiàn)在假設(shè)傳入了的cap=12，那么就是1100侧漓，經(jīng)過異或運算就變成了1111锅尘，再+1處理就成為了 0001 0000，也就是16布蔗。所以現(xiàn)在知道了其實這個方法就是為了計算出比傳入數(shù)據(jù)大且最接近的2^n的數(shù)組
那么還有一個問題藤违，為什么一開始減1呢？其實是為了處理當(dāng)cap=0的情況纵揍，當(dāng)cap=0時顿乒，計算的數(shù)據(jù)為1，同樣滿足1 = 2^0且大于0的結(jié)論
所以如果傳入了initialCapacity泽谨，threshold閥值一定會是2^n這種數(shù)據(jù)的
調(diào)用HashMap()方法璧榄，則閥值和容量都是0
調(diào)用HashMap(initialCapacity) 方法，則賦值閥值吧雹，容量為0
當(dāng)然這里還是沒有解釋上面的一個疑問「table的長度到底是多少」骨杂，繼續(xù)往下看
HashMap get方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// 隱含了當(dāng)key為null的時候返回0這種情況
// 剩下的都是hash的高16位和低16位進(jìn)行異或運算，其原因也是為了降低hash沖突
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
// 如果tab不為null雄卷，而且長度>0搓蚪，再甚至數(shù)組偏移量的節(jié)點first不為null
// 偏移量是通過(tab.length - 1)&hash計算出來的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 當(dāng)前first節(jié)點如果K值一樣，直接返回
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 紅黑樹龙亲，查詢紅黑樹的節(jié)點信息
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
// 依次遍歷陕凹，計算hash值一樣，且Key一樣的節(jié)點
} while ((e = e.next) != null);
}
}
return null;
}
需要關(guān)注一下鳄炉，在定位數(shù)組的偏移量是采用了(tab.length - 1)&hash計算的,因為tab.length = 2^n，那么一定可以確保偏移量在數(shù)組之內(nèi)
HashMap put方法
public V put(K key, V value) {
// 先計算hash值搜骡，然后調(diào)用putVal方法
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 如果table為null或者table長度為0拂盯，需要進(jìn)行重置table操作（后面再說resize方法）
// 初始化時，table為null记靡，也是一種Lazy的思想
n = (tab = resize()).length;
// 現(xiàn)在table是有一定長度的數(shù)組，而且長度為2^n
// 定位數(shù)字的索引 (n-1) & hash
// 01111 1111 和hash值的和運算
if ((p = tab[i = (n - 1) & hash]) == null)
// 數(shù)組上節(jié)點為null空凸，表示沒有數(shù)據(jù)寸痢，直接創(chuàng)建一個新節(jié)點設(shè)置好就可以了
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 此時節(jié)點p是數(shù)組有值的節(jié)點，也可以是鏈表(紅黑樹)的首節(jié)點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// hash值一樣兵罢，key值也一樣卖词，那就相當(dāng)于發(fā)現(xiàn)了K一樣的情況
e = p;
else if (p instanceof TreeNode)
// p節(jié)點是樹節(jié)點的類型吏夯，添加到紅黑樹中去
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 遍歷鏈表的節(jié)點
if ((e = p.next) == null) {
// 遍歷到最后一個節(jié)點了噪生，肯定為null
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 記住binCount是從0開始計數(shù)的，所以這里是TREEIFY_THRESHOLD - 1 = 7
// 當(dāng)鏈表節(jié)點數(shù)目大于等于8顾瞪，則會轉(zhuǎn)變成紅黑樹
treeifyBin(tab, hash);
break;
// 鏈表執(zhí)行完了肯定就退出循環(huán)
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 鏈表遍歷中發(fā)現(xiàn)了同樣的K值節(jié)點
break;
p = e;
// 否則繼續(xù)遍歷
}
}
if (e != null) {
// 如果找到了同樣的K的節(jié)點信息
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 替換老的Value信息
e.value = value;
afterNodeAccess(e);
return oldValue;
// 返回舊的Value信息
}
}
// 到這里來的都算需要往Map中添加新節(jié)點的
// 所以modCount + 1操作
++modCount;
if (++size > threshold)
// HashMap的節(jié)點大小個數(shù)超過了閥值陈醒，調(diào)用resize
resize();
afterNodeInsertion(evict);
// 新增節(jié)點钉跷，肯定就沒有舊節(jié)點信息爷辙，返回null完事
return null;
}
整個流程只是需要注意resize()方法朦促，當(dāng)table還未初始化和當(dāng)前的HashMap節(jié)點數(shù)超過閥值時就會調(diào)用resize進(jìn)行擴(kuò)容操作务冕，那么現(xiàn)在就來看下resize方法
HashMap resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 在初次調(diào)用put時禀忆，table就是null，設(shè)定oldCap = 0离熏，否則就是舊table的長度
int oldThr = threshold;
// 舊閥值oldThr
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果老的table長度大于0
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果數(shù)組長度大于等于容量最大值滋戳，只會修改閥值大小，不進(jìn)行擴(kuò)容操作
// 即使發(fā)生碰撞情況也不再考慮
// 換句話說矢棚，在Map裝入了如此多的數(shù)據(jù)也不太合理吧
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的table容量翻倍處理
// 如果oldCap * 2 小于最大容量 而且 oldCap 超過默認(rèn)16個容量大小府喳，新的閥值也會翻倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 調(diào)用了HashMap(int, float) 的構(gòu)造方法的初始情況
// 舊table的長度為0 且 舊閥值大于0（可以理解為初始情況）
// 而且新閥值這個時候依舊等于0钝满，無變化
// 注意這點弯蚜！新的table長度是舊的閥值，而之前已經(jīng)說了閥值數(shù)據(jù)是2^n路鹰，直接賦值給了table
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 調(diào)用了HashMap()的構(gòu)造方法的初始情況
newCap = DEFAULT_INITIAL_CAPACITY;
// 新的默認(rèn)table長度是16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
// 新的閥值 = 16 * 0.75晋柱，這里才是之前一直所說的閥值=0.75的容量情況
}
// 新的閥值為0诵叁，只有oldThr > 0 這一種情況下才有可能
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
// 對閥值進(jìn)行重新計算操作
}
threshold = newThr;
// 所以才有了常說的 閥值 = 0.75 * table長度
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 新創(chuàng)建了一個新容量的newTab拧额，接下來就是開始拷貝搬遷舊table的數(shù)據(jù)了
table = newTab;
if (oldTab != null) {
// 舊table有過值的情況下侥锦，依次開始遍歷操作
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果該節(jié)點沒有外接鏈表或者紅黑樹，直接重新計算偏移量賦值即可
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 樹節(jié)點的重新切割處理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 開始處理鏈表了泪幌，此時e節(jié)點還未處理
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 按照和運算 是否為0進(jìn)行拆分
if (loTail == null)
// 當(dāng)前e節(jié)點賦值給loHead
loHead = e;
else
loTail.next = e;
// loTail也賦值給了e節(jié)點
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 經(jīng)過上面的while循環(huán)處理，就是相當(dāng)于把節(jié)點hash是否為0拆分為2種情況
// 各自由一個鏈表負(fù)責(zé)建芙，采用的尾插法
if (loTail != null) {
// 和運算為0的情況禁荸，直接掛載在原偏移量節(jié)點下
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 否則，掛載在j + oldCap 的節(jié)點下
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize方法整體而言還是比較復(fù)雜的瑰妄，涉及到了的調(diào)用場景有無參構(gòu)造映砖、有參構(gòu)造邑退、正常擴(kuò)容等三種情況，所以也就有了開頭比較復(fù)雜的新容量大小以及新閥值的計算行為蜈七。
無參構(gòu)造：新容量是默認(rèn)容量值16飒硅，新閥值是默認(rèn)容量值16 * 負(fù)載因子0.75 = 12
有參構(gòu)造：新容量是由傳入的initialCapacity數(shù)據(jù)計算出大且最近的2^n的值作谚，新閥值是新容量 * 0.75（如果新容量值或者新閥值超過了 最大的容量值，修正新閥值為Integer.MAX_VALUE）
正常擴(kuò)容：舊容量大于等于最大容量值尽棕，設(shè)置新閥值為Integer.MAX_VALUE滔悉，結(jié)束擴(kuò)容单绑；否則新容量double操作（有一些信息被忽略了）
再來細(xì)說一下e.hash & oldCap) == 0這個判斷邏輯搂橙，我們知道table的數(shù)組偏移量的計算是通過hash & (oldCap-1)得到的，既然是在同一個鏈表中苔巨，則其結(jié)果是相同的侄泽，又因為oldCap = 2^n蜻韭，所以意味著不同的節(jié)點Node1和Node2 的hash值必然存在著后幾位為1的bit一定相等的情況（和此處邏輯無關(guān)緊要），例如如下結(jié)果做和運算
Node1 0101 1010
Node2 0001 1010
len-1 0000 1111
table 0001 0000
這兩個節(jié)點后四位一定會相同的闺魏，所以也就是看table二進(jìn)制為1的那1bit和節(jié)點相對應(yīng)的那1bit的和運算是否為0進(jìn)行拆分，這樣可盡可能進(jìn)行均等拆分司草，降低hash沖突翻伺，提高效率沮焕。
HashMap remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
// 找到了待移除的節(jié)點e峦树，返回其value，否則返回null
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// matchValue 為true時會比對找到的節(jié)點和傳入的Value 值
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) {
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);
}
}
// 上面就不再細(xì)說了急灭，就是找到待移除的節(jié)點node
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果node節(jié)點不為null 而且
// 1葬馋、無需匹配Value 值
// 2畴嘶、需要匹配且value值確實相同
// 上述1 和 2 是或的關(guān)系
if (node instanceof TreeNode)
// 樹節(jié)點的移除方法
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// node和p相同就意味著node節(jié)點是table上的窗悯，直接把node的next賦值給table即可
tab[index] = node.next;
else
// p節(jié)點是node節(jié)點的前節(jié)點
// 直接把node的next賦值給p的next節(jié)點
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
// hashmap的修改次數(shù)+1偷拔，size減一操作，然后返回node節(jié)點
return node;
}
}
return null;
}
這里有個小點需要注意到在鏈表的首節(jié)點(也是table上)和鏈表中的節(jié)點移除邏輯是不一樣的欺旧，鏈表中需要知道其移除節(jié)點的上一個節(jié)點切端，而首節(jié)點則沒有上一個節(jié)點這種說法顷啼，直接把下一個節(jié)點賦值給table就行了
HashMap 迭代器iterator
HashMap在遍歷輸出時钙蒙，經(jīng)常使用到迭代器Iterator，常見的代碼如下
在JDK1.8中有一個
forEach(BiConsumer<? super K, ? super V> action)也可以很方便的處理HashMap
Map<String, String> map = new HashMap<>();
map.put("1111", "2222");
map.put("2222", "44444");
map.put("3333", "66666");
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry entry = iterator.next();
System.out.print("key:" + entry.getKey() + ", value: " + entry.getValue());
}
獲取EntrySet迭代器马昨，然后利用hasNext以及next方法獲取具體的值鸿捧，代碼很簡單疙渣，看看HashMap如何實現(xiàn)其步驟的
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
// 沒做什么只是直接創(chuàng)建了一個新的EntrySet對象
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
// 調(diào)用EntrySet的iterator也是啥都沒做妄荔，返回了一個EntryIterator新對象，使用的是無參構(gòu)造
return new EntryIterator();
}
.....
}
那現(xiàn)在來看看EntryIterator類到底干了什么
// Hash迭代器抽象類
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
// 記錄下了當(dāng)前的修改次數(shù)哗伯，用于快速失敗
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) {
// 空轉(zhuǎn)焊刹，從數(shù)組的第一個開始遍歷恳蹲，直到節(jié)點不為null為止阱缓，記錄下index和next
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
// 就是看下一個節(jié)點next是否為null
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
// 在迭代期間hashmap經(jīng)歷了修改操作，直接拋出異常
throw new ConcurrentModificationException();
if (e == null)
// 意味著必須先調(diào)用hasNext敞嗡，通過后才可調(diào)用nextNode
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
// 把當(dāng)前處理的節(jié)點賦值給current丰榴，開始遍歷鏈表
// 直到鏈表的下一個節(jié)點為null時（也就意味著鏈表遍歷完成），需要進(jìn)入到下一個table節(jié)點遍歷
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
// 移除節(jié)點信息，同時賦值新的修改次數(shù)給expectedModCount
// 也就意味著如果想在迭代中移除節(jié)點勺像，只能通過remove方法
expectedModCount = modCount;
}
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
// 繼承了HashIterator 實現(xiàn)了迭代器的接口
public final Map.Entry<K,V> next() { return nextNode(); }
}
整個的迭代過程也是很清晰的，先預(yù)處理遍歷table找到第一個不為null的節(jié)點吟宦，后面遍歷該節(jié)點的next值殃姓，直到為null也就意味著該節(jié)點的鏈表(紅黑樹)遍歷完成，繼續(xù)遍歷table下一個節(jié)點篷牌。
問題&總結(jié)
什么時候會創(chuàng)建table數(shù)組踏幻？
HashMap使用的Lazy模式叫倍，初始化時不會創(chuàng)建table，而是直到put數(shù)據(jù)時才會創(chuàng)建table數(shù)組
table數(shù)組長度可以為任意數(shù)字么听诸？
不可以蚕泽，通過tableSizeFor方法，
一定會修正使得table的length為2^n仔蝌，所以new HashMap(12) 和new HashMap(13)其實是一樣的含義敛惊，最后length都會被修正為16
建議給新建的HashMap賦予一定的初始值绰更，減少不必要的擴(kuò)容操作，損耗性能
為什么默認(rèn)的負(fù)載因子0.75f特恬？
這個點在HashMap的源碼描述中已經(jīng)介紹了癌刽，hash的值是遵循
泊松分布，當(dāng)負(fù)載因子為0.75時衡奥，碰撞出現(xiàn)鏈表長度大于等于8個情況概率小于1/1kw讼油，也恰好說明了為什么鏈表轉(zhuǎn)為紅黑樹的節(jié)點個數(shù)為8，當(dāng)真正出現(xiàn)紅黑樹也說明了hash碰撞比較嚴(yán)重，所以使用紅黑樹提高效率
至于為什么是泊松分布就涉及到概率統(tǒng)計學(xué)了瘦赫，可以翻翻相關(guān)的paper
這個0.75也無絕對蛤迎，只是針對大部分場景比較適用，也是對空間和時間的一種妥協(xié)校辩，如果你能嚴(yán)格證明0.8甚至0.9可以提高自身業(yè)務(wù)的效率辆童，也是可以傳入自定義的負(fù)載因子
為什么table數(shù)組長度必須為2^n?
進(jìn)行數(shù)組偏移量計算時把鉴，采用的是(n-1) & hash，n-1又是0001111 類似尾部全部為1的情況场晶，使得計算出來的值一定在table的長度范圍之內(nèi)
位運算 比 常見的取模速度快
(n-1) & hash也就說明了真正有作用的是hash值的后幾位數(shù)字怠缸，而hash的值hashcode ^ (hashcode >> 16) 低16位和高16位做異或運算得到的，意味著hash后幾位數(shù)字由hashcode高低位共同決定扳炬，這也進(jìn)一步的降低hash碰撞
有什么缺點么罐呼？
在JDK1.7中在高并發(fā)場景下擴(kuò)容機(jī)制會出現(xiàn)鏈表循環(huán)的情況（主要是頭插法導(dǎo)致），使得CPU負(fù)載達(dá)到100%厌杜，不過在JDK1.8中已經(jīng)不存在該問題了
線程不安全，無鎖控制瞧壮，也不能控制活躍性問題咆槽，也無法解決發(fā)布安全的問題圈纺，那么該如何解決呢？
擴(kuò)容存在潛在的OOM的情況灯谣，例如當(dāng)前1G的空間已經(jīng)使用了800M蛔琅，再經(jīng)過擴(kuò)容之后就會出現(xiàn)OOM的場景，這樣進(jìn)一步說明了必須預(yù)估業(yè)務(wù)場景的容量大小辜窑，并一次性賦值到位穆碎，減少無所謂的擴(kuò)容操作
