目錄Map集合HashMap源碼分析1、存儲(chǔ)結(jié)構(gòu)2、拉鏈法的工作原理3、put()方法4、確定桶下標(biāo)4.1、確定hash值4.2、取模確定桶下標(biāo)5、擴(kuò)容原理6、擴(kuò)容-重新計(jì)算桶下標(biāo)7、計(jì)算數(shù)組容量8、JDK1.8開(kāi)始，鏈表轉(zhuǎn)換為紅黑樹(shù)get()我們能否讓HashMap同步？

Map集合

Map集合存儲(chǔ)的是鍵值對(duì)

Map集合的實(shí)現(xiàn)類：

HashTable、LinkedHashMap、HashMap、TreeMap

HashMap

基礎(chǔ)了解：

1、鍵不可以重復(fù)，值可以重復(fù)；

2、底層使用哈希表實(shí)現(xiàn)；

3、線程不安全；

4、允許key為null，但只允許有一條記錄為null，value也可以為null，允許多條記錄為null；

源碼分析

（一）以JDK1.7為例

1、存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表

首先hashmap內(nèi)部有一個(gè)Entry類型的數(shù)組table；

通過(guò)Entry<K,V> 知道table數(shù)組每一個(gè)節(jié)點(diǎn)，存儲(chǔ)的元素是鍵值對(duì)；

再通過(guò)字段next知道，每一個(gè)節(jié)點(diǎn)當(dāng)出現(xiàn)哈希沖突的時(shí)候，會(huì)通過(guò)鏈表的形式將哈希值相同的節(jié)點(diǎn)放在同一個(gè)桶內(nèi)；

四個(gè)字段：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');

新建一個(gè) HashMap，默認(rèn)大小為 16；

插入 <K1,V1> 鍵值對(duì)，先計(jì)算 K1 的 hashCode 為 115，使用除留余數(shù)法得到所在的桶下標(biāo) 115%16=3。

插入 <K2,V2> 鍵值對(duì)，先計(jì)算 K2 的 hashCode 為 118，使用除留余數(shù)法得到所在的桶下標(biāo) 118%16=6。

插入 <K3,V3> 鍵值對(duì)，先計(jì)算 K3 的 hashCode 為 118，使用除留余數(shù)法得到所在的桶下標(biāo) 118%16=6，插在 <K2,V2> 前面。

應(yīng)該注意到鏈表的插入是以頭插法方式進(jìn)行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在鏈表頭部。

查找需要分成兩步進(jìn)行：

計(jì)算鍵值對(duì)所在的桶；

在鏈表上順序查找，時(shí)間復(fù)雜度顯然和鏈表的長(zhǎng)度成正比

3、put()方法

put方法調(diào)用

1.調(diào)用hash函數(shù)得到key的HashCode值

2.通過(guò)HashCode值與數(shù)組長(zhǎng)度-1邏輯與運(yùn)算得到一個(gè)index值

3.遍歷索引位置對(duì)應(yīng)的鏈表，如果Entry對(duì)象的hash值與hash函數(shù)得到的hash值相等，并且該Entry對(duì)象的key值與put方法傳過(guò)來(lái)的key值相等則，將該Entry對(duì)象的value值賦給一個(gè)變量，將該Entry對(duì)象的value值重新設(shè)置為put方法傳過(guò)來(lái)的value值。將舊的value返回。

4.添加Entry對(duì)象到相應(yīng)的索引位置

public V put(K key, V value) { if (table == EMPTY_TABLE) {inflateTable(threshold); } // 鍵為 null 單獨(dú)處理 if (key == null)return putForNullKey(value); int hash = hash(key); // 確定桶下標(biāo) int i = indexFor(hash, table.length); // 先找出是否已經(jīng)存在鍵為 key 的鍵值對(duì)，如果存在的話就更新這個(gè)鍵值對(duì)的值為 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++; // 插入新鍵值對(duì) addEntry(hash, key, value, i); return null;}

HashMap 允許插入鍵為 null 的鍵值對(duì)。但是因?yàn)闊o(wú)法調(diào)用 null 的 hashCode() 方法，也就無(wú)法確定該鍵值對(duì)的桶下標(biāo)，只能通過(guò)強(qiáng)制指定一個(gè)桶下標(biāo)來(lái)存放。HashMap 使用第 0 個(gè)桶存放鍵為 null 的鍵值對(duì)

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;}

使用鏈表的頭插法，也就是新的鍵值對(duì)插在鏈表的頭部，而不是鏈表的尾部。

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]; // 頭插法，鏈表頭部指向新的鍵值對(duì) 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、確定桶下標(biāo)

很多操作都需要先確定一個(gè)鍵值對(duì)所在的桶下標(biāo)。如上所示代碼

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、取模確定桶下標(biāo)

令 x = 1<<4，即 x 為 2 的 4 次方，它具有以下性質(zhì)：

x : 00010000x-1 : 00001111

令一個(gè)數(shù) y 與 x-1 做與運(yùn)算，可以去除 y 位級(jí)表示的第 4 位以上數(shù)：

y : 10110010x-1 : 00001111y&(x-1) : 00000010

