存儲結(jié)構(gòu)
首先，HashMap是基于哈希表存儲的。它內(nèi)部有一個數(shù)組，當元素要存儲的時候，先計算其key的哈希值，根據(jù)哈希值找到元素在數(shù)組中對應(yīng)的下標。如果這個位置沒有元素，就直接把當前元素放進去，如果有元素了(這里記為A)，就把當前元素鏈接到元素A的前面，然后把當前元素放入數(shù)組中。所以在Hashmap中，數(shù)組其實保存的是鏈表的首節(jié)點。下面是百度百科的一張圖：
如上圖，每個元素是一個Entry對象，在其中保存了元素的key和value，還有一個指針可用于指向下一個對象。所有哈希值相同的key(也就是沖突了)用鏈表把它們串起來，這是拉鏈法。
內(nèi)部變量
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
//默認初始容量static final int DEFAULT_INITIAL_CAPACITY = 16;//最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//默認裝載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//哈希表transient Entry<K,V>[] table;//鍵值對的數(shù)量transient int size;//擴容的閾值int threshold;//哈希數(shù)組的裝載因子final float loadFactor; |
在上面的變量中，capacity是指哈希表的長度，也就是table的大小，默認為16。裝載因子loadFactor是哈希表的“裝滿程度”，JDK的文檔是這樣說的：
The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
大體意思是：裝載因子是哈希表在擴容之前能裝多滿的度量值。當哈希表中“鍵值對”的數(shù)量超過當前容量(capacity)和裝載因子的乘積后，哈希表重新散列(也就是內(nèi)部的數(shù)據(jù)結(jié)構(gòu)重建了)，并且哈希表的容量大約變?yōu)樵瓉淼膬杀丁?/p>
從上面的變量定義可以看出，默認的裝載因子DEFAULT_LOAD_FACTOR 是0.75。這個值越大，空間利用率越高，但查詢速度(包括get和put)操作會變慢。明白了裝載因子之后，threshold也就能理解了，它其實等于容量*裝載因子。
構(gòu)造器
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) //計算出大于指定容量的最小的2的冪 capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; //給哈希表分配空間 useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init();} |
構(gòu)造器有好幾個，最終都會調(diào)用上面的這個。它接受兩個參數(shù)，一個是初始容量，還有一個是裝載因子。剛開始先判斷值合不合法，有問題的話會拋出異常。重要的是下面的capacity的計算，它的邏輯是計算出大于initialCapacity的最小的2的冪。其實目的就是要讓容量能大于等于指定的初始容量，但這個值還得是2的指數(shù)倍，這是一個關(guān)鍵的問題。這么做的原因主要是為了哈希值的映射。先來看一下HashMap中有關(guān)哈希的方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } 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);}static int indexFor(int h, int length) { return h & (length-1);} |
hash()方法重新計算了key的哈希值，用了比較復(fù)雜的位運算，具體邏輯我也不清楚，反正肯定是比較好的方法，能減少沖突什么的。
下面的indexFor()是根據(jù)哈希值得到元素在哈希表中的下標。一般在哈希表中是用哈希值對表長取模得到。當length(也就是capacity)為2的冪時，h & (length-1)是同樣的效果。并且，2的冪一定是偶數(shù)，那么減1之后就是奇數(shù)，二進制的最后一位一定是1。那么h & (length-1)的最后一位可能是1，也可能是0，可以均勻地散列。如果length是奇數(shù)，那么length-1就是偶數(shù)，最后一位是0。此時h & (length-1)的最后一位只可能是0，所有得到的下標都是偶數(shù)，那么哈希表就浪費了一半的空間。所以HashMap中的容量(capacity)一定要是2的冪。可以看到默認的DEFAULT_INITIAL_CAPACITY=16和MAXIMUM_CAPACITY=1<<30都是這樣的。
Entry對象
HashMap中的鍵值對被封裝成Entry對象，這是HashMap中的一個內(nèi)部類，看一下它的實現(xiàn)：
|
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
49
50
51
52
53
54
55
|
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 (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } void recordAccess(HashMap<K,V> m) { } void recordRemoval(HashMap<K,V> m) { }} |
這個類的實現(xiàn)還是簡潔易懂的。提供了getKey()、getValue()等方法供調(diào)用，判斷相等是要求key和value均相等。
put操作
先put了才能get，所以先看一下put()方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); 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;} |
在這個方法中，先判斷key是否為null，是的話調(diào)用putForNullKey()方法，這說明HashMap允許key為null(其實value可以)。如果不是null，計算哈希值并且得到在表中的下標。然后到對應(yīng)的鏈表中查詢是否已經(jīng)存在相同的key，如果已經(jīng)存在就直接更新值(value)。否則，調(diào)用addEntry()方法進行插入。
看一下putForNullKey()方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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時直接在下標0處插入，同樣是存在就更新值，否則調(diào)用addEntry()插入。
下面是addEntry()方法的實現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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++;} |
首先判斷是否要擴容(擴容會重新計算下標值，并且復(fù)制元素)，然后計算數(shù)組下標，最后在createEntry()中使用頭插法插入元素。
get操作
|
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
|
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue();}private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null;}final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(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;} |
這個比put()簡單一些，同樣要判斷key是不是null，然后就是鏈表的遍歷查詢。
性能優(yōu)化
HashMap是一個高效通用的數(shù)據(jù)結(jié)構(gòu)，它在每一個Java程序中都隨處可見。先來介紹些基礎(chǔ)知識。你可能也知 道，HashMap使用key的hashCode()和equals()方法來將值劃分到不同的桶里。桶的數(shù)量通常要比map中的記錄的數(shù)量要稍大，這樣 每個桶包括的值會比較少（最好是一個）。當通過key進行查找時，我們可以在常數(shù)時間內(nèi)迅速定位到某個桶（使用hashCode()對桶的數(shù)量進行取模） 以及要找的對象。
這些東西你應(yīng)該都已經(jīng)知道了。你可能還知道哈希碰撞會對hashMap的性能帶來災(zāi)難性的影響。如果多個hashCode()的值落到同一個桶內(nèi)的 時候，這些值是存儲到一個鏈表中的。最壞的情況下，所有的key都映射到同一個桶中，這樣hashmap就退化成了一個鏈表——查找時間從O(1)到 O(n)。我們先來測試下正常情況下hashmap在Java 7和Java 8中的表現(xiàn)。為了能完成控制hashCode()方法的行為，我們定義了如下的一個Key類：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Key implements Comparable<Key> {private final int value;Key(int value) {this.value = value;}@Overridepublic int compareTo(Key o) {return Integer.compare(this.value, o.value);}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass())return false;Key key = (Key) o;return value == key.value;}@Overridepublic int hashCode() {return value;}} |
Key類的實現(xiàn)中規(guī)中矩：它重寫了equals()方法并且提供了一個還算過得去的hashCode()方法。為了避免過度的GC，我將不可變的Key對象緩存了起來，而不是每次都重新開始創(chuàng)建一遍：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class Key implements Comparable<Key> {public class Keys {public static final int MAX_KEY = 10_000_000;private static final Key[] KEYS_CACHE = new Key[MAX_KEY];static {for (int i = 0; i < MAX_KEY; ++i) {KEYS_CACHE[i] = new Key(i);}}public static Key of(int value) {return KEYS_CACHE[value];} |
現(xiàn)在我們可以開始進行測試了。我們的基準測試使用連續(xù)的Key值來創(chuàng)建了不同的大小的HashMap（10的乘方，從1到1百萬）。在測試中我們還會使用key來進行查找，并測量不同大小的HashMap所花費的時間：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import com.google.caliper.Param;import com.google.caliper.Runner;import com.google.caliper.SimpleBenchmark;public class MapBenchmark extends SimpleBenchmark {private HashMap<Key, Integer> map;@Paramprivate int mapSize;@Overrideprotected void setUp() throws Exception {map = new HashMap<>(mapSize);for (int i = 0; i < mapSize; ++i) {map.put(Keys.of(i), i);}}public void timeMapGet(int reps) {for (int i = 0; i < reps; i++) {map.get(Keys.of(i % mapSize));}}} |
有意思的是這個簡單的HashMap.get()里面，Java 8比Java 7要快20%。整體的性能也相當不錯：盡管HashMap里有一百萬條記錄，單個查詢也只花了不到10納秒，也就是大概我機器上的大概20個CPU周期。 相當令人震撼！不過這并不是我們想要測量的目標。
假設(shè)有一個很差勁的key，他總是返回同一個值。這是最糟糕的場景了，這種情況完全就不應(yīng)該使用HashMap:
|
1
2
3
4
5
6
7
|
class Key implements Comparable<Key> {//...@Overridepublic int hashCode() {return 0;}} |
Java 7的結(jié)果是預(yù)料中的。隨著HashMap的大小的增長，get()方法的開銷也越來越大。由于所有的記錄都在同一個桶里的超長鏈表內(nèi)，平均查詢一條記錄就需要遍歷一半的列表。因此從圖上可以看到，它的時間復(fù)雜度是O(n)。
不過Java 8的表現(xiàn)要好許多！它是一個log的曲線，因此它的性能要好上好幾個數(shù)量級。盡管有嚴重的哈希碰撞，已是最壞的情況了，但這個同樣的基準測試在JDK8中的時間復(fù)雜度是O(logn)。單獨來看JDK 8的曲線的話會更清楚，這是一個對數(shù)線性分布：
為什么會有這么大的性能提升，盡管這里用的是大O符號（大O描述的是漸近上界）？其實這個優(yōu)化在JEP-180中已經(jīng)提到了。如果某個桶中的記錄過 大的話（當前是TREEIFY_THRESHOLD = 8），HashMap會動態(tài)的使用一個專門的treemap實現(xiàn)來替換掉它。這樣做的結(jié)果會更好，是O(logn)，而不是糟糕的O(n)。它是如何工作 的？前面產(chǎn)生沖突的那些KEY對應(yīng)的記錄只是簡單的追加到一個鏈表后面，這些記錄只能通過遍歷來進行查找。但是超過這個閾值后HashMap開始將列表升 級成一個二叉樹，使用哈希值作為樹的分支變量，如果兩個哈希值不等，但指向同一個桶的話，較大的那個會插入到右子樹里。如果哈希值相等，HashMap希 望key值最好是實現(xiàn)了Comparable接口的，這樣它可以按照順序來進行插入。這對HashMap的key來說并不是必須的，不過如果實現(xiàn)了當然最 好。如果沒有實現(xiàn)這個接口，在出現(xiàn)嚴重的哈希碰撞的時候，你就并別指望能獲得性能提升了。
這個性能提升有什么用處？比方說惡意的程序，如果它知道我們用的是哈希算法，它可能會發(fā)送大量的請求，導(dǎo)致產(chǎn)生嚴重的哈希碰撞。然后不停的訪問這些 key就能顯著的影響服務(wù)器的性能，這樣就形成了一次拒絕服務(wù)攻擊（DoS）。JDK 8中從O(n)到O(logn)的飛躍，可以有效地防止類似的攻擊，同時也讓HashMap性能的可預(yù)測性稍微增強了一些。我希望這個提升能最終說服你的 老大同意升級到JDK 8來。
測試使用的環(huán)境是：Intel Core i7-3635QM @ 2.4 GHz，8GB內(nèi)存，SSD硬盤，使用默認的JVM參數(shù)，運行在64位的Windows 8.1系統(tǒng) 上。
總結(jié)
HashMap的基本實現(xiàn)就如上面所分析的，最后做下總結(jié)：
- HashMap內(nèi)部用Entry對象保存鍵值對，基于哈希表存儲，用拉鏈法解決沖突。
- HashMap的默認容量大小為16，默認裝載因子為0.75。可以指定容量大小，容量最終一定會被設(shè)置為2的冪，這是為了均勻地散列。
- HashMap的key和value都可以是null，當然只能有一個key是null，value可以有多個。
- HashMap的鍵值對數(shù)量超過容量*裝載因子時會擴容，擴容后的容量大約是原來的兩倍。擴容會重新散列，所以元素的位置可能發(fā)生會變化，而且這是一個耗時操作。
- HashMap是線程不安全的。
