HashMap是基于哈希表的Map接口實現(xiàn)，提供了所有可選的映射操作，并允許使用null值和null建，不同步且不保證映射順序。下面記錄一下研究HashMap實現(xiàn)原理。
HashMap內(nèi)部存儲
在HashMap內(nèi)部，通過維護一個 瞬時變量數(shù)組table (又稱：桶) 來存儲所有的鍵值對關(guān)系，桶 是個Entry對象數(shù)組，桶 的大小可以按需調(diào)整大小，長度必須是2的次冪。如下代碼：
|
1
2
3
4
5
6
7
8
|
/** * 一個空的entry數(shù)組，桶 的默認值 */ static final Entry<?,?>[] EMPTY_TABLE = {}; /** * 桶，按需調(diào)整大小，但必須是2的次冪 */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; |
初始容量與負載因子
HashMap有兩個參數(shù)影響性能，初始容量和負載因子。容量是哈希表中 桶 的數(shù)量，初始容量只是哈希表在創(chuàng)建時的容量，負載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中條目數(shù)超出了負載因子與當前容量的乘積時，則要對該Hash表進行rehash操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），重建時以當前容量的兩倍數(shù)目新建。可以通過構(gòu)造器設(shè)置初始容量與負載因子，默認初始容量是16個條目，最大容量是2^30次方個條目，默認負載因子是0.75
桶 就像一個存水的水桶，它默認的初始存水容量是16個單位的水，默認在灌水灌到16*0.75時，在下次添加數(shù)據(jù)時會先擴充容量，擴充到32單位。0.75就是負載因子，初始容量與負載因子可以通過創(chuàng)建水桶的時候進行設(shè)置。水桶最大的容量是2的30次方個單位的水。當初始容量設(shè)置的數(shù)量大于最大容量時，以最大容量為準。當擴展時如果大于等于最大容量時則直接返回。
如下為HashMap的部分源碼，定義了默認初始容量、負載因子及其他一些常量：
|
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
|
/** * 默認初始化容量，必須為2的次冪The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量，如果通過構(gòu)造函數(shù)參數(shù)中傳遞初始化容量大于該最大容量了，也會使用該容量為初始化容量 * 必須是2的次冪且小于等于2的30次方 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默認的負載因子，可以通過構(gòu)造函數(shù)指定 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 一個空的數(shù)組表，當 桶沒有初始化的時候 */ static final Entry<?,?>[] EMPTY_TABLE = {}; /** * 桶 , 存儲所有的鍵值對條目，可以按需調(diào)整大小，長度大小必須為2的次冪 */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; /** * Map中鍵值對的數(shù)量，在每次新增或刪除的時候都會對size進行+1或者-1操作. */ transient int size; /** * 負載值，需要調(diào)整大小的臨界值，為：(capacity * load factor).在每次調(diào)整大小后會使用新的容量計算一下 * @serial */ // If table == EMPTY_TABLE then this is the initial capacity at which the // table will be created when inflated. int threshold; /** * 負載因子，如果構(gòu)造函數(shù)中沒有指定，則采用默認的負載因子， * * @serial */ final float loadFactor; /** * HashMap結(jié)構(gòu)修改次數(shù)，結(jié)構(gòu)修改時改變HashMap中的映射數(shù)量或修改其內(nèi)部結(jié)構(gòu)（例如，* rehash方法，重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），此字段用于在 * HashMap的集合視圖上生成的迭代器都處理成快速失敗的 */ transient int modCount; |
初始容量與負載因子性能調(diào)整
通常，默認負載因子（0.75）在時間和空間成本上尋求一種折中。負載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數(shù)HashMap類的操作中，包括get和put操作，都反映了這一點）。在設(shè)置初始容量時應(yīng)該考慮到映射中所需的條目數(shù)及其負載因子，以便最大限度的減少rehash操作次數(shù)。如果初始容量大于最大條目數(shù)除以加載因子，則不會發(fā)生rehash操作。
如果很多映射關(guān)系要存儲在HashMap實例中，則相對于按需執(zhí)行自動的rehash操作以增大表的容量來說，使用足夠大的初始容量創(chuàng)建它將使得映射關(guān)系能更有效的存儲。
如下為重建HashMap數(shù)據(jù)結(jié)構(gòu)的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { // 如果容量已達最大限制，則設(shè)置下負載值后直接返回 threshold = Integer.MAX_VALUE; return; } // 創(chuàng)建新的table存儲數(shù)據(jù) Entry[] newTable = new Entry[newCapacity]; // 將舊table中的數(shù)據(jù)轉(zhuǎn)存到新table中去，這一步會花費比較多的時間 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; // 最后設(shè)置下下次調(diào)整大小的負載值 threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);} |
HashMap構(gòu)造方法
第四個構(gòu)造方法是以已經(jīng)存在的Map創(chuàng)建一個新的HashMap，稍后再說，前三個構(gòu)造方法，其實最終調(diào)用的都是第三個帶兩個參數(shù)的方法，如果沒有傳遞參數(shù)則使用默認的數(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
36
37
38
39
|
/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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(); } |
由上可以看出，在構(gòu)造函數(shù)中，如果初始容量給的大于最大容量，則直接以最大容量代替。
put方法
接下來就看看HashMap中比較重要的部分
|
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
|
/** * 在此映射中關(guān)聯(lián)指定值與指定建。如果該映射以前包含了一個該鍵的映射關(guān)系，則舊值被替換 * * @param 指定將要關(guān)聯(lián)的鍵 * @param 指定將要關(guān)聯(lián)的值 * @return 與key關(guān)聯(lián)的舊值，如果key沒有任何映射關(guān)系，則返回null（返回null還可能表示該映射之前將null與key關(guān)聯(lián)） */ public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } 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; } |
1. 首先put方法中，先判斷 桶 是否為默認的未初始化狀態(tài)，如果未初始化則調(diào)用 inflateTable 方法去初始化，然后判斷參數(shù)key是否為null，如果為null，則調(diào)用putForNullKey專門進行放key為null的數(shù)據(jù)，putForNullKey方法與下面的第3步開始其實都是一樣的，只不過key為null的數(shù)據(jù)默認存儲位置就是第一個，即下標默認為0。
2. 如果key不是null,則調(diào)用hash()方法獲取key的hash值，可以根據(jù)hash值、桶的長度通過indexFor方法計算該key可以放到桶的位置。
3. Entry對象中有一個屬性next，可以形成一個單向鏈表，用來存儲哈希值相同的元素。因此當計算出來key的hash值重復(fù)時，存儲位置也會重復(fù)，只要判斷一下存儲位置的元素及該元素的next屬性鏈表中是否與給定的key和key的hash值是否完全一致就可以了。如果有完全一致的，代表已經(jīng)存在，則替換舊值，并把舊值做為返回值直接返回。
4. 把結(jié)構(gòu)修改次數(shù)自增1
5. 調(diào)用addEntry方法將新的鍵值對增加到HashMap中。addEntity方法首先判斷當前條目數(shù)據(jù)是否已經(jīng)大于等于負載值（桶的容量*負載因子）且桶的指定位置不為null，如果已經(jīng)大于且指定位置不為null，則調(diào)調(diào)整桶的容量為當前容量的2倍，調(diào)整桶的容量參照上面的初始容量與負載因子性能調(diào)整 目錄。重新計算Hash值，計算存放位置。調(diào)用createEntry方法存放到 桶 中
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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++; } /** * Entry構(gòu)造方法，創(chuàng)建一個新的Entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } |
6. 在 createEntry 方法中，首先獲取指定位置的entry，然后新生成一個entry，在生成entry時把原有的entry存儲到新生成的entry的next屬性中（參考Entry的構(gòu)造方法），并把指定位置的entry替換成新生成的。
因為新增條目的時候，需要計算hash值，長度不夠時需要調(diào)整長度，當計算的存儲位置已有元素的時候需要進行鏈表式的存儲，所以使用HashMap新增操作的效率并不是太高。
get方法
首先看下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
|
/** * 返回指定鍵所映射的值；如果對于該鍵來說，此映射不包含任何映射關(guān)系，則返回null * 返回null值并不一定表明該映射不包含該鍵的映射，也可能改映射將該鍵顯示的映射為null，可使用containsKey操作來區(qū)分這兩種情況 * @see #put(Object, Object) */ public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } 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;} |
get方法實現(xiàn)較簡單，以下是幾個步驟：
- 首先判斷key是否為null，如果為null，則調(diào)用 getForNullKey 方法來獲取，如果不為null則調(diào)用 getEntry 方法來獲取。getForNullKey方法與getEntity基本上一致，只不過少了一個步驟，就是默認的key為null的存儲位置在第一個，即下標為0，沒有去計算位置而已。
- getEntity方法根據(jù)key計算哈希值，然后用哈希值、桶的長度計算存儲位置。
- getEntity以獲取指定位置的entry作為遍歷的開始，遍歷entry的next單鏈表，如果entry的哈希值與計算的哈希值一致且entry的key與指定的相等則返回entry
- 根據(jù)getEntity返回的值，get方法返回對應(yīng)的值。
通過查看get的源碼可以發(fā)現(xiàn)，get方法通過key的哈希值與桶的長度計算存儲位置，基本上一下就能定位到要找的元素，即使再遍歷幾個重復(fù)哈希值的key，也是很快速的，因為哈希值相對唯一，所以HashMap對于查找性能是非常快的。
自定義對象作為HashMap的鍵
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class User { // 身份證號碼 protected int idNumber; public User(int id){ idNumber = id; }}public class TestUser{ public static void main(String[] args) { Map<User, String> map = new HashMap<User, String>(); for (int i=0; i<5; i++) { map.put(new User(i), "姓名: " + i); } System.out.println("User3 的姓名：" + map.get(new User(3))); }}輸出：User3 的姓名：null |
如上代碼，通過自定義的User類實例作為HashMap的對象時，在打印的時候是無法找到User3的姓名的，因為User類自動繼承基類Object，所以這里會自動使用Object的hashCode方法生成哈希值，而它默認是使用對象的地址計算哈希值的。因此new User(3)生成的第一個實例的哈希值與生成的第二個實例的哈希值是不一樣的。但是如果只需要簡單的覆蓋hashCode方法，也是無法正常運作的，除非同時覆蓋equals方法，它也是Object的一部分。HashMap使用equals()判斷當前的鍵是否與表中存在的鍵相同，可以參考上面的get或put方法。
正確equals()方法必須滿足下列5個條件：---參考《Java編程思想》—489頁
- 自反性。對任意x，x.equals(x)一定返回true
- 對稱性。對任意x和y，如果有y.equals(x)返回true，則x.equals(y)也返回true
- 傳遞性。對任意x,y,z，如果有x.equals(y)返回true，y.equals(z)返回true，則x.equals(z)一定返回true
- 一致性，對任意x和y，如果對象中用于等價比較的信息沒有改變，那么無論調(diào)用x.equals(y)多少次，返回的結(jié)果應(yīng)該保持一致，要么一致是true，要么一致是false.
- 對任何不是null的x，x.equals(null)一定返回false
再次強調(diào)：默認的Object.equals()只是比較對象的地址，所以一個new User(3)并不等于另一個new User(3)。因此，如果要使用自己的類作為HashMap的鍵，必須同時重載hashCode()和equals().
如下代碼可以正常運作：
|
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
|
class User { // 身份證號碼 protected int idNumber; public User(int id){ idNumber = id; } @Override public int hashCode() { return idNumber; } @Override public boolean equals(Object obj) { return obj instanceof User && (idNumber==((User)obj).idNumber); }}public class TestUser{ public static void main(String[] args) { Map<User, String> map = new HashMap<User, String>(); for (int i=0; i<5; i++) { map.put(new User(i), "姓名: " + i); } System.out.println("User3 的姓名：" + map.get(new User(3))); }}輸出：User3 的姓名：姓名: 3 |
上面只是簡單的在hashCode中返回了idNumber作為唯一的判別，用戶也可以根據(jù)自己的業(yè)務(wù)實現(xiàn)自己的方法。在equals方法中，instanceof會悄悄的檢查對象是否為null，如果instanceof左邊的參數(shù)為null，則會返回false，如果equals()的參數(shù)不為null且類型正確，則基于每個對象中的實際的idNumber進行比較。從輸出可以看出，現(xiàn)在的方式是正確的。
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務(wù)器之家！
