一、HashMap的概述
HashMap可以說是Java中最常用的集合類框架之一,是Java語言中非常典型的數(shù)據(jù)結(jié)構(gòu)。
HashMap是基于哈希表的Map接口實(shí)現(xiàn)的,此實(shí)現(xiàn)提供所有可選的映射操作。存儲的是對的映射，允許多個null值和一個null鍵。但此類不保證映射的順序，特別是它不保證該順序恒久不變。
除了HashMap是非同步以及允許使用null外，HashMap 類與 Hashtable大致相同。
此實(shí)現(xiàn)假定哈希函數(shù)將元素適當(dāng)?shù)胤植荚诟魍爸g，可為基本操作（get 和 put）提供穩(wěn)定的性能。迭代collection 視圖所需的時間與 HashMap 實(shí)例的“容量”（桶的數(shù)量）及其大小（鍵-值映射關(guān)系數(shù)）成比例。所以，如果迭代性能很重要，則不要將初始容量設(shè)置得太高（或?qū)⒓虞d因子設(shè)置得太低）。
HashMap 的實(shí)例有兩個參數(shù)影響其性能：初始容量 和加載因子。容量 是哈希表中桶的數(shù)量，初始容量只是哈希表在創(chuàng)建時的容量。加載因子 是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時，則要對該哈希表進(jìn)行 rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有大約兩倍的桶數(shù)。
通常，默認(rèn)加載因子 (0.75) 在時間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數(shù) HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點(diǎn)）。在設(shè)置初始容量時應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地減少 rehash 操作次數(shù)。如果初始容量大于最大條目數(shù)除以加載因子，則不會發(fā)生 rehash 操作。
注意，此實(shí)現(xiàn)不是同步的。 如果多個線程同時訪問一個HashMap實(shí)例，而其中至少一個線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步。這通常是通過同步那些用來封裝列表的 對象來實(shí)現(xiàn)的。但如果沒有這樣的對象存在，則應(yīng)該使用{@link Collections#synchronizedMap Collections.synchronizedMap}來進(jìn)行“包裝”，該方法最好是在創(chuàng)建時完成，為了避免對映射進(jìn)行意外的非同步操作。
|
1
|
Map m = Collections.synchronizedMap(new HashMap(...)); |
二、構(gòu)造函數(shù)
HashMap提供了三個構(gòu)造函數(shù)：
HashMap()：構(gòu)造一個具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構(gòu)造一個帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個帶指定初始容量和加載因子的空 HashMap。
這里提到了兩個參數(shù)：初始容量，加載因子。這兩個參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為0.75，一般情況下我們是無需修改的。
HashMap是一種支持快速存取的數(shù)據(jù)結(jié)構(gòu)，要了解它的性能必須要了解它的數(shù)據(jù)結(jié)構(gòu)。
三、數(shù)據(jù)結(jié)構(gòu)
我們知道在Java中最常用的兩種結(jié)構(gòu)是數(shù)組和模擬指針(引用)，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來組合實(shí)現(xiàn)，HashMap也是如此。實(shí)際上HashMap是一個“鏈表散列”，如下是它數(shù)據(jù)結(jié)構(gòu)：
|
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
56
57
58
59
60
61
62
63
|
// Entry是單向鏈表。 它是 “HashMap鏈?zhǔn)酱鎯Ψ?rdquo;對應(yīng)的鏈表。 // 實(shí)現(xiàn)了Map.Entry接口，即getKey(),getValue(),setValue(V value),equals(Object o),hashCode()這些函數(shù) static class Entry implements Map.Entry { final K key; V value; // 指向下一個節(jié)點(diǎn) Entry next; final int hash; // 構(gòu)造函數(shù) // 輸入?yún)?shù)包括"哈希值(h)", "鍵(k)", "值(v)", "下一節(jié)點(diǎn)(n)" Entry(int h, K k, V v, Entry 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; } // 判斷兩個Entry是否相等 // 若兩個Entry的“key”和“value”都相等，則返回true。 // 否則，返回false 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; } // 實(shí)現(xiàn)hashCode() public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } // 當(dāng)向HashMap中添加元素時，繪調(diào)用recordAccess()。 // 這里不做任何處理 void recordAccess(HashMap m) { } // 當(dāng)從HashMap中刪除元素時，繪調(diào)用recordRemoval()。 // 這里不做任何處理 void recordRemoval(HashMap m) { } } |
從上圖我們可以看出HashMap底層實(shí)現(xiàn)還是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈。其中參數(shù)initialCapacity就代表了該數(shù)組的長度。下面為HashMap構(gòu)造函數(shù)的源碼：
|
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
|
// 找出“大于Capacity”的最小的2的冪,使Hash表的容量保持為2的次方倍 // 算法的思想：通過使用邏輯運(yùn)算來替代取余，這里有一個規(guī)律，就是當(dāng)N為2的次方（Power of two），那么X％N==X&(N-1)。 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; // >>> 無符號右移,高位補(bǔ)0 n |= n >>> 2; // a|=b的意思就是把a(bǔ)和b按位或然后賦值給a n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } // 構(gòu)造一個帶指定初始容量和加載因子的空HashMap 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; this.threshold = tableSizeFor(initialCapacity); } // 構(gòu)造一個帶指定初始容量和默認(rèn)加載因子(0.75)的空 HashMap public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 構(gòu)造一個具有默認(rèn)初始容量 (16)和默認(rèn)加載因子 (0.75)的空 HashMap public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 構(gòu)造一個映射關(guān)系與指定 Map相同的新 HashMap,容量與指定Map容量相同，加載因子為默認(rèn)的0.75 public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } |
從源碼中可以看出，每次新建一個HashMap時，都會初始化一個table數(shù)組。table數(shù)組的元素為Entry節(jié)點(diǎn)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Entry是單向鏈表。 // 它是 “HashMap鏈?zhǔn)酱鎯Ψ?rdquo;對應(yīng)的鏈表。 // 它實(shí)現(xiàn)了Map.Entry 接口，即實(shí)現(xiàn)getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數(shù) static class Entry implements Map.Entry { final K key; V value; // 指向下一個節(jié)點(diǎn) Entry next; final int hash; // 構(gòu)造函數(shù)。 // 輸入?yún)?shù)包括"哈希值(h)", "鍵(k)", "值(v)", "下一節(jié)點(diǎn)(n)" Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } ...... } |
其中Entry為HashMap的內(nèi)部類，它包含了鍵key、值value、下一個節(jié)點(diǎn)next，以及hash值，這是非常重要的，正是由于Entry才構(gòu)成了table數(shù)組的項(xiàng)為鏈表。
以上這篇基于Java中最常用的集合類框架之HashMap(詳解)就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/shsxt/archive/2017/11/12/7822841.html
