HashMap 和 HashSet 是 Java Collection Framework 的兩個(gè)重要成員，其中 HashMap 是 Map 接口的常用實(shí)現(xiàn)類(lèi)，HashSet 是 Set 接口的常用實(shí)現(xiàn)類(lèi)。雖然 HashMap 和 HashSet 實(shí)現(xiàn)的接口規(guī)范不同，但它們底層的 Hash 存儲(chǔ)機(jī)制完全一樣，甚至 HashSet 本身就采用 HashMap 來(lái)實(shí)現(xiàn)的。
實(shí)際上，HashSet 和 HashMap 之間有很多相似之處，對(duì)于 HashSet 而言，系統(tǒng)采用 Hash 算法決定集合元素的存儲(chǔ)位置，這樣可以保證能快速存、取集合元素；對(duì)于 HashMap 而言，系統(tǒng) key-value 當(dāng)成一個(gè)整體進(jìn)行處理，系統(tǒng)總是根據(jù) Hash 算法來(lái)計(jì)算 key-value 的存儲(chǔ)位置，這樣可以保證能快速存、取 Map 的 key-value 對(duì)。
在介紹集合存儲(chǔ)之前需要指出一點(diǎn)：雖然集合號(hào)稱(chēng)存儲(chǔ)的是 Java 對(duì)象，但實(shí)際上并不會(huì)真正將 Java 對(duì)象放入 Set 集合中，只是在 Set 集合中保留這些對(duì)象的引用而言。也就是說(shuō)：Java 集合實(shí)際上是多個(gè)引用變量所組成的集合，這些引用變量指向?qū)嶋H的 Java 對(duì)象。
一、HashMap的基本特性
讀完JDK源碼HashMap.class中的注釋部分，可以總結(jié)出很多HashMap的特性。
HashMap允許key與value都為null, 而Hashtable是不允許的。
HashMap是線(xiàn)程不安全的， 而Hashtable是線(xiàn)程安全的
HashMap中的元素順序不是一直不變的，隨著時(shí)間的推移，同一元素的位置也可能改變（resize的情況）
遍歷HashMap的時(shí)間復(fù)雜度與其的容量(capacity)和現(xiàn)有元素的個(gè)數(shù)（size）成正比。如果要保證遍歷的高效性，初始容量（capacity)不能設(shè)置太高或者平衡因子（load factor）不能設(shè)置太低。
與之前的相關(guān)List同樣， 由于HashMap是線(xiàn)程不安全的, 因此迭代器在迭代過(guò)程中試圖做容器結(jié)構(gòu)上的改變的時(shí)候， 會(huì)產(chǎn)生fail-fast。通過(guò)Collections.synchronizedMap(HashMap)可以得到一個(gè)同步的HashMap
二、Hash table 數(shù)據(jù)結(jié)構(gòu)分析
Hash table(散列表，哈希表),是根據(jù)關(guān)鍵字而直接訪(fǎng)問(wèn)內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)散列表建立了關(guān)鍵字和存儲(chǔ)地址之間的一種直接映射
如下圖, key經(jīng)過(guò)散列函數(shù)得到buckets的一個(gè)索引位置。
通過(guò)散列函數(shù)獲取index不可避免會(huì)出現(xiàn)相同的情況，也就是沖突。下面簡(jiǎn)單介紹幾種解決沖突的方法：
Open addressing(開(kāi)放定址法):此方法的基本思想就是遇到?jīng)_突時(shí)，順序掃描表下N個(gè)位置，如果有空閑就填入。具體算法不再說(shuō)明，下面是示意圖：
Separate chaining(拉鏈)：此方法基本思想就是遇到?jīng)_突時(shí)，將相同索引值的Entry用鏈表串起來(lái)。具體算法不再說(shuō)明，下面是示意圖：
JDK中的HashMap解決沖突的方法就是用的Separate chaining法。
三、HashMap源碼分析（JDK1.7）
1、HashMap讀寫(xiě)元素
Entry
HashMap中的存放的元素是Entry類(lèi)型，下面給出源碼中Entry的源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
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; } //key, value的get與set方法省略，get與set操作會(huì)在后面的迭代器中用到 ... 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; } //此處將Key的hashcode與Value的hashcode做亦或運(yùn)算得到Entry的hashcode public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } } |
一個(gè)Entry包括key, value, hash以及下一個(gè)Entry的引用， 很明顯這是個(gè)單鏈表， 其實(shí)現(xiàn)了Map.Entry接口。
recordAcess(HashMap<K, V> 與recordRemoval(HashMap<K, V>)在HashMap中是沒(méi)有任何具體實(shí)現(xiàn)的。但是在LinkedHashMap這兩個(gè)方法用來(lái)實(shí)現(xiàn)LRU算法。
get：讀元素
從HashMap中獲取相應(yīng)的Entry， 下面給出get相關(guān)源碼：
|
1
2
3
4
5
6
7
8
|
public V get(Object key) { //key是null的情況 if (key == null) return getForNullKey(); //根據(jù)key查找Entry Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } |
getForNullKey源碼
|
1
2
3
4
5
6
7
8
9
10
11
|
private V getForNullKey() { if (size == 0) { return null; } //遍歷沖突鏈 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } |
key為Null的Entry存放在table[0]中，但是table[0]中的沖突鏈中不一定存在key為null， 因此需要遍歷。
根據(jù)key獲取entry：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); //通過(guò)hash得到table中的索引位置，然后遍歷沖突鏈表找到Key for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } |
以上就是HashMap讀取一個(gè)Entry的過(guò)程及其源碼。時(shí)間復(fù)雜度O(1)
put：寫(xiě)元素
HashMap中put操作相對(duì)復(fù)雜， 因?yàn)閜ut操作的過(guò)程中會(huì)有HashMap的擴(kuò)容操作。
新寫(xiě)入一個(gè)元素，如果HashMap中存在要寫(xiě)入元素的key，則執(zhí)行的是替換value的操作，相當(dāng)于update。下面是put源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public V put(K key, V value) { //空表table的話(huà)，根據(jù)size的閾值填充 if (table == EMPTY_TABLE) { inflateTable(threshold); } //填充key為Null的Entry if (key == null) return putForNullKey(value); //生成hash，得到索引Index的映射 int hash = hash(key); int i = indexFor(hash, table.length); //遍歷當(dāng)前索引的沖突鏈，找是否存在對(duì)應(yīng)的key for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果存在對(duì)應(yīng)的key， 則替換oldValue并返回oldValue if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //沖突鏈中不存在新寫(xiě)入的Entry的key modCount++; //插入一個(gè)新的Entry addEntry(hash, key, value, i); return null; } |
addEntry與createEntry源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void addEntry(int hash, K key, V value, int bucketIndex) { //插入新Entry前，先對(duì)當(dāng)前HashMap的size和其閾值大小的判斷，選擇是否擴(kuò)容 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]; //頭插法，新寫(xiě)入的entry插入當(dāng)前索引位置的沖突鏈第一個(gè)Entry的前面 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } |
以上就是HashMap寫(xiě)入一個(gè)Entry的過(guò)程及其源碼。時(shí)間復(fù)雜度O(1)
remove移除元素：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) { return null; } //根據(jù)key計(jì)算hash值，獲取索引 int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); //鏈表的刪除，定義兩個(gè)指針，pre表示前驅(qū) Entry<K,V> prev = table[i]; Entry<K,V> e = prev; //遍歷沖突鏈，刪除所有為key的Enrty while (e != null) { Entry<K,V> next = e.next; Object k; //找到了 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; //找到第一個(gè)結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn) if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } |
以上就是HashMap刪除一個(gè)Entry的過(guò)程及其源碼。時(shí)間復(fù)雜度O(1)
2、HashMap的哈希原理（hash function）
HashMap中散列函數(shù)的實(shí)現(xiàn)是通過(guò)hash(Object k) 與 indexFor(int h, int length)完成， 下面看下源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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);} |
獲取Index索引源碼：
|
1
2
3
4
|
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); } |
HashMap通過(guò)一個(gè)hash function將key映射到[0, table.length]的區(qū)間內(nèi)的索引。這樣的索引方法大體有兩種：
hash(key) % table.length, 其中l(wèi)ength必須為素?cái)?shù)。JDK中HashTable利用此實(shí)現(xiàn)方式。
具體使用素?cái)?shù)的原因，可以查找相關(guān)算法資料證明，這里不再陳述。
hash(key) & (table.length - 1 ) 其中l(wèi)ength必須為2指數(shù)次方。JDK中HashMap利用此實(shí)現(xiàn)方式。
因?yàn)閘ength的大小為2指數(shù)次方倍， 因此 hash(key) & (table.length - 1)總會(huì)在[0, length - 1]之間。但是僅僅這樣做的話(huà)會(huì)出現(xiàn)問(wèn)題一個(gè)沖突很大的問(wèn)題，因?yàn)镴AVA中hashCode的值為32位，當(dāng)HashMap的容量偏小，例如16時(shí)，做異或運(yùn)算時(shí)，高位總是被舍棄，低位運(yùn)算后卻增加了沖突發(fā)生的概率。
因此為了降低沖突發(fā)生的概率， 代碼中做了很多位運(yùn)算以及異或運(yùn)算。
3、HashMap內(nèi)存分配策略
成員變量capacity與loadFactor
HashMap中要求容量Capacity是2的指數(shù)倍， 默認(rèn)容量是1 << 4 = 16。HashMap中還存在一個(gè)平衡因子（loadFactor），過(guò)高的因子會(huì)降低存儲(chǔ)空間但是查找（lookup，包括HashMap中的put與get方法）的時(shí)間就會(huì)增加。 loadFactor默認(rèn)值為0.75是權(quán)衡了時(shí)間復(fù)雜度以及空間復(fù)雜度給出的最優(yōu)值。
|
1
2
3
|
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f; |
HashMap的構(gòu)造函數(shù)
HashMap的構(gòu)造就是設(shè)置capacity，與loadFactor的初始值
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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); this.loadFactor = loadFactor; threshold = initialCapacity; init(); } |
之前說(shuō)過(guò)HashMap中capacity必須是2的指數(shù)倍， 構(gòu)造函數(shù)里并沒(méi)有限制，那如何保證保證capacity的值是2的指數(shù)倍呢？
在put操作時(shí)候，源碼中會(huì)判斷目前的哈希表是否是空表，如果是則調(diào)用inflateTable(int toSize)
|
1
2
3
4
5
6
7
|
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); } |
其中roundUpToPowerOf2就是獲取大于等于給定參數(shù)的最小的2的n次冪
|
1
2
3
4
5
6
|
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.hightestOneBit(int)是將給定參數(shù)的最高位的1保留，剩下的變?yōu)?的操作，簡(jiǎn)單說(shuō)就是將參數(shù)int變?yōu)樾∮诘扔谒淖畲蟮?的n次冪。
若number為2的n次冪，減1后最高位處于原來(lái)的次高位， 再左移1位仍然可以定位到最高位位置
若number不是2的n次冪，減1左移1位后最高位仍是原來(lái)的最高位
擴(kuò)容：
HashMap在put操作的時(shí)候會(huì)發(fā)生resize行為，具體源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //哈希表已達(dá)到最大容量，1 << 30 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; //將oldTable中的Entry轉(zhuǎn)移到newTable中 //initHashSeedAsNeeded的返回值決定是否重新計(jì)算hash值 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; //重新計(jì)算threshold threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //遍歷oldTable for (Entry<K,V> e : table) { //遍歷沖突鏈 while(null != e) { Entry<K,V> next = e.next; if (rehash) { //重新計(jì)算hash值 e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //將元素插入到頭部，頭插法 e.next = newTable[i]; newTable[i] = e; e = next; } } } |
以上就是HashMap內(nèi)存分配的整個(gè)過(guò)程，總結(jié)說(shuō)來(lái)就是，hashMap在put一個(gè)Entry的時(shí)候會(huì)檢查當(dāng)前容量與threshold的大小來(lái)選擇是否擴(kuò)容。每次擴(kuò)容的大小是2 * table.length。在擴(kuò)容期間會(huì)根據(jù)initHashSeedAsNeeded判斷是否需要重新計(jì)算hash值。
四、HashMap的迭代器
HashMap中的ValueIterator， KeyIterator, EntryIterator等迭代器都是基于HashIterator的，下面看下它的源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot，table index Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; //在哈希表中找到第一個(gè)Entry if (size > 0) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { //HashMap是非線(xiàn)程安全的，遍歷時(shí)仍然先判斷是否有表結(jié)構(gòu)的修改 if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { //找到下一個(gè)Entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } } |
Key, Value, Entry這個(gè)三個(gè)迭代器進(jìn)行封裝就變成了keySet, values, entrySet三種集合視角。這三種集合視角都支持對(duì)HashMap的remove, removeAll, clear操作，不支持add， addAll操作。
