我的所有原創Android知識體系,已打包整理到GitHub.努力打造一系列適合初中高級工程師能夠看得懂的優質文章,歡迎star~
1. 存儲結構
1.1 JDK 1.7
內部是以數組的形式存儲了Entry對象,而每個Entry對象裏面有key和value用來存值.它裏面包含了key、value、next、hash四個字段,其中next字段是用來引用下一個Entry的(相同的hash值會被放入同一個鏈表中).數組中的每個位置都是一條單鏈表(也可以稱之為桶),數組中的元素的表頭.解決衝突的方式是拉鍊法,同一條單鏈表中的Entry的hash值是相同的.
transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}1.2 JDK 1.8
存儲結構也是數組,只不過將Entry換了個名字叫Node.1.7中hash值相同的是放單鏈表中,1.8也是,當這個單鏈表的長度超過8時,會轉換成紅黑樹,增加查找效率.
2. 基本概念
2.1 負載因子和閾值
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;HashMap的默認大小是16,默認負載因子是0.75,意思是當存的元素個數超過16*0.75時就要對數組擴容,這裏的閾值就是16*0.75=12.負載因子就是用來控制什麼時候進行擴容的.
閾值 = 當前數組長度*負載因子
每次擴容之後都得重新計算閾值.默認的數組長度是16,默認的負載因子是0.75這些都是有講究的.在元素個數達到數組的75%時進行擴容是一個比較折中的臨界點,如果定高了的話hash衝突就很嚴重,桶就會很深,查找起來比較慢,定低了又浪費空間.一般情況下,還是不會去定製這個負載因子.
ps: 到底是閥值還是閾值,傻傻分不清,,,,知乎上有個關於這個問題的討論 - 「閥值」是否為「閾值」的誤筆？
2.2 拉鍊法工作原理
每次新存入一個新的鍵值對時,首先計算Entry的hashCode,用hashCode%數組長度得到所在桶下標,然後在桶內依次查找是否已存在該元素,存在則更新,不存在則插入到桶的頭部.
3. 源碼分析
3.1 JDK 1.7
有了上面的基礎概念,下面開始看源碼學習
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
//默認初始容量,必須是2的冪 這裏的值是16
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;
//默認的空數組
static final Entry<?,?>[] EMPTY_TABLE = {};
//用來盛放真實數據的數組
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//當前HashMap的真實鍵值對數量
transient int size;
//閾值 = 數組長度*負載因子
int threshold;
//負載因子
final float loadFactor;
//標識對該HashMap進行結構修改的次數,結構修改是指增刪改或其他修改其內部結構(例如rehash)的次數.
//用於迭代器快速失敗.
transient int modCount;
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//可以同時制定數組大小和負載因子
public HashMap(int initialCapacity, float loadFactor) {
...//省略部分邏輯判斷
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
...
this.loadFactor = loadFactor;
threshold = initialCapacity;
...
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
}3.1.1 put
上面是HashMap的一些基本屬性,都是相對比較重要的.接着我們來看一下添加元素put方法的實現,以下是JDK 1.7的put代碼
public V put(K key, V value) {
//1. 數組為空 -> 初始化(創建)數組
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//2. key為null,單獨處理
if (key == null)
return putForNullKey(value);
//3. 計算hash值
int hash = hash(key);
//4. 計算該hash值該存放在數組的哪個索引處
int i = indexFor(hash, table.length);
//5. 遍歷鏈表(數組的每個元素都是單鏈表的表頭) 查找鏈表中是否已存在相同的key 如果有,則替換掉
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//6. 添加元素到數組中
addEntry(hash, key, value, i);
return null;
}3.1.1.1 inflateTable 數組初始化
簡簡單單幾句代碼涉及的東西缺特別多,我們逐個來解讀一下.首先是初始化數組inflateTable方法,傳入的是閾值.
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
//Integer.highestOneBit
public static int highestOneBit(int var0) {
//求掩碼
var0 |= var0 >> 1;
var0 |= var0 >> 2;
var0 |= var0 >> 4;
var0 |= var0 >> 8;
var0 |= var0 >> 16;
//>>>：無符號右移。無論是正數還是負數，高位通通補0. 這裏減了之後只剩下最高位為1
return var0 - (var0 >>> 1);
}
roundUpToPowerOf2方法是為了求一個比number大一點的2的冪次方的數,這裏的代碼看起來有點迷.它最後會求出數組應該初始化的長度,它可以自動將傳入的容量轉換為2的n次方.
Integer.highestOneBit是取傳入的這個數的二進制形式最左邊的最高一位且高位後面全部補零,最後返回int類型的結果.比如傳入的是7(0111),則最後得到的是4(0100).它這裏先將number-1,然後再左移一位,比如number是9,則number-1等於8(1000),左移一位等於10000就是16.這樣最後它就將傳入的容量轉換為了2的n次方.
計算好了容量之後,計算閾值,然後初始化數組.
3.1.1.2 putForNullKey 添加null key
用了一個專門的方法用來操作key為null的情況
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
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++;
addEntry(0, null, value, 0);
return null;
}將元素存放到了數組的第一個位置.第一個位置也是一個桶,這桶裏面只有一個元素的key可以是null,其他元素都是被hash算法分配到這裏來的.
3.1.1.3 計算hash值
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}獲取到了key的hashCode之後,又進行了一些騷操作,這裏的hash算法設計得很神,這裏的hash算法設計得好的話,則會大大減少hash衝突.
3.1.1.4 indexFor 計算元素在數組中的索引
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}用hash值按位與數組長度-1,相當於 h % length.&運算比%效率高,所以這裏是&運算來進行.為什麼h & (length-1) = h % length ? 這其實與length有關,length上面説過,必須是2的冪.我們簡單舉個例子,h=2,length=8.
h & (length-1)
= 00000010 & 00000111
= 00000010上面的最後結果是2 , 2 % 8 確實是等於2,驗證完畢.
3.1.1.5 addEntry 添加元素到數組中
添加元素的時候可能之前這個位置是空桶,也可能之前這裏的桶已經有元素存在了(hash衝突了).
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//1. 鍵值對數量超過閾值 && 該索引處數組不為空(説明這裏之前已經存在元素)
if ((size >= threshold) && (null != table[bucketIndex])) {
//擴容->原來的2倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//2. 創建Entry節點
createEntry(hash, key, value, bucketIndex);
}
//創建新的節點
void createEntry(int hash, K key, V value, int bucketIndex) {
//table[bucketIndex] 是放到新插入節點的後面,,所以這裏是頭插法
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
鍵值對超過閾值就會擴容
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, initHashSeedAsNeeded(newCapacity));
table = newTable;
//更新閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//轉移數據到新數組
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//元素非空 則轉移
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//根據該節點hash值計算一下該節點該放到新數組的哪個索引處
int i = indexFor(e.hash, newCapacity);
//將桶內元素逐個轉移到新的數組的新的索引處
//注意: 這裏桶內順序會倒過來.
//比如桶內是1->2->3 轉移數據之後就是3->2->1
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
擴容之後就涉及到數據的遷移,遷移的時候需要重新計算節點在新數組中的位置,遷移完成還得更新一下閾值.
JDK 1.7中的put操作就是這些啦,東西還挺多的. 最核心的也就是put部分的代碼,get的話比較簡單這裏就不做分析了.
3.2 JDK 1.8
基本上思路是差不多的,也是用數組+鏈表(or 紅黑樹)來裝數據.
transient Node<K,V>[] table;
//鏈表長度超過8且數組長度大於64,則將鏈表轉換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//在1.8中節點改名字了.. 改成了Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
來看看它的put方法是怎麼實現的
3.2.1 put
1.8的put方法稍微比1.7的看起來複雜些,但是不用怕,我們一句一句的分析
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. table為空表時,創建數組 初始化. resize既是初始化也是擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2. 根據hash和數組長度求出元素應該在數組中的索引位置,如果此處為空則將節點放到這裏
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//3. 該索引處已經有節點存在且hash值和key都相等(需要替換value),則記錄下該索引處的節點引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4. 如果該索引處是紅黑樹,則將節點插入到樹中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//5. 該索引處是鏈表
else {
//5.1 依次遍歷鏈表
for (int binCount = 0; ; ++binCount) {
//5.2 找到鏈表尾部,將節點插入到尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果鏈表長度超過8,則轉換成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//5.3 找到key相等的了,則結束for循環,已在鏈表中找到需要替換value的節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//6. 替換原來的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//7. 超過閾值,則擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}註釋寫得比較詳細,這裏與1.7的區別還是挺大的.
- Java7中將節點插入鏈表是頭插法,而Java8是尾插法
- Java8中鏈表超過8且數組長度大於64則會將鏈表樹化
- Java7將key為null的單獨處理,Java8沒有單獨處理(雖然它們的hash都是0,都是放數組第0處)
3.2.1.1 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() {
Node<K,V>[] oldTab = table;
//老數組長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//新數組長度 新閾值
int newCap, newThr = 0;
if (oldCap > 0) {
//老數組長度大於MAXIMUM_CAPACITY,則將閾值設置成Integer.MAX_VALUE 不擴容了..
//一般情況下,不會走到這個邏輯分支裏面去
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//1. 擴容: 將數組長度*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//閾值也是*2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//2. 初始化數組
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//3. 遍歷舊數組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//3.1 該索引處 桶內只有一個元素,根據該節點的hash和新數組長度求出該節點在新數組中的位置,然後放置到新數組中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//3.2 該索引處為紅黑樹 單獨處理
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//3.3 該索引處為單鏈表(鏈表長度小於8)
else { // preserve order
//不用挪動位置的鏈表,hash值&老數組長度為0,loHead為頭部,loTail為尾部
Node<K,V> loHead = null, loTail = null;
//需要挪動位置的鏈表,hash值&老數組長度為1,hiHead為頭部,hiTail為尾部
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//hash值&老數組長度
// 其實就是求最高位是0還是1,是0則保持原位置不動;是1則需要移動到 j + oldCap 處
//每條鏈表都被分散成2條,更分散
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);
//這些元素還是在老索引處
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//這些元素移動到了 老索引位置+oldCap 處
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}resize的東西比較雜,即包含了初始化數組,也包含了擴容的邏輯.初始化數組比較簡單,咱直接看一下擴容部分邏輯.首先是遍歷原數組,此時原數組的每個索引處可能存在3種情況
- 該索引處桶內只有一個元素->根據該節點的hash和新數組長度求出該節點在新數組中的位置,然後放置到新數組中
- 該索引處為紅黑樹->單獨處理
- 該索引處鏈表長度大於1,小於8
第3種情況比較複雜,這裏單獨分析一下.
分析前我們來看個東西,假設數組長度n=16,那麼根據put部分的代碼,存入數組時索引是(16 - 1) & hash,這裏有2個元素key1和key2,它們的hash值分別為5和21.下面是它們的計算過程
key1:
00001111 & 00000101 = 5
key2:
00001111 & 00010101 = 5當數組擴容,n=32
key1:
00011111 & 00000101 = 00101 = 5
key2:
00011111 & 00010101 = 10101 = 5 + 16 = 21擴容後n-1比以前多了1個1,這樣會導致按位與的時候key2的位置變成了原位置+16的位置.因為我們使用的是2次冪的擴展,所以元素的位置要麼在原位置,要麼在原位置+2次冪的位置.
有了上面的分析之後,再回到我們3.3處的邏輯
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;
}e.hash & oldCap: 用元素hash值與上老數組長度,假設之前數組長度是16,那麼這裏就是按位與10000,而平時put的時候算索引是按位與(n-1)也就是1111.擴容之後,在put的時候就得按位與11111.因此它這裏只是想看看hash值新增的那個bit是1還是0.如果是0則保留老位置,是1的話則在老位置的基礎上加老數組長度才是新的位置.
為什麼要這麼幹? 主要是計算簡單,不需要像JDK 1.7那樣還需要重新計算hash.還有就是讓元素更分散.本來原來是一條鏈上的,現在在2條鏈上(不同的數組索引處)了,查找更快了.
需要注意的一個小點就是,這裏是尾插法且還是原來的順序,而JDK 1.7是頭插法且順序與想來相反.
擴容的內容大概就是這些,稍微有點多.
4. 相關知識點
4.1 HashMap 1.7和1.8區別
- JDK1.7用的是頭插法,JDK1.8及置換是尾插法. 且1.7插入時候順序是與原來相反的,而1.8則還是原來的順序
- JDK1.7是數組+鏈表,JDK1.8是數組+鏈表+紅黑樹
- JDK1.7在插入數據之前進行擴容,JDK1.8是插入數據之後才擴容
- JDK1.7是Entry來表示節點,而JDK1.8是Node
- JDK1.7擴容和後存儲位置是用
hash & (length-1)計算來的,而JDK1.8只需要判斷hash值新增參與運算的位是0還是1就能快速計算出擴容後該放在原位置,還是需要放在 原位置+擴容的大小值 . - 計算hash值的時候,JDK1.7用了9次擾動處理,而JDK1.8是2次
ps: 紅黑樹查找元素,需要O（logn）的開銷
4.2 Hashtable與HashMap的區別
- Hashtable不支持null鍵和值
- Hashtable使用synchronized來進行同步(有性能開銷)
- Hashtable的迭代器是fail-fast迭代器
- Hashtable默認容量為11且不要求底層數組的容量一定要是2的整數次冪,而HashMap則是16,必須是2的整數次冪.
HashMap是絕大部分利用鍵值對存取場景的首選.多線程環境下,推薦使用ConcurrentHashMap.
參考
- 圖解HashMap(一)
- 圖解HashMap(二)
- Java 容器
- openjdk集合源碼
