HashMap在JDK1.8和JDK1.7的差別
結論
先說結論，HashMap在1.7和1.8中最大的差別就是底層資料結構的變化，在1.7中HashMap采用的底層資料結構是數組+連結清單的形式，而在1.8中HashMap采用的是數組+連結清單+紅黑樹的資料結構（當連結清單長度大于8且數組長度大于等于64時連結清單會轉成紅黑樹，當長度低于6時紅黑樹又會轉成連結清單），紅黑樹是一種平衡二叉搜尋樹，它能通過左旋、右旋、變色保持樹的平衡，關于紅黑樹大家想了解的可以自行百度，這裡不再講述。之是以用紅黑樹是因為他能夠大大提高查找效率，連結清單的時間複雜度是O(n)而紅黑樹的時間複雜度是O(logn)，那麼為啥要連結清單長度大于8且數組長度大于64才轉成紅黑樹呢，簡單來說就是節點太少的時候沒必要轉換資料結構，因為不僅轉換資料結構需要浪費時間同時也要浪費空間。而為什麼不直接一直用紅黑樹呢？這是因為樹的結構太浪費空間，隻有節點足夠多的情況下用樹才能展現出它的優勢，而如果在節點數量不夠多的情況下用連結清單的效率更高，占用的空間更小。
HashMap是如何存放元素的呢
當我們向HashMap中存放資料時，首先會根據key的hashCode方法計算出值，然後結合數組長度和算法（如取餘法、位運算等）來計算出向數組存放資料的位置索引值。如果索引位置不存在資料的話則将資料放到索引位中；如果索引位置已經存在資料，這時就發生了hash碰撞（兩個不同的原始值在經過哈希運算後得到相同的結果），為了解決hash碰撞，JDK1.8前用的是數組+連結清單的形式，而JDK1.8後用的是數組+連結清單+紅黑樹，這裡以連結清單為例。由于該位置的hash值和新元素的hash值相同，這時候要比較兩個元素的内容如果内容相同則進行覆寫操作，如果内容不同則繼續找連結清單中的下一個元素進行比較，以此類推如果都沒重複的則在連結清單中新開辟一個空間存放元素。以上圖為例，假設張三、王五、趙六、王五對應的數組數組下标是1，李四對應的數組下标是2。剛開始索引位置1為空，（張三，15）直接放入1位置，索引位置 2為空，（李四，22）直接放入2位置，（王五，18）發現索引位置1已經有資料，這時候調用equals方法和張三進行内容比較，發現内容不同，連結清單開辟新空間存放資料；（趙六，25）發現1位置已經有元素，調用equals和張三比較，内容不同，繼續向下和王五比較，内容不同，開辟新空間存放資料；（王五，28）發現1位置已經有元素，調用equals和張三進行内容比較，不同，繼續向下和（王五，18）比較，發現内容也相同，這時候則進行覆寫操作将原來的（王五，18）改成（王五，28）。
HashMap介紹
1.HashMap hashMap = new HashMap();
當建立一個HashMap集合對象的時候，在JDK8之前，構造方法中建立了一個長度是16的Entry[]table用來存儲鍵值對資料。在JDK8後就不在HashMap的構造方法中建立數組了，而是在第一次調用put方法時建立數組Node[] table，用這個數組來存儲鍵值對資料的。
初始容量大小介紹
說到數組就不得不提HashMap裡面的成員變量
DEFAULT_INITIAL_CAPACITY
也就是容量大小，如果不指定的話預設是16，如果通過有參構造指定容器大小的話也必須是2的平方數，當然了如果傳入的參數并不是2的平方數的話（最好不要這樣，實在不知道寫多少容量我們直接寫個預設的大小16），HashMap會通過方法将它變成比這個數大且離2的平方數最近的數例如傳入11他會變成16，之是以要這麼做的原因是，根據上述講解我們已經知道，當向 HashMap 中添加一個元素的時候，需要根據 key 的 hash 值，去确定其在數組中的具體位置。HashMap 為了存取高效，減少碰撞，就是要盡量把資料配置設定均勻，每個連結清單長度大緻相同，這個實作的關鍵就在把資料存到哪個連結清單中的算法。這個算法實際就是取模，hash % length，計算機中直接求餘效率不如位移運算。是以源碼中做了優化，使用 hash & (length - 1)，而實際上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。
上面提到了如果傳入的指定大小并不是2的n次幂，HashMap會将大小變成比指定大小大且是2的n次幂的數，我們看看JDK1.7和JDK1.8是如何做的。
JDK1.7
*/
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
// 從1開始不停的左移也就是變大2的n次幂，直到不比指定容量小
// 1 2 4 8 16 32.。。。
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
JDK1.8
// 假設cap為13
static final int tableSizeFor(int cap) {
// n=12 int類型在記憶體中占4個位元組，，一個位元組占8位
int n = cap - 1;
/*
* 00000000 00000000 00000000 00001100 12
* 00000000 00000000 00000000 00000110 右移1位
* ---------------------------------------------- 或運算
* 00000000 00000000 00000000 00001110 14
*/
n |= n >>> 1; // n=14
/*
* 00000000 00000000 00000000 00001110 12
* 00000000 00000000 00000000 00000111 右移2位
* ---------------------------------------------- 或運算
* 00000000 00000000 00000000 00001111 15
*/
n |= n >>> 2;//計算完n=15
/*
* 00000000 00000000 00000000 00001111 15
* 00000000 00000000 00000000 00000000 右移4位
* ---------------------------------------------- 或運算
* 00000000 00000000 00000000 00001111 15
*/
n |= n >>> 4;// 計算完n=15
/*
* 00000000 00000000 00000000 00001111 15
* 00000000 00000000 00000000 00000000 右移8位
* ---------------------------------------------- 或運算
* 00000000 00000000 00000000 00001111 15
*/
n |= n >>> 8;// 計算完n=15
/*
* 00000000 00000000 00000000 00001111 15
* 00000000 00000000 00000000 00000000 右移16位
* ---------------------------------------------- 或運算
* 00000000 00000000 00000000 00001111 15
*/
n |= n >>> 16;// 計算完n=15
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
JDK1.8中的做法簡單來說就是通過位運算将最高非0位後面全置為1，由上面可以看出通過這五次的計算，最後的結果剛好可以填滿32位的空間，也就是一個int類型的空間，這就是為什麼必須是int類型，且最多隻無符号右移16位！那麼為啥傳進來的時候進行減1操作呢？因為當傳入的參數剛好是2的n次幂時，算出來的結果是比傳進來的值大的最小n次幂，比如恰好傳進來16如果不減一的話最後計算出來的結果是64，和我們想要的結果不符合，是以在傳進來的時候減一能夠避免出現恰好是n次幂的情況導緻結果不對。大家也可以手動算一算，這樣就能明白了。
負載因子和門檻值
負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f
和門檻值
int threshold
的話是用來給map擴容判斷時用的，負載因子也能夠在構造函數中進行指定（不推薦），每次進行put的時候都會進行判斷是否需要擴容，當size超過了門檻值=總容量*負載因子，則會擴容，預設情況下總容量是16，負載因子是0.75，至于為啥是0.75這是由于經過大量的實驗證明該系數是最合适的，如果設定過小，HashMap每put少量的資料，都要進行一次擴容，而擴容操作會消耗大量的性能。如果設定過大的話，如果設成1，容量還是16，假設現在數組上已經占用的15個，再要put資料進來，計算數組index時，發生hash碰撞的機率将達到15/16，這違背的HashMap減少hash碰撞的原則。
HashMap構造方法
JDK1.7中的無參構造方法：
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
// 負載因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 門檻值：總容量*負載因子
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// 存放鍵值對的entry
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
JDK1.8中的構造方法：
public HashMap() {
// 将負載因子設定為預設的0.75f，并沒有在構造方法中建立Entry的數組，而是放到put方法中了
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity, float loadFactor) {
// 給的初始大小是不是小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 是否超過最大容量，是的話則直接指派最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 給的加載因子是不是個大于0的數字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 設定加載因子的大小
this.loadFactor = loadFactor;
// 調整給定的數組大小
this.threshold = tableSizeFor(initialCapacity);
}
this.threshold = tableSizeFor(initialCapacity);判斷指定的初始化容量是否是2的n次幂，如果不是那麼會變為比指定初始化容量大的最小的2的n次幂。但是注意，在tableSizeFor方法體内部将計算後的資料傳回給調用這裡了，并且直接指派給threshold邊界值了。有些人會覺得這裡是一個bug，應該這樣書寫：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;這樣才符合threshold的意思（當HashMap的size到達threshold這個門檻值時會擴容）。但是請注意，在jdk8以後的構造方法中，并沒有對table這個成員變量進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算。
JDK1.8中的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
.......
// 存放鍵值對的Node
Node<K,V>[] tab;
.......
}
在put方法中又調用了
putVal(hash(key), key, value, false, true);
以及
hash(key)
方法，首先我們先來看下
hash(key)
方法
static final int hash(Object key) {
int h;
// 如果key是null則hash值為0
//(h = key.hashCode()) ^ (h >>> 16)
// 先擷取key的hashCode并指派給h， 然後和h和h右移16位後做異或運算得到hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這裡有個步驟(h = key.hashCode()) ^ (h >>> 16)，為什麼要擷取完hashCode()指派給h後要和h右移16位做異或運算呢，直接讓h=key.hashCode()不行嗎？實際上這是在進行put操作時盡可能的避免hash沖突，前面說過存放元素的時候尋找數組下标實際上是hash值對數組長度取餘，當數組長度為2的n次幂時，(n - 1) & hash和hash%n是等價的而且運算效率比取餘高，簡單來說之是以這麼做就是，高 16bit 不變，低 16bit 和高 16bit 做了一個異或（得到的 hashCode 轉化為 32 位二進制，前 16 位和後 16 位低 16bit 和高 16bit 做了一個異或），可以看看下面計算，确實了解起來有點深度，但這也是人家牛逼之處。
假設：
數組大小n=16=0000 0000 0000 0000 0000 0000 0001 0000
1.假設hash直接和h相等
調用hashCode()方法h=h.hashCode()：
h=h.hashCode()=1111 1111 1111 1111 1111 0000 1110 1010
hash=1111 1111 1111 1111 1111 0000 1110 1010
計算數組下标：(n-1)&hash
(n-1):0000 0000 0000 0000 0000 0000 0000 1111
hash：1111 1111 1111 1111 1111 0000 1110 1010
---------------------------------------------
(n-1)&hash=0000 0000 0000 0000 0000 0000 0000 1010=10
我們看到真正參與運算的實際上隻有最後四位，也就是說其他高位并沒有參與運算
那麼會出現一種狀況，就是調用hashCode()方法擷取的值高位不停的在變動但是
地位不變，這種狀況就會造成(n-1)&hash結果會一緻，造成hash沖突。
2.假設hash = h^(h>>>16)：
調用hashCode()方法h=h.hashCode()：
h=h.hashCode()=1111 1111 1111 1111 1111 0000 1110 1010
(h>>>16):
0000 0000 0000 0000 1111 1111 1111 1111
hash = h^(h>>>16)：
1111 1111 1111 1111 0000 1111 0001 0101
計算數組下标：(n-1)&hash
(n-1):0000 0000 0000 0000 0000 0000 0000 1111
hash:1111 1111 1111 1111 0000 1111 0001 0101
------------------------------------------------
(n-1)&hash=0000 0000 0000 0000 0000 0000 0000 0101=5
簡單來說就是通過右移16位和異或操作讓高位地位都參與了運算盡可能的減少hash沖突
接着看putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/*
Node<K,V>[] tab：存放元素的數組
Node<K,V> p：用來儲存索引位置的元素
int n：n用來記錄數組的長度
int i：i用來記錄索引的位置
*/
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
1.table：transient Node<K,V>[] table; 存放元素的數組
2.(tab = table) == null 将table指派給tab并判斷是否為null 第一次put必然為null
3.(n = tab.length) == 0 将數組的長度指派給n并判斷是否為0
*/
if ((tab = table) == null || (n = tab.length) == 0)
// tab為null 或者 tab長度為0，進行擴容操作
n = (tab = resize()).length;
/*
(n - 1) & hash：之前說過，當n為2的n次幂時這個操作等價于hash%n，即hash值對數組長度取餘
i = (n - 1) & hash：存放元素的數組索引下标
索引位置不存在元素，則在索引位置建立一個新節點
這裡會給p進行指派，不存元素p則為null
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
/* 執行else說明tab[i]不等于null，表示這個位置已經有值了
Node<K,V> e：儲存資料的節點
K k：儲存key
*/
Node<K,V> e; K k;
/*
1.p.hash == hash：p的hash值==傳入的hash值
2.(k = p.key) == key：将p的key指派給k == 現在的key
3.key != null && key.equals(k)))：key不為空&&key的内容和現在的key的内容相等
同時滿足1、2或者滿足3，則将p節點指派給e
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/*
判斷p是否為紅黑樹結點
*/
else if (p instanceof TreeNode)
/*
往樹中插入節點并指派給e
*/
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
/*
binCount：記錄周遊節點的個數
*/
for (int binCount = 0; ; ++binCount) {
/*
1)e = p.next 擷取p的下一個元素指派給e。
2)(e = p.next) == null 判斷p.next是否等于null，等于null，說明p沒有下一個元素，
那麼此時到達了連結清單的尾部，還沒有找到重複的key,則說明HashMap沒有包含該鍵，将該鍵值對插傳入連結表中。
*/
if ((e = p.next) == null) {
/*
最後一個節點了，是以next為null
JDK8采用尾插法新增節點，JDK8之前是頭插法
*/
p.next = newNode(hash, key, value, null);
/*
判斷是否要轉成紅黑樹
binCount是從0開始自增的，當binCount = 7時說明已經有8個節點
加上剛剛插入的節點是以是9個，是以當連結清單長度>8時轉成紅黑樹
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 轉成紅黑樹
treeifyBin(tab, hash);
break;
}
/*
執行到這裡說明e = p.next 不是null，不是最後一個元素。繼續判斷連結清單中結點的key值與插入的元素的key值是否相等。
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
break;
// 将e指派給p，繼續查找下一節點
p = e;
}
}
/*
如果e!=null則說明通過上面的一系列操作，找到了重複的key，是以
這裡就是将key對應的原來的舊值替換成新值并将舊值傳回
*/
if (e != null) { // existing mapping for key
// 擷取舊值
V oldValue = e.value;
// onlyIfAbsent為false或者oldValue為null
if (!onlyIfAbsent || oldValue == null)
// 将新值儲存
e.value = value;
// 通路後回調，點進去會發現是個空方法，是為了繼承HashMap的LinkedHashMap類服務
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
// 這個變量是用來記錄修改次數的
++modCount;
// 判斷新增元素後的大小是否比門檻值大，如果是的話則要進行擴容操作
if (++size > threshold)
resize();
// 插入後回調，點進去會發現是個空方法，是為了繼承HashMap的LinkedHashMap類服務
afterNodeInsertion(evict);
return null;
}
轉成紅黑樹的__treeifyBin()__方法
/**
* 轉成紅黑樹
* @param tab
* @param hash
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/*
數組tab不為空或者數組長度小于64則進行擴容操作
n = tab.length:數組長度指派給n
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
/*
轉成紅黑樹操作
e = tab[index = (n - 1) & hash])：擷取索引位置元素
*/
else if ((e = tab[index = (n - 1) & hash]) != null) {
/*
hd：存放樹的頭結點
tl：用來存放臨時節點
*/
TreeNode<K,V> hd = null, tl = null;
do {
// 将連結清單節點轉成樹節點
TreeNode<K,V> p = replacementTreeNode(e, null);
/*
tl：第一次臨時節點必然為空
将p節點指派給頭結點
*/
if (tl == null)
hd = p;
else {
/*
臨時tl節點不為空：
p.prev = tl：将tl指派給p的prev節點
tl.next = p：将p節點指派給tl的next節點
*/
p.prev = tl;
tl.next = p;
}
// 将p節點指派給tl節點
tl = p;
} while ((e = e.next) != null); // 循環，直到Next節點不存在
/*
(tab[index] = hd)：将樹的頭結點指派給數組索引位置
*/
if ((tab[index] = hd) != null)
/*
轉成紅黑樹的具體操作
*/
hd.treeify(tab);
}
}
說明
- size表示HashMap中鍵值對的實時數量，這個不等于數組的長度
- threshold（臨界值）= capacity（容量）* loadFactor（負載因子）。這個值是目前已占用數組長度的最大值。size 超過這個值就重新 resize（擴容），擴容後的 HashMap 容量是之前容量的兩倍。
JDK1.7中的put方法
public V put(K key, V value) {
/*
如果Key是null的話，則調用putForNullKey方法
putForNullKey：如果不存在null為key的Entry則新增，如果存在的話則替換原來的值并傳回
*/
if (key == null)
return putForNullKey(value);
/*
key.hashCode()：調用key的hashCode()擷取hashCode
hash(key.hashCode()):通過調用hash方法獲得hash值
這個操作實際上和JDK1.8的HashMap的hash(key)類似，也是通過該方法使得高低位都參與
hash計算進而避免hash沖突，大家可以參考一下上面JDK1.8的HashMap
*/
int hash = hash(key.hashCode());
/*
這一步是計算出數組的索引下标
計算方法和JDK8一樣
*/
int i = indexFor(hash, table.length);
/*
Entry<K,V> e = table[i]：将索引下标對應的元素指派給Entry
這個步驟實際上就上周遊連結清單查找元素
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
/*
e的哈希值和新元素的hash值相等且内容也相同則說明key相同
用新值替換節點中的舊值并将舊值傳回
*/
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 這個變量是用來記錄修改次數的
modCount++;
// 到這一步說明沒有key重複的元素，新增元素
addEntry(hash, key, value, i);
return null;
}
新增元素的addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
/*
擷取索引位置的Entry
*/
Entry<K,V> e = table[bucketIndex];
/*
采用頭插法将元素插入到連結清單中
新節點插入後将e指派給next
*/
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 判斷新增元素後數組大小是否超過門檻值
if (size++ >= threshold)
// 擴容方法，将擴大為原來數組大小的兩倍
resize(2 * table.length);
}
擴容方法resize()
HashMap在進行擴容時，每次擴容後的大小都是原來數組的兩倍，然後将原數組中的元素配置設定到新的數組中去，那麼它是如何配置設定的呢？由于每次進行擴容都是原來大小的兩倍，計算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我們有了這樣的結論：這新舊兩次計算下标的結果，要不然就相同，要不然就是新下标等于舊下标加上舊數組的長度
舊數組長度：n=16
n： 0000 0000 0000 0000 0000 0000 0001 0000
n-1： 0000 0000 0000 0000 0000 0000 0000 1111
假設有兩個元素的hash值為:
hash1： 1111 1111 1111 1111 0000 1111 0000 0101
hash2： 1111 1111 1111 1111 0000 1111 0001 0101
計算兩個hash對應數組的索引位置:(n-1)*hash
index1: 0000 0000 0000 0000 0000 0000 0000 0101
index2: 0000 0000 0000 0000 0000 0000 0000 0101
在原數組中hash1和hash2通過計算對應的數組索引位置都是5(0101)
================================================================
擴容後的新數組：n=2*n=32
n： 0000 0000 0000 0000 0000 0000 0010 0000
n-1： 0000 0000 0000 0000 0000 0000 0001 1111
元素還是之前的元素，也就是說hash還是之前的hash:
hash1： 1111 1111 1111 1111 0000 1111 0000 0101
hash2： 1111 1111 1111 1111 0000 1111 0001 0101
計算兩個hash對應數組的索引位置:(n-1)*hash
index1: 0000 0000 0000 0000 0000 0000 0000 0101（5）
index2: 0000 0000 0000 0000 0000 0000 0001 0101（21）
從結果上看，在原數組中放到同一個索引位置的兩個元素，在經過擴容重新
配置設定後，hash1計算出的索引位置還是原數組中的位置，hash2計算出的索
引位置是原數組中的位置+原數組長度
其實hash值的對應的新數組下标是不是需要加上舊數組的長度，隻需要看看hash值&舊數組長度(hash&oldTable.length)是不是1就行了如果是1的話就是原數組中的位置+原數組長度，0的話就是原數組中的位置
JDK1.7中的擴容方法
void resize(int newCapacity) {
// 擷取源數組
Entry[] oldTable = table;
// 原數組容量大小
int oldCapacity = oldTable.length;
// 判斷原容量大小是否已經是最大值了
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 建立數組大小為原數組大小的兩倍
Entry[] newTable = new Entry[newCapacity];
/*
擴容方法的關鍵，重新計算索引配置設定位置
*/
transfer(newTable);
// 新數組替換原數組
table = newTable;
// 新門檻值
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
// 源數組
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
// 将元素指派給e
Entry<K,V> e = src[j];
if (e != null) {
// 将原來位置的元素置為null，友善GC
src[j] = null;
do {
Entry<K,V> next = e.next;
// 重新計算元素在新數組中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
static int indexFor(int h, int length) {
return h & (length-1);
}
JDK1.8中的擴容方法
final Node<K, V>[] resize() {
// 源數組
Node<K, V>[] oldTab = table;
// 原來的數組容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 原來數組的門檻值
int oldThr = threshold;
/*
newCap：新數組的容量，初始值為0
newThr：新數組的門檻值，初始值為0
*/
int newCap, newThr = 0;
// 判斷原來的數組大小是否不為0
if (oldCap > 0) {
/*
原數組的容量已經大于等于最大容量
将最大值指派給原來的門檻值并傳回原數組
*/
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
(newCap = oldCap << 1)：将原數組左移一位，也就是擴大為原來的2倍并指派給新容量newCap
新容量小于最大容量值且原數組容量要大于預設的初始容量16則将門檻值擴大
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 門檻值擴大一倍
newThr = oldThr << 1; // double threshold
}
/*
原門檻值大于0則指派給新容量
這裡肯能有疑問為啥将原數組門檻值大小指派給新容量？
看看前面的JDK1.8中的有參構造方法就明白了，
在tableSizeFor方法體内部将計算後的資料直接指派給threshold邊界值了
*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/*
進入else則說明原來數組的容量和門檻值都是0，則進行初始化預設值
newCap：指派初始值16
newThr：新門檻值=0.75*16=12
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/*
新門檻值還是初始值0則計算新門檻值
*/
if (newThr == 0) {
// ft = 新容量*負載因子
float ft = (float) newCap * loadFactor;
// 新數組容量不超過最大值且ft小于最大值則取ft為新門檻值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
// 将新門檻值指派給成員變量threshold
threshold = newThr;
// 建立新長度的數組newTab
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
// 将新數組指派給成員變量table
table = newTab;
if (oldTab != null) {
// 周遊原數組，将資料放到新的數組中去
for (int j = 0; j < oldCap; ++j) {
// 用來儲存周遊中的元素
Node<K, V> e;
if ((e = oldTab[j]) != null) {
/*
将原數組中索引位置的元素指派給e後，将索引位置的元素置為null友善GC
*/
oldTab[j] = null;
/*
判斷數組是否有下一個引用，如果e.next為空則說明不是連結清單，直接将元素放到數組中即可
*/
if (e.next == null)
/*
将原數組中的原素放到新數組中
e.hash & (newCap - 1)：這一步是計算元素放到新數組的索引位置
*/
newTab[e.hash & (newCap - 1)] = e;
/*
判斷是否是紅黑樹
*/
else if (e instanceof TreeNode)
// 說明是紅黑樹來，則調用相關方法處理
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else {
/*
到了else說明是連結清單
loHead：下标不變情況下的連結清單頭
loTail：下标不變情況下的連結清單尾
hiHead：下标改變情況下的連結清單頭
hiTail：下标改變情況下的連結清單尾
*/
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
// 将e的next節點指派給next變量
next = e.next;
// 這裡來判斷如果等于true e這個結點在resize之後不需要移動位置，也就是對應數組下标不變，這裡也就是判斷是不是新索引位置=原數組長度+原數組位置
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);// 将next指派給e，繼續循環直到next為空
// 原索引放到數組中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到數組中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
後面的remove和get方法相對比較容易一點，下面都是以JDK8為例，大家可以自己去看看源碼對比對比
删除方法 remove()
删除方法就是首先先找到元素的位置，如果是連結清單就周遊連結清單找到元素之後删除。如果是用紅黑樹就周遊樹然後找到之後做删除，樹小于 6 的時候要轉連結清單。
查找元素方法 get()
主要是getNode方法
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;
// first：儲存頭結點 e：儲存next節點
Node<K, V> first, e;
// 儲存數組長度
int n;
// 儲存key值
K k;
/*
tab = table：将數組指派給tab
n = tab.length：記錄數組長度
first = tab[(n - 1) & hash]：将key對應的索引位置中的元素指派給first
*/
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;
/*
将next節點指派給e
*/
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;
}
幾種周遊HashMap的方式
public static void main(String[] args){
HashMap<String,Integer> hashMap = new HashMap<>(16);
hashMap.put("科比",36);
hashMap.put("韋德",23);
hashMap.put("詹姆斯",38);
hashMap.put("安東尼",30);
hashMap.put("保羅",25);
// 分别周遊key和values
iteratorMap_1(hashMap);
// 使用疊代器周遊
iteratorMap_2(hashMap);
// 通過 get 方式
iteratorMap_3(hashMap);
// 通過lambda方式
iteratorMap_4(hashMap);
}
1.分别周遊key和value（不常用）
/**
* 分别周遊key和values
* @param hashMap
*/
private static void iteratorMap_1(HashMap<String, Integer> hashMap) {
for (String key : hashMap.keySet()) {
System.out.println(key);
}
for (Integer value : hashMap.values()) {
System.out.println(value);
}
}
2.通過疊代器疊代（推薦）
/**
* 使用疊代器周遊
* @param hashMap
*/
private static void iteratorMap_2(HashMap<String, Integer> hashMap) {
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
System.out.println(entry.getKey()+"=====>"+entry.getValue());
}
}
3.通過get方式（不推薦使用）
根據阿裡開發手冊，不建議使用這種方式，因為疊代兩次。keySet 擷取 Iterator一次，還有通過 get 又疊代一次，降低性能。
/**
* 通過 get 方式
* @param hashMap
*/
private static void iteratorMap_3(HashMap<String, Integer> hashMap) {
for (String key : hashMap.keySet()) {
Integer value = hashMap.get(key);
System.out.println(key+"=====>"+value);
}
}
4.使用lambda表達式周遊（推薦）
/**
* 通過lambda
* @param hashMap
*/
private static void iteratorMap_4(HashMap<String, Integer> hashMap) {
hashMap.forEach((key,value)->System.out.println(key+"=====>"+value));
}
如何給HashMap設定正确的初始容量
我們上面介紹過，HashMap 的擴容機制，就是當達到擴容條件時會進行擴容。HashMap 的擴容條件就是當 HashMap 中的元素個數（size）超過臨界值（threshold）時就會自動擴容。是以，如果我們沒有設定初始容量大小，随着元素的不斷增加，HashMap 會有可能發生多次擴容，而 HashMap 中的擴容機制決定了每次擴容都需要重建 hash 表，是非常影響性能的。比如我們有7個元素要存放，我們設定初始容量為7，經過HashMap的處理他會給我們将容量設定為8，但是我們知道當元素個數超過8*0.75=6時就會進行一次擴容，也就是說我們設定的這個初始容量7其實是不對的。
是以初始化容量，設定的數值不同也會影響性能，那麼當我們已知 HashMap 中即将存放的 Key、Value個數的時候，容量設定成多少為好呢？
關于設定 HashMap 的初始化容量大小：可以認為，當我們明确知道 HashMap 中元素的個數的時候，把預設容量設定成initialCapacity/ 0.75F + 1.0F 是一個在性能上相對好的選擇，但是，同時也會犧牲些記憶體。而 Jdk 并不會直接拿使用者傳進來的數字當做預設容量，而是會進行一番運算，最終得到一個 2 的n次幂。同意以7為例，7/0.75+1=10，我們傳入10經過HashMap處理會給一個16大小的HashMap這樣就避免了頻繁擴容，但是會浪費一些空間。
參考部落格