HashMap 和 HashSet 是 Java Collection Framework 的兩個重要成員，其中 HashMap 是 Map 接口的常用實現類，HashSet 是 Set 接口的常用實現類。雖然 HashMap 和 HashSet 實現的接口規范不同，但它們底層的 Hash 存儲機制完全一樣，甚至 HashSet 本身就采用 HashMap 來實現的。
實際上，HashSet 和 HashMap 之間有很多相似之處，對于 HashSet 而言，系統采用 Hash 算法決定集合元素的存儲位置，這樣可以保證能快速存、取集合元素；對于 HashMap 而言，系統 key-value 當成一個整體進行處理，系統總是根據 Hash 算法來計算 key-value 的存儲位置，這樣可以保證能快速存、取 Map 的 key-value 對。
在介紹集合存儲之前需要指出一點：雖然集合號稱存儲的是 Java 對象，但實際上并不會真正將 Java 對象放入 Set 集合中，只是在 Set 集合中保留這些對象的引用而言。也就是說：Java 集合實際上是多個引用變量所組成的集合，這些引用變量指向實際的 Java 對象。
一、HashMap的基本特性
讀完JDK源碼HashMap.class中的注釋部分，可以總結出很多HashMap的特性。
HashMap允許key與value都為null, 而Hashtable是不允許的。
HashMap是線程不安全的， 而Hashtable是線程安全的
HashMap中的元素順序不是一直不變的，隨著時間的推移，同一元素的位置也可能改變（resize的情況）
遍歷HashMap的時間復雜度與其的容量(capacity)和現有元素的個數（size）成正比。如果要保證遍歷的高效性，初始容量（capacity)不能設置太高或者平衡因子（load factor）不能設置太低。
與之前的相關List同樣， 由于HashMap是線程不安全的, 因此迭代器在迭代過程中試圖做容器結構上的改變的時候， 會產生fail-fast。通過Collections.synchronizedMap(HashMap)可以得到一個同步的HashMap
二、Hash table 數據結構分析
Hash table(散列表，哈希表),是根據關鍵字而直接訪問內存存儲位置的數據結構。也就是說散列表建立了關鍵字和存儲地址之間的一種直接映射
如下圖, key經過散列函數得到buckets的一個索引位置。
通過散列函數獲取index不可避免會出現相同的情況，也就是沖突。下面簡單介紹幾種解決沖突的方法：
Open addressing(開放定址法):此方法的基本思想就是遇到沖突時，順序掃描表下N個位置，如果有空閑就填入。具體算法不再說明，下面是示意圖：
Separate chaining(拉鏈)：此方法基本思想就是遇到沖突時，將相同索引值的Entry用鏈表串起來。具體算法不再說明，下面是示意圖：
JDK中的HashMap解決沖突的方法就是用的Separate chaining法。
三、HashMap源碼分析（JDK1.7）
1、HashMap讀寫元素
Entry
HashMap中的存放的元素是Entry類型，下面給出源碼中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操作會在后面的迭代器中用到 ... 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做亦或運算得到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) { } } |
一個Entry包括key, value, hash以及下一個Entry的引用， 很明顯這是個單鏈表， 其實現了Map.Entry接口。
recordAcess(HashMap<K, V> 與recordRemoval(HashMap<K, V>)在HashMap中是沒有任何具體實現的。但是在LinkedHashMap這兩個方法用來實現LRU算法。
get：讀元素
從HashMap中獲取相應的Entry， 下面給出get相關源碼：
|
1
2
3
4
5
6
7
8
|
public V get(Object key) { //key是null的情況 if (key == null) return getForNullKey(); //根據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， 因此需要遍歷。
根據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); //通過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讀取一個Entry的過程及其源碼。時間復雜度O(1)
put：寫元素
HashMap中put操作相對復雜， 因為put操作的過程中會有HashMap的擴容操作。
新寫入一個元素，如果HashMap中存在要寫入元素的key，則執行的是替換value的操作，相當于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的話，根據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); //遍歷當前索引的沖突鏈，找是否存在對應的key for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果存在對應的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; } } //沖突鏈中不存在新寫入的Entry的key modCount++; //插入一個新的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前，先對當前HashMap的size和其閾值大小的判斷，選擇是否擴容 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]; //頭插法，新寫入的entry插入當前索引位置的沖突鏈第一個Entry的前面 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } |
以上就是HashMap寫入一個Entry的過程及其源碼。時間復雜度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; } //根據key計算hash值，獲取索引 int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); //鏈表的刪除，定義兩個指針，pre表示前驅 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--; //找到第一個結點就是要刪除的結點 if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } |
以上就是HashMap刪除一個Entry的過程及其源碼。時間復雜度O(1)
2、HashMap的哈希原理（hash function）
HashMap中散列函數的實現是通過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通過一個hash function將key映射到[0, table.length]的區間內的索引。這樣的索引方法大體有兩種：
hash(key) % table.length, 其中length必須為素數。JDK中HashTable利用此實現方式。
具體使用素數的原因，可以查找相關算法資料證明，這里不再陳述。
hash(key) & (table.length - 1 ) 其中length必須為2指數次方。JDK中HashMap利用此實現方式。
因為length的大小為2指數次方倍， 因此 hash(key) & (table.length - 1)總會在[0, length - 1]之間。但是僅僅這樣做的話會出現問題一個沖突很大的問題，因為JAVA中hashCode的值為32位，當HashMap的容量偏小，例如16時，做異或運算時，高位總是被舍棄，低位運算后卻增加了沖突發生的概率。
因此為了降低沖突發生的概率， 代碼中做了很多位運算以及異或運算。
3、HashMap內存分配策略
成員變量capacity與loadFactor
HashMap中要求容量Capacity是2的指數倍， 默認容量是1 << 4 = 16。HashMap中還存在一個平衡因子（loadFactor），過高的因子會降低存儲空間但是查找（lookup，包括HashMap中的put與get方法）的時間就會增加。 loadFactor默認值為0.75是權衡了時間復雜度以及空間復雜度給出的最優值。
|
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的構造函數
HashMap的構造就是設置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(); } |
之前說過HashMap中capacity必須是2的指數倍， 構造函數里并沒有限制，那如何保證保證capacity的值是2的指數倍呢？
在put操作時候，源碼中會判斷目前的哈希表是否是空表，如果是則調用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就是獲取大于等于給定參數的最小的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)是將給定參數的最高位的1保留，剩下的變為0的操作，簡單說就是將參數int變為小于等于它的最大的2的n次冪。
若number為2的n次冪，減1后最高位處于原來的次高位， 再左移1位仍然可以定位到最高位位置
若number不是2的n次冪，減1左移1位后最高位仍是原來的最高位
擴容：
HashMap在put操作的時候會發生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; //哈希表已達到最大容量，1 << 30 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; //將oldTable中的Entry轉移到newTable中 //initHashSeedAsNeeded的返回值決定是否重新計算hash值 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; //重新計算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) { //重新計算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內存分配的整個過程，總結說來就是，hashMap在put一個Entry的時候會檢查當前容量與threshold的大小來選擇是否擴容。每次擴容的大小是2 * table.length。在擴容期間會根據initHashSeedAsNeeded判斷是否需要重新計算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; //在哈希表中找到第一個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是非線程安全的，遍歷時仍然先判斷是否有表結構的修改 if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { //找到下一個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這個三個迭代器進行封裝就變成了keySet, values, entrySet三種集合視角。這三種集合視角都支持對HashMap的remove, removeAll, clear操作，不支持add， addAll操作。