這個(gè)性質(zhì)和 y 對(duì) x 取模效果是一樣的：

y : 10110010x : 00010000y%x : 00000010

我們知道，位運(yùn)算的代價(jià)比求模運(yùn)算小的多，因此在進(jìn)行這種計(jì)算時(shí)用位運(yùn)算的話能帶來(lái)更高的性能。

確定桶下標(biāo)的最后一步是將 key 的 hash 值對(duì)桶個(gè)數(shù)取模：hash%capacity，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個(gè)操作轉(zhuǎn)換為位運(yùn)算。

static int indexFor(int h, int length) { return h & (length-1);}

面試題目：hashmap的初始容量值為什么設(shè)置為16？

原因1、根據(jù)確定桶下標(biāo)的原理， h & (length-1)，長(zhǎng)度length為2的整數(shù)次冪可以保證散列的均勻，提升效率；

原因2、因?yàn)閘ength為偶數(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ù)組，造成很大的浪費(fèi)；

5、擴(kuò)容原理

HashMap的初始容量是2的n次冪，擴(kuò)容也是2倍的形式進(jìn)行擴(kuò)容，是因?yàn)槿萘渴?的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;

從下面的添加元素代碼中可以看出，當(dāng)需要擴(kuò)容時(shí)，令 capacity 為原來(lái)的兩倍

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);}

擴(kuò)容使用 resize() 實(shí)現(xiàn)，需要注意的是，擴(kuò)容操作同樣需要把 oldTable 的所有鍵值對(duì)重新插入 newTable 中，因此這一步是很費(fèi)時(shí)的。

多線程下擴(kuò)容會(huì)出現(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、擴(kuò)容-重新計(jì)算桶下標(biāo)

在進(jìn)行擴(kuò)容時(shí)，需要把鍵值對(duì)重新放到對(duì)應(yīng)的桶上。HashMap 使用了一個(gè)特殊的機(jī)制，可以降低重新計(jì)算桶下標(biāo)的操作。

假設(shè)原數(shù)組長(zhǎng)度 capacity 為 16，擴(kuò)容之后 new capacity 為 32：

capacity : 00010000new capacity : 00100000對(duì)于一個(gè) Key，

它的哈希值如果在第 5 位上為 0，那么取模得到的結(jié)果和之前一樣；如果為 1，那么得到的結(jié)果為原來(lái)的結(jié)果 +16。

7、計(jì)算數(shù)組容量

HashMap 構(gòu)造函數(shù)允許用戶傳入的容量不是 2 的 n 次方，因?yàn)樗梢宰詣?dòng)地將傳入的容量轉(zhuǎn)換為 2 的 n 次方。

先考慮如何求一個(gè)數(shù)的掩碼，對(duì)于 10010000，它的掩碼為 11111111，可以使用以下方法得到：

mask |= mask >> 1 11011000mask |= mask >> 2 11111110mask |= mask >> 4 11111111

mask+1 是大于原始數(shù)字的最小的 2 的 n 次方。

num 10010000mask+1 100000000

以下是 HashMap 中計(jì)算數(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開(kāi)始，鏈表轉(zhuǎn)換為紅黑樹(shù)

從 JDK 1.8 開(kāi)始，一個(gè)桶存儲(chǔ)的鏈表長(zhǎng)度大于 8 時(shí)會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)。

數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹(shù)

get()

get方法調(diào)用

1.當(dāng)調(diào)用get方法時(shí)會(huì)調(diào)用hash函數(shù)，這個(gè)hash函數(shù)會(huì)將key的hashCode值返回，返回的hashCode與Entry數(shù)組長(zhǎng)度-1進(jìn)行邏輯與運(yùn)算得到一個(gè)index值，用這個(gè)index值來(lái)確定數(shù)據(jù)存儲(chǔ)在Entry數(shù)組當(dāng)中的位置

2.通過(guò)循環(huán)來(lái)遍歷索引位置對(duì)應(yīng)的鏈表，初始值為數(shù)據(jù)存儲(chǔ)在Entry數(shù)組當(dāng)中的位置，循環(huán)條件為Entry對(duì)象不為null，改變循環(huán)條件為Entry對(duì)象的下一個(gè)節(jié)點(diǎn)

3.如果hash函數(shù)得到的hash值與Entry對(duì)象當(dāng)中key的hash值相等，并且Entry對(duì)象當(dāng)中的key值與get方法傳進(jìn)來(lái)的key值equals相同則返回該Entry對(duì)象的value值，否則返回null

我們能否讓HashMap同步？

在多線程條件下，容易導(dǎo)致死循環(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上進(jìn)行操作。

通過(guò)Collections.synchronizedMap()來(lái)封裝所有不安全的HashMap的方法,就連toString, hashCode都進(jìn)行了封裝. 封裝的關(guān)鍵點(diǎn)有2處

(1)使用了經(jīng)典的synchronized來(lái)進(jìn)行互斥,

(2)使用了代理模式new了一個(gè)新的類,這個(gè)類同樣實(shí)現(xiàn)了Map接口

到此這篇關(guān)于HashMap集合類的寫(xiě)法的文章就介紹到這了,更多相關(guān)Java遍歷HashMap內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！