java集合類HashMap源碼解析
Map集合
Map集合存儲的是鍵值對
Map集合的實現(xiàn)類：
HashTable、LinkedHashMap、HashMap、TreeMap
HashMap
基礎(chǔ)了解：
1、鍵不可以重復，值可以重復；
2、底層使用哈希表實現(xiàn)；
3、線程不安全；
4、允許key為null，但只允許有一條記錄為null，value也可以為null，允許多條記錄為null；
源碼分析
（一）以JDK1.7為例
1、存儲結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表
首先hashmap內(nèi)部有一個Entry類型的數(shù)組table；
通過Entry<K,V> 知道table數(shù)組每一個節(jié)點，存儲的元素是鍵值對；
再通過字段next知道，每一個節(jié)點當出現(xiàn)哈希沖突的時候，會通過鏈表的形式將哈希值相同的節(jié)點放在同一個桶內(nèi)；
四個字段：K，V，next，hash；
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
}
2、拉鏈法的工作原理
HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");
新建一個 HashMap，默認大小為 16；
插入 <K1,V1> 鍵值對，先計算 K1 的 hashCode 為 115，使用除留余數(shù)法得到所在的桶下標 115%16=3。
插入 <K2,V2> 鍵值對，先計算 K2 的 hashCode 為 118，使用除留余數(shù)法得到所在的桶下標 118%16=6。
插入 <K3,V3> 鍵值對，先計算 K3 的 hashCode 為 118，使用除留余數(shù)法得到所在的桶下標 118%16=6，插在 <K2,V2> 前面。
應該注意到鏈表的插入是以頭插法方式進行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在鏈表頭部。
查找需要分成兩步進行：
計算鍵值對所在的桶；
在鏈表上順序查找，時間復雜度顯然和鏈表的長度成正比
3、put()方法
put方法調(diào)用
1.調(diào)用hash函數(shù)得到key的HashCode值
2.通過HashCode值與數(shù)組長度-1邏輯與運算得到一個index值
3.遍歷索引位置對應的鏈表，如果Entry對象的hash值與hash函數(shù)得到的hash值相等，并且該Entry對象的key值與put方法傳過來的key值相等則，將該Entry對象的value值賦給一個變量，將該Entry對象的value值重新設置為put方法傳過來的value值。將舊的value返回。
4.添加Entry對象到相應的索引位置
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 鍵為 null 單獨處理
if (key == null)
return putForNullKey(value);
int hash = hash(key);
// 確定桶下標
int i = indexFor(hash, table.length);
// 先找出是否已經(jīng)存在鍵為 key 的鍵值對，如果存在的話就更新這個鍵值對的值為 value
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++;
// 插入新鍵值對
addEntry(hash, key, value, i);
return null;
}
HashMap 允許插入鍵為 null 的鍵值對。但是因為無法調(diào)用 null 的 hashCode() 方法，也就無法確定該鍵值對的桶下標，只能通過強制指定一個桶下標來存放。HashMap 使用第 0 個桶存放鍵為 null 的鍵值對
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;
}
使用鏈表的頭插法，也就是新的鍵值對插在鏈表的頭部，而不是鏈表的尾部。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
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++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
4、確定桶下標
很多操作都需要先確定一個鍵值對所在的桶下標。如上所示代碼
int hash = hash(key); int i = indexFor(hash, table.length);
4.1、確定hash值
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);
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
4.2、取模確定桶下標
令 x = 1<<4，即 x 為 2 的 4 次方，它具有以下性質(zhì)：
x : 00010000 x-1 : 00001111
令一個數(shù) y 與 x-1 做與運算，可以去除 y 位級表示的第 4 位以上數(shù)：
y : 10110010 x-1 : 00001111 y&(x-1) : 00000010
這個性質(zhì)和 y 對 x 取模效果是一樣的：
y : 10110010 x : 00010000 y%x : 00000010
我們知道，位運算的代價比求模運算小的多，因此在進行這種計算時用位運算的話能帶來更高的性能。
確定桶下標的最后一步是將 key 的 hash 值對桶個數(shù)取模：hash%capacity，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個操作轉(zhuǎn)換為位運算。
static int indexFor(int h, int length) {
return h & (length-1);
}
面試題目：hashmap的初始容量值為什么設置為16？
原因1、根據(jù)確定桶下標的原理， h & (length-1)，長度length為2的整數(shù)次冪可以保證散列的均勻，提升效率；
原因2、因為length為偶數(shù)，length-1必為奇數(shù)，所以h值的奇偶數(shù)決定了散列表數(shù)組落入奇數(shù)或者偶數(shù)數(shù)組內(nèi)；這樣保證了散列的均勻性。而如果length為奇數(shù)，那么length-1位偶數(shù)，最后一位為0，根據(jù) 邏輯 & 的原則碼，最后一位肯定都是偶數(shù)0，而不可能出現(xiàn)奇數(shù)1，所以散列表只能使用一半的數(shù)組，造成很大的浪費；
5、擴容原理
HashMap的初始容量是2的n次冪，擴容也是2倍的形式進行擴容，是因為容量是2的n次冪，可以使得添加的元素均勻分布在HashMap中的數(shù)組上，減少hash碰撞，避免形成鏈表的結(jié)構(gòu)，使得查詢效率降低！
static final int DEFAULT_INITIAL_CAPACITY = 16; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; transient Entry[] table; transient int size; int threshold; final float loadFactor; transient int modCount;
從下面的添加元素代碼中可以看出，當需要擴容時，令 capacity 為原來的兩倍
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
擴容使用 resize() 實現(xiàn)，需要注意的是，擴容操作同樣需要把 oldTable 的所有鍵值對重新插入 newTable 中，因此這一步是很費時的。
多線程下擴容會出現(xiàn)HashMap的循環(huán)鏈表情況
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++) {
Entry<K,V> e = src[j];
if (e != null) {
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);
}
}
}
6、擴容-重新計算桶下標
在進行擴容時，需要把鍵值對重新放到對應的桶上。HashMap 使用了一個特殊的機制，可以降低重新計算桶下標的操作。
假設原數(shù)組長度 capacity 為 16，擴容之后 new capacity 為 32：
capacity : 00010000 new capacity : 00100000 對于一個 Key，
它的哈希值如果在第 5 位上為 0，那么取模得到的結(jié)果和之前一樣；如果為 1，那么得到的結(jié)果為原來的結(jié)果 +16。
7、計算數(shù)組容量
HashMap 構(gòu)造函數(shù)允許用戶傳入的容量不是 2 的 n 次方，因為它可以自動地將傳入的容量轉(zhuǎn)換為 2 的 n 次方。
先考慮如何求一個數(shù)的掩碼，對于 10010000，它的掩碼為 11111111，可以使用以下方法得到：
mask |= mask >> 1 11011000 mask |= mask >> 2 11111110 mask |= mask >> 4 11111111
mask+1 是大于原始數(shù)字的最小的 2 的 n 次方。
num 10010000 mask+1 100000000
以下是 HashMap 中計算數(shù)組容量的代碼：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
8、JDK1.8開始，鏈表轉(zhuǎn)換為紅黑樹
從 JDK 1.8 開始，一個桶存儲的鏈表長度大于 8 時會將鏈表轉(zhuǎn)換為紅黑樹。
數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹
get()
get方法調(diào)用
1.當調(diào)用get方法時會調(diào)用hash函數(shù)，這個hash函數(shù)會將key的hashCode值返回，返回的hashCode與Entry數(shù)組長度-1進行邏輯與運算得到一個index值，用這個index值來確定數(shù)據(jù)存儲在Entry數(shù)組當中的位置
2.通過循環(huán)來遍歷索引位置對應的鏈表，初始值為數(shù)據(jù)存儲在Entry數(shù)組當中的位置，循環(huán)條件為Entry對象不為null，改變循環(huán)條件為Entry對象的下一個節(jié)點
3.如果hash函數(shù)得到的hash值與Entry對象當中key的hash值相等，并且Entry對象當中的key值與get方法傳進來的key值equals相同則返回該Entry對象的value值，否則返回null
我們能否讓HashMap同步？
在多線程條件下，容易導致死循環(huán)，具體表現(xiàn)為CPU使用率100%。因此多線程環(huán)境下保證 HashMap 的線程安全性，主要有如下幾種方法：
1、使用 java.util.Hashtable 類，此類是線程安全的。
2、使用 java.util.concurrent.ConcurrentHashMap，此類是線程安全的。
3、使用 java.util.Collections.synchronizedMap() 方法包裝 HashMap object，得到線程安全的Map，并在此Map上進行操作。
通過Collections.synchronizedMap()來封裝所有不安全的HashMap的方法,就連toString, hashCode都進行了封裝. 封裝的關(guān)鍵點有2處
(1)使用了經(jīng)典的synchronized來進行互斥,
(2)使用了代理模式new了一個新的類,這個類同樣實現(xiàn)了Map接口
到此這篇關(guān)于HashMap集合類的寫法的文章就介紹到這了,更多相關(guān)Java遍歷HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Spring?@Transactional事務失效的原因分析
一個程序中不可能沒有事務，Spring中，事務的實現(xiàn)方式分為兩種：編程式事務和聲明式事務。日常項目中，我們都會使用聲明式事務?@Transactional來實現(xiàn)事務，本文來和大家聊聊什么情況會導致@Transactional事務失效2022-09-09
今天小編就為大家分享一篇關(guān)于Java利用移位運算將int型分解成四個byte型的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了MyBatis中XML 映射文件中常見的標簽說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
本文主要介紹如何將本地Java項目resources目錄下的一個PNG圖片上傳到MinIO，然后將上傳的圖片刪除，文中有詳細的流程步驟和示例代碼,需要的朋友可以參考下2023-06-06
這篇文章主要介紹了springboot 啟動如何排除某些bean的注入方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
ArrayList和HashMap如何自己實現(xiàn)實例詳解
這篇文章主要介紹了 ArrayList和HashMap如何自己實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2016-12-12
這篇文章主要介紹了Mybatis如何分割字符串問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
這篇文章主要介紹了Spring使用xml方式整合第三方框架流程，Spring會在應用上下文中為某個bean尋找其依賴的bean，Spring中bean有三種裝配機制，分別是：在xml中顯式配置、在java中顯式配置、隱式的bean發(fā)現(xiàn)機制和自動裝配2023-02-02
Maven是一個能使我們的java程序開發(fā)節(jié)省時間和精力,是開發(fā)變得相對簡單,還能使開發(fā)規(guī)范化的工具,下面這篇文章主要給大家介紹了關(guān)于idea中Maven鏡像源詳細配置(對所有項目)的相關(guān)資料,需要的朋友可以參考下2023-05-05
本文介紹關(guān)于jmap和MAT的使用來進行堆內(nèi)存溢出分析，因為這個內(nèi)存溢出是我們手動構(gòu)造出來的，查找比較簡單，真的到了生產(chǎn)上面需要我們仔細排除2021-09-09