大家好，相信大家平時學習生活中HashMap肯定用的不少，反正在面試中你熟讀其原始碼，了解其原理，知道其什么地方不合理，會導致什么樣的問題
今天帶大家看一看JDK1.7和JDK1.8的HashMap的原始碼
他們兩個的差別隨便抓一個還在上幼兒園的小盆友都說的頭頭是道
小朋友奶里奶氣的說：1.7是陣列+鏈表，1.8優化成了陣列+鏈表（紅黑樹）
真的就這嗎？
我們來看看其原始碼（每段原始碼前我用自己的話進行了一番描述，可能有點丑看不懂，就直接看原始碼吧，關鍵地方我也進行了注釋）
先看1.7的
屬性：
/** 建構式沒傳初始化容量就使用該默認容量 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** 最大容量,建構式傳的初始容量也不能大于這個 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 默認負載因子*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** table未初始化時的table實體 */
static final Entry<?,?>[] EMPTY_TABLE = {};
/** 維護的一個table,根據需要調整大小,長度必須為2的冪*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE
/** entry的數量*/
transient int size;
/** 閾值,下一個需要調整大小的值,loadFactor * capacity */
// 當table未初始化時,這個就是initial capacity
int threshold;
/** 負載因子 */
final float loadFactor;
/** hash值生成種子,目的是減少hash沖突*/
transient int hashSeed = 0;
put()方法會先判斷當前table是否需要初始化
然后會判斷待添加的key是否為null
接著會計算出當前key的hash，根據算出的hash值和當前table的長度算出應該存放在index為多少的bucket（bucket可以看作是指定下標的陣列）里面
會去遍歷該bucket，判斷是否有key相同的（判斷依據是先判斷hash值，再判斷地址值或者值是否相等）
有則覆寫之前的值，無則新增一個entry
public V put(K key, V value) {
// 假如當前table為空的,根據threshold(initialCapacity)擴容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
// 當key為null時的put方法
return putForNullKey(value);
int hash = hash(key);
// 根據hash值和當前table的長度計算應該放在下標為多少的bucket里面
int i = indexFor(hash, table.length);
// 這里去遍歷指定下標的bucket,看key為當前key的entry有沒有
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 先判斷hash值,再判斷key是否==或者equals
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相等的entry沒有
addEntry(hash, key, value, i);
return null;
}
初始化table方法：
會將initialCapacity向上取整為2的冪作為當前的capacity，并更新當前threshold為capacity * loadFactor
還會初始化hashcode生成種子（注意，這個什么hash種子只存在于1.7，1.8就無了）
private void inflateTable(int toSize) {
// toSize向上取整為2的冪
int capacity = roundUpToPowerOf2(toSize);
// 更新當前閾值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
// 懶加載hashcode種子
initHashSeedAsNeeded(capacity);
}
當key為null時的put方法：
HashMap默認將key為null的放在index為0的bucket里面，所以這里會去遍歷index為0的bucket里面是否有key為null的entry
有則替換，無則新增一個entry
private V putForNullKey(V value) {
// key為null時,默認將entry放在index為0的bucket里面
// 這里會去遍歷index為0的鏈表,如果找到key為null的會替換
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 沒找到這里會新增一個key為null的entry
addEntry(0, null, value, 0);
return null;
}
進行新增entry的一些前置作業：
這里涉及到一些擴容操作
如果當前size大于等于threshold并且指定index的bucket不為null時（也就是將要放入的bucket里一個元素都沒有，不會進行擴容）
將bucket的長度擴大為現在的兩倍，并將hash值和index值重新計算
void addEntry(int hash, K key, V value, int bucketIndex) {
// 替換是不涉及擴容的,這里新增才會涉及
if ((size >= threshold) && (null != table[bucketIndex])) {
// bucket長度擴大為現在的兩倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
擴容：
擴容方法，先對舊table進行容量判斷，如果舊的容量已經最大了，那么不能再大了，直接不擴容
否則會生成一個新的table，將舊table里的entry全部轉放到新的table里面，會重新生成hashcode種子，并判斷是否需要重新hash
threshold設定為newCapacity * loadFactor
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];
// 重新生成hash種子會判斷是否需要重新hash,再將現有的entry轉移到new table里面
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
將擴容后的entry從舊table 轉移到 new table里面：
遍歷每一個bucket，再遍歷每一個bucket的鏈表，如果需要hash會重新hash，并重新計算該放入的bucket的index
注意：這里的操作會使鏈表反轉（記住，要考的）
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
// e是每一個bucket
while(null != e) {
Entry<K,V> next = e.next;
// 需要重新hash就會重新hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新計算bucket的下標
int i = indexFor(e.hash, newCapacity);
// 經典將鏈表反轉
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
真 - 添加entry方法：沒什么好說的，只有一個頭插法比較6（要考哦）
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 也是經典頭插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
get()會先判斷需要查找的key是否為null，感覺get()沒什么好說的，相比put()來說簡直太清爽，隨便看一看就好
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
獲取key為null的value的方法：
private V getForNullKey() {
// 如果當前size為0,直接回傳null
if (size == 0) {
return null;
}
// key為null會將其放在index為0的bucket里面
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
獲取指定key的方法：
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 計算帶查找key的hash值
int hash = (key == null) ? 0 : hash(key);
// 根據當前table的長度和hash值計算bucket的index,并遍歷
for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
Object k;
// 判斷依據還是和添加時一樣的,先判斷hash,再判斷地址值或者值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
執行緒安全問題：在擴容時采用頭插法，頭插法會使元素順序倒轉，多執行緒情況（兩個執行緒同時擴容，一個執行緒先擴容完成，另一個執行緒看到的鏈表就是被倒轉的）下會產生環形鏈表導致死回圈以及資料丟失的問題
看完清爽的1.7，接下來看1.8（不得不說，就算1.8優化的再6，思想再6，1.8的代碼寫的是真的臭，比1.7清爽的代碼不知道差到天上去，自己寫時爽，讀時火葬場）
1.8的HashMap：
因為1.7在發生嚴重hash沖突時整個Map會退化成鏈表，導致效率會很低，1.8做了一些優化
1.8將內部的Entry改為Node（這個操作誰給我解釋一下），除此之外好像沒什么毛區別
1.8的屬性與1.7相比基本變，只是新增了幾個屬性，還有就是沒有了EMPTY_TABLE這個屬性
/** list->tree的閾值,必須大于2且至少為8?*/
static final int TREEIFY_THRESHOLD = 8;
/** tree->list的閾值,最多為6,*/
static final int UNTREEIFY_THRESHOLD = 6;
/** 樹化的最小容量 至少為4 * TREEIFY_THRESHOLD*/
static final int MIN_TREEIFY_CAPACITY = 64;
1.8的hash()方法相比1.7的更簡單了，1.7還有什么hash種子，1.8已經沒有了
1.7的：
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
1.8的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
原因可能（我也不知道，猜的，抓作者過來問一問就知道了）是因為在1.7的時候，應該要盡量避免hash沖突，否則會導致整個表退化成為一個鏈表，而1.8引進了紅黑樹，相對而言，比1.7不那么怕了，所以整個hash值的運算變簡單了
put()：put()方法就是一個玩具，下面才是正題
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
putVal()：
onlyIfAbsent如果為true的話，表示不覆寫key已經存在的值，evict為false，表示當前table處于創建模式
putVal()會先判斷當前table是否需要初始化
接著會判斷待插入節點應放在table的位置是否為null（也就是待插入節點應放在的陣列位置，現在是不是為null），為null就直接放入了不需要后面的操作
不為null的話接著判斷陣列（鏈表）的第一個元素的key和待插入元素的key相同不，判斷依據是hash值是否相同，以及記憶體地址或者值是否相同（與1.7好像無異）
不相同會判斷是否為treeNode，假如是，會依據treeNode的方式去添加元素
以上都不成立，會遍歷當前鏈表，找到最后一個空位置將其插入，或者是找到鏈表上是否有key相同的節點
假如找到了最后一個空位置會判斷是否需要樹化
之前找到的相同key的位置會放到現在來覆寫，最后會判斷是否需要擴容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 如果當前table還未初始化(為null或者長度為0)
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化當前table
n = (tab = resize()).length;
// 當前陣列元素是否為null
// 這里順便確定了一下當前entry應該放在index為多少的陣列里面
if ((p = tab[i = (n - 1) & hash]) == null)
// 為null直接新增一個node(list)放在鏈表頭(也就是陣列位置)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// p是當前陣列的元素(也就是鏈表的第一個元素)
// 判斷當前元素與待插入元素的key是否相同
// 依據是hash值是否相同,以及記憶體地址或者值是否相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 這里是tree版的putVal()
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 這里在遍歷鏈表
if ((e = p.next) == null) {
// 找到最后一個節點插入
p.next = newNode(hash, key, value, null);
// 當前鏈表長度大于等于樹化閾值就會樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 找到了key相同的節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 迭代鏈表節點
p = e;
}
}
// e不為null說明找到了key相同的節點
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// afterNodeAccess()是空實作,為LinkedHashMap準備的
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 添加完新節點后size大于閾值需要resize
if (++size > threshold)
resize();
// afterNodeInsertion(),這個也是空實作,同上
afterNodeInsertion(evict);
return null;
}
resize()：
首先會判斷當前容量是否大于0，大于0說明是擴容，則只要不超過最大容量的情況下將容量和閾值分別擴大兩倍即可
如果不為擴容，會判斷是否當前閾值大于0，當前閾值大于0說明從建構式里面傳入了初始容量，只是用閾值這個值來暫放一下，會把新容量設定為當前閾值
都不是（既不是擴容，建構式也沒傳入初始容量），使用默認容量，配合默認負載因子確定閾值（其實也是默認的）
接著判斷如果新容量是當前閾值，將當前閾值更新（根據老公式）
以上是確定新容量和新閾值，下面是將舊table里的元素放入新table，對應1.7里的transfer()
如果舊table不為null，說明是擴容，會去遍歷沒每一個陣列元素，再遍歷每一條鏈表（或許不為鏈表）
假如這個鏈表只有一個元素，直接計算其在新table里面的下標放入即可
如果是treeNode，則按照treeNode的方式轉移
如果都不是，就會遍歷當前鏈表，依據e.hash & oldCap是否為0，將原鏈表hash為高低位兩個鏈表
低位的鏈表保留在與old table同一index的位置，高位的鏈表放在old table的index + old容量的位置 ，且這里與1.7不同點在于，注釋里面都寫了preserve order（保留順序）
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) {
// 不能擴大到MAXIMUM_CAPACITY之外
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 將新容量新閾值擴大為兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 初始化容量為0,閾值不為0,則初始化容量就為當前閾值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 使用的是空構造
else { // zero initial threshold signifies using defaults
// 默認容量1 << 4 aka 16
newCap = DEFAULT_INITIAL_CAPACITY;
// 默認閾值 0.75 * 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// new閾值為0表示初始化容量使用了當前閾值
if (newThr == 0) {
// 更新一下當前閾值,實則是縮小了
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 創建一個新的table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 下面要將old table的entry轉移到new table,相當于1.7的transfer()
if (oldTab != null) {
// 遍歷每一個陣列元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 雖然他沒寫,我幫他寫一個help GC
oldTab[j] = null;
// 這個鏈表只有一個元素
if (e.next == null)
// 計算出新table的index并放入
newTab[e.hash & (newCap - 1)] = e;
// 樹節點的放入
else if (e instanceof TreeNode)
// 這里也是將樹拆分為高位和低位,如果樹太小就變為list
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 不同于1.7,這里要保留當前順序
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 這里根據e.hash & oldCap是否為0,將原鏈表hash為高低位兩個鏈表
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);
// 低位的鏈表保留在與old table同一index的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位的鏈表放在old table的index + old容量的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get()：get()方法好像還是繼承了HashMap的老傳統，沒什么好說的
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
getNode()：
首先會判斷table是否為空，以及當前key對應的陣列元素是否為null
不為null的話會檢查第一個元素是否是要查找的元素，
如果第一個不是且有next元素的話，會遍歷查找
treeNode按照tree的方式，鏈表按照鏈表的方式
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table不為null且table的長度不為0且key對應的陣列元素不為null
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元素會遍歷的找
if ((e = first.next) != null) {
// 是treeNode會按照treeNode方式獲取
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;
}
執行緒安全問題：jdk1.8采用尾插法，解決了1.7存在的問題
又出現了新的問題：
1、多執行緒并發插入資料時，resize呼叫split()拆分樹，接著會呼叫untreeify()將當前treeNode轉為listNode，故原有的treeNode會被gc，但是并沒有，會出現OOM
2、put時會覆寫掉一些值，導致資料丟失
3、多執行緒情況下，size()值也不準確
總結：1.8結構、思想、實作比1.7 6，代碼寫的是真臭，比如說下面這段代碼
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {}
您不能寫成
tab = table;
n = tab.length;
first = tab[(n - 1) & hash];
if (tab != null && n > 0 && first != null) {}
這樣嗎？
反正1.8的代碼不憋著火你是沒法看進去的
其他總結就不總結了，你們來總結，寫的不好的地方歡迎評論區交流哦，謝謝大家
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258142.html
標籤：其他
上一篇：go預防跨站腳本
下一篇：轉型時代，我心目中的數字化產品！