HashMap
HashMap存儲(chǔ)的時(shí)key-value格式的實(shí)例。
底層的存儲(chǔ)結(jié)構(gòu)是數(shù)組+鏈表格式。
單個(gè)實(shí)例的格式
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
一些成員變量
transient Node<K,V>[] table：底層存儲(chǔ)結(jié)構(gòu)
Set<Map.Entry<K,V>> entrySet：
size：記錄了當(dāng)前數(shù)量
threshold：臨界值threshold = capacity * loadFactor,當(dāng)size大于臨界值就要擴(kuò)容
loadFactor：負(fù)載因子，衡量HashMap滿的程度，默認(rèn)0.75f
還有一個(gè)capacity容量，不是成員變量，但很重要。
新建HashMap
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
無參構(gòu)造函數(shù)，在第一次put數(shù)據(jù)的時(shí)候會(huì)進(jìn)行擴(kuò)容。
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
上述構(gòu)造函數(shù)新建時(shí)，并沒有新建數(shù)組，對于前2個(gè)，只是設(shè)置了負(fù)載因子和臨界值。
對于無參的構(gòu)造函數(shù)，在第一次put數(shù)據(jù)時(shí)才會(huì)設(shè)置負(fù)載因子和臨界值。
初始化數(shù)組都是在第一次put數(shù)據(jù)時(shí)。
存取原理
put方法
總體的流程就是，如果定位的table[index]為null，直接插入，如果index的key和要插入的相等（地址或者equals）那直接覆蓋。如果不是就鏈表或紅黑樹遍歷，遍歷完再走上面流程。
- 通過hash函數(shù)計(jì)算存儲(chǔ)位置
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- 判斷table是否為null或長度為0，如果是，調(diào)用resize()方法進(jìn)行擴(kuò)容
- 如果tabel[i]為null，直接構(gòu)造Node插入
- 如果tabel[i]不為null 判斷key是否等于index處對應(yīng)的key，如果相等或者equals方法相等，直接覆蓋。
- 否則如果是紅黑樹，插入
- 鏈表的話判斷長度是否大于等于8，是的話變?yōu)榧t黑樹插入，否則鏈表 插入。
get方法
- table為null，返回null
- 計(jì)算hash值，定位到index，判斷key是否相等或者equals是否相等，如果相等返回
- 否則遍歷，如果是TreeNode紅黑樹，如果是鏈表，鏈表遍歷。
為什么需要負(fù)載因子：
因?yàn)閙ap映射需要進(jìn)行hash，如果負(fù)載因子是1的話，hash沖突概率變大。0.75是個(gè)經(jīng)驗(yàn)值。
如果小了，空間利用率低，如果大了，鏈表長度過長或者紅黑樹高度過高。
默認(rèn)長度為啥是16
經(jīng)驗(yàn)值，保證是2的次冪就行（1 << 4; // aka 16）
為什么capatity大小都是2的冪？(真正的大小)
為了使用二進(jìn)制完成取模運(yùn)行，不用做進(jìn)制轉(zhuǎn)換，效率高。
hash函數(shù)
初始的閾值計(jì)算。
this.threshold = tableSizeFor(initialCapacity);
該方法是找到第一個(gè)比capacity大的2的次冪。
hash函數(shù)的原理還是取模
X % 2^n = X & (2^n – 1)
table中index的選擇方式：i = (n - 1) & hash
因此：只要保證length的長度是2^n 的話，就可以實(shí)現(xiàn)取模運(yùn)算了
擴(kuò)容方式
擴(kuò)容時(shí)機(jī)
第一次插入時(shí)擴(kuò)容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
容量不夠時(shí)擴(kuò)容
if (++size > threshold)
resize();
容量不足時(shí)擴(kuò)容的長度2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
擴(kuò)容是插入步驟：
- 新建一個(gè)2倍數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; - 重新計(jì)算index插入
newTab[e.hash & (newCap - 1)] = e;
頭插入尾插為啥形成環(huán)
頭插入的話，擴(kuò)容后，鏈表上實(shí)例的相對位置會(huì)發(fā)生變化。多線程環(huán)境下操作可能形成環(huán)。
線程安全相關(guān)
1.在jdk1.7中，在多線程環(huán)境下，擴(kuò)容時(shí)會(huì)造成環(huán)形鏈或數(shù)據(jù)丟失。
2.在jdk1.8中，在多線程環(huán)境下，會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。
