構(gòu)造方法
HashMap提供了三個(gè)構(gòu)造函數(shù)
HashMap()：構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap。
下面是所有的屬性
/**
* 默認(rèn)的初始容量：16
* 必須為2的冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量為2的 30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)加載因子0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*一個(gè)桶中bin（箱子）的存儲(chǔ)方式由鏈表轉(zhuǎn)換成樹的閾值
*當(dāng)桶上的結(jié)點(diǎn)數(shù)量大于等于TREEIFY_THRESHOLD時(shí)底層結(jié)構(gòu)由鏈表變?yōu)榧t黑樹。默認(rèn)是8
*/
static final int TREEIFY_THRESHOLD = 8;
/**
*當(dāng)桶上的結(jié)點(diǎn)數(shù)量小于等于6時(shí)等層結(jié)構(gòu)由紅黑樹變?yōu)殒湵?。默認(rèn)是6
*當(dāng)執(zhí)行resize操作時(shí)，當(dāng)桶中bin的數(shù)量少于6時(shí)使用鏈表來代替樹
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
*當(dāng)桶中的bin被樹化時(shí)最小的hash表容量。（如果沒有達(dá)到這個(gè)閾值，即hash表容量小于MIN_TREEIFY_CAPACITY，當(dāng)桶中bin的數(shù)量太多時(shí)
*會(huì)執(zhí)行resize擴(kuò)容操作）這個(gè)MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD(鏈表轉(zhuǎn)化為紅黑樹的閥值)的4倍。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Entry數(shù)組，哈希表，長(zhǎng)度必須為2的冪
*/
transient Entry<K,V>[] table;
/**
* 已存元素的個(gè)數(shù)
*/
transient int size;
/**
* 下次擴(kuò)容的臨界值，size >= threshold就會(huì)擴(kuò)容
*/
int threshold;
/**
* 加載因子
*/
final float loadFactor;
數(shù)據(jù)結(jié)構(gòu)
HashMap的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表。當(dāng)鏈表長(zhǎng)度達(dá)到8時(shí)（binCount >= TREEIFY_THRESHOLD - 1），就轉(zhuǎn)化為紅黑樹（JDK1.8增加了紅黑樹部分）
哈希桶數(shù)組
里面有個(gè)屬性next，是個(gè)節(jié)點(diǎn)類型，根據(jù)構(gòu)造函數(shù)傳進(jìn)來的。他對(duì)上面那個(gè)鏈表的形成很重要。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用來定位數(shù)組索引位置
final K key;
V value;
Node<K,V> next; //鏈表的下一個(gè)node
Node(int hash, K key, V value, Node<K,V> next) {.....} //初始化四個(gè)屬性
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() { //返回hashcode
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) { //更改value值，并返回oldvalue
V oldValue = value;
value = newValue;
return oldValue;
}
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;
}
}
HashMap就是使用哈希表來存儲(chǔ)的。哈希表為解決沖突，可以采用開放地址法和鏈地址法等來解決問題，Java中HashMap采用了鏈地址法。鏈地址法，簡(jiǎn)單來說，就是數(shù)組加鏈表的結(jié)合。在每個(gè)數(shù)組元素上都一個(gè)鏈表結(jié)構(gòu)，當(dāng)數(shù)據(jù)被Hash后，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對(duì)應(yīng)下標(biāo)元素的鏈表上。
功能實(shí)現(xiàn)
確定哈希桶數(shù)組索引
步驟1：獲取key的hashcode值
步驟2：高位運(yùn)算，通過hashcode值的高十六位異或低十六位得到hash值
public class Hash_IndexFor {
/**
* HashMap的hash算法
*/
private int hash(Object key){
/*if (key == null) return 0;
// 獲得key的hashcode值
int hashcode = key.hashCode();
// 高位運(yùn)算
int hash = hashcode ^(hashcode >>> 16); // 高16位與低十六位做異或運(yùn)算
return hash;*/
int h;
return key == null ? 0: (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 計(jì)算索引
* JDK1.8把它去掉了，但是在put方法中直接使用了，沒有單獨(dú)作為方法。
*
*/
private int indexFor(int hash, int length){
return hash & (length - 1);
}
}
分析put方法
public V put(K key, V value) {
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;
// 步驟1：判斷數(shù)組是否為null或者為空，否則進(jìn)行擴(kuò)容resize()操作，新建一個(gè)。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟2：通過key的hash值得到插入數(shù)組的索引i; 如果tab[i]處還沒有元素，直接新建一個(gè)節(jié)點(diǎn)放入數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null) // 這里注意：table[i]已經(jīng)賦給引用p了，后續(xù)操作會(huì)多次用到p
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步驟3：節(jié)點(diǎn)key存在，則直接覆蓋value。這里還有疑問，為什么要比較兩次，兩次操作作用有什么不同嗎？
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步驟4：判斷table[i]的處鏈表是否為紅黑樹。
else if (p instanceof TreeNode) // 這里注意：TreeNode繼承自LinkedList的內(nèi)部類Entry，而Entry又繼承自HashMap的內(nèi)部類Node，即TreeNode是Node的子類，故能進(jìn)行（p instanceof TreeNode）這樣的判斷。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步驟5：該鏈為鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表長(zhǎng)度 大于8 則轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍歷過程中，如果發(fā)現(xiàn)節(jié)點(diǎn)key存在，則直接覆蓋value。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步驟6：超過最大容量就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
擴(kuò)容機(jī)制
先分析JDK1.7的擴(kuò)容機(jī)制，會(huì)更容易理解JDK1.8的擴(kuò)容
什么時(shí)候擴(kuò)容
當(dāng)向容器添加元素的時(shí)候，會(huì)判斷當(dāng)前容器的元素個(gè)數(shù)，如果大于等于閾值的時(shí)候，就要自動(dòng)擴(kuò)容啦。
擴(kuò)容是怎么實(shí)現(xiàn)
就是重新計(jì)算容量，向HashMap對(duì)象里不停的添加元素，而當(dāng)HashMap對(duì)象內(nèi)部的數(shù)組無法裝載更多的元素時(shí)，對(duì)象就需要擴(kuò)大數(shù)組的長(zhǎng)度，以便能裝入更多的元素。當(dāng)然Java里的數(shù)組是無法自動(dòng)擴(kuò)容的，方法是使用一個(gè)新的數(shù)組代替已有的容量小的數(shù)組，就像我們用一個(gè)小桶裝水，如果想裝更多的水，就得換大水桶，再將小水桶中的水倒進(jìn)大水桶。
幾個(gè)重要的屬性
- loadFactor：負(fù)載因子
- Node<K,V>：鏈表節(jié)點(diǎn)，包含了key、value、hash、next指針?biāo)膫€(gè)元素
- table：Node<K,V>類型的數(shù)組，里面的元素是鏈表，用于存放元素的鍵和值
- threshold：閾值。決定了HashMap何時(shí)擴(kuò)容（達(dá)到閥值的3/4時(shí)就擴(kuò)），以及擴(kuò)容后的大小，一般等于table的大小乘以負(fù)載因子（0.75）
JDK1.7中的擴(kuò)容的具體實(shí)現(xiàn)方法（resize）
void resize(int newCapacity) { //傳入新的容量，原容量的兩倍
Entry[] oldTable = table; //引用擴(kuò)容前的Entry數(shù)組
int oldCapacity = oldTable.length;//原容量
if (oldCapacity == MAXIMUM_CAPACITY) { //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大容量了
threshold = Integer.MAX_VALUE; //修改閾值為（最大容量-1），這樣以后就不會(huì)擴(kuò)容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一個(gè)新的Entry數(shù)組
transfer(newTable); //注意?。簩?shù)據(jù)拷貝到新的數(shù)組里
table = newTable; //HashMap的table屬性引用指向新的Entry數(shù)組
threshold = (int) (newCapacity * loadFactor);//修改閾值
}
transfer()方法：
將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里
/*上面的resize方法中，調(diào)用了transfer(newTable)方法，將數(shù)據(jù)拷貝到一個(gè)更大的數(shù)組中*/
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了舊的Entry數(shù)組
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
Entry<K, V> e = src[j]; //取得舊Entry數(shù)組的每個(gè)元素
if (e != null) {
src[j] = null;//釋放舊Entry數(shù)組的對(duì)象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對(duì)象）
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); //注意?。褐匦掠?jì)算每個(gè)元素在數(shù)組中的位置
e.next = newTable[i];
newTable[i] = e; //頭插法，將新元素放到單鏈表的頭部。因?yàn)閚ewTable是數(shù)組加鏈表的形式，newTable[i]存放的是鏈表首節(jié)點(diǎn)的地址
e = next; //訪問下一個(gè)Entry鏈上的元素
} while (e != null);
}
}
}
JDK1.8的擴(kuò)容機(jī)制
resize()方法的注釋：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize()
初始化或者翻倍表的大小。如果表為null，則根據(jù)存放在threshold變量中的初始化capacity的值來分配table內(nèi)存（這個(gè)注釋說的很清楚，在實(shí)例化HashMap時(shí)，capacity其實(shí)是存放在了成員變量threshold中，注意，HashMap中沒有capacity這個(gè)成員變量）。如果表不為null，由于我們使用2的冪來擴(kuò)容，則每個(gè)bin（箱子）元素要么還是在原來的bucket（桶）中，要么在2的冪中。
下面是resize()方法對(duì)于newCap 和newThr的計(jì)算：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/* 如果原容量 > 0 */
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大容量了
threshold = Integer.MAX_VALUE; //修改閾值為（最大容量-1），這樣以后就不會(huì)擴(kuò)容了
return oldTab;
}
//先對(duì)newCap進(jìn)行翻倍。如果newCap達(dá)還小于最大值，且原容量oldCap大于等于默認(rèn)的容量。則newThr賦值為原容量的兩倍，即此時(shí)newCap
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/*如果原容量 == 0 */
else if (oldThr > 0) // 表示在實(shí)例化HashMap時(shí)，調(diào)用了HashMap的帶參構(gòu)造方法，初始化了threshold，這時(shí)將閾值賦值給newCap，因?yàn)樵? newCap = oldThr; //構(gòu)造方法 中是將capacity賦值給了threshold。
/*如果原容量 == 0， 而且oldThr == 0。即調(diào)用了HashMap的默認(rèn)構(gòu)造方法，這時(shí)，將newCap賦值默認(rèn)初始容量16，然后newThr等于加載因子與默認(rèn)容量的乘積*/
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/*如果newThr == 0。這里是上面當(dāng)oldThr > 0遺留下來的,要重新計(jì)算newThr的值*/
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
//加載因子可以大于1，所以要同時(shí)判斷newCap或newThr是否達(dá)到了整數(shù)最大值
}
threshold = newThr;
重點(diǎn)，將原HashMap中的元素拷貝到新HashMap中：
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//把每個(gè)桶的水都移動(dòng)到新的桶中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 這部分是鏈表優(yōu)化rehash的代碼塊
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 新索引 == 原索引+oldCap
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;
}
//新索引 == 原索引 + oldCap放到桶里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
相比于JDK1.7 ， JDK1.8采用2次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來2倍)，所以
經(jīng)過rehash之后，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。
jdk1.8擴(kuò)容機(jī)制的優(yōu)化
- 省去了重新計(jì)算hash值的時(shí)間
- 由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了。這一塊就是JDK1.8新增的優(yōu)化點(diǎn)。
- 有一點(diǎn)注意區(qū)別，JDK1.7中rehash的時(shí)候，舊鏈表遷移新鏈表的時(shí)候，如果在新表的數(shù)組索引位置相同，則鏈表元素會(huì)倒置，但是JDK1.8不會(huì)倒置。
