詳解HashMap內部實現原理
內部數據結構
|
1
2
3
4
5
|
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; |
從上面的數據結構定義可以看出，HashMap存元素的是一組鍵值對的鏈表，以什么形式存儲呢
|
1
|
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; |
可以看出，是以數組形式儲存，好的，現在我們知道，HashMap是以數組形式存儲，每個數組里面是一個鍵值對，這個鍵值對還可以鏈接到下個鍵值對。如下圖所示:
hashmap的添加
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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; } |
這里可以看出，hashmap的添加，首先根據一個entry的hash屬性去查找相應的table元素i，然后看這個位置是否有元素存在，如果沒有，直接放入，如果有，遍歷此次鏈表，加到表尾
刪除
|
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
|
final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; 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; } |
刪除的話，還是先根據hash在table數組中查找，然后再根據equals在鏈表中進行查找，這個也是為什么hashmap和hashset等以hash方式進行存儲的數據結構要求實現兩個方法hashcode和equalsd的原因
學過hash的人都知道，hash表的性能和hash沖突的發生次數有很大關系，但有不能申請過長的table表浪費空間，所以這里有了我們的resize函數
擴容機制
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } |
這個方法會在put的時候調用,上面put的時候先調用 addEntry(hash, key, value, i);方法，然后看addEntry方法
|
1
2
3
4
5
6
7
8
9
|
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); } |
上面可以看出那么 HashMap 當 HashMap 中的元素個數超過數組大小 *loadFactor 時，就會進行數組擴容，loadFactor 的默認值為 0.75，這是一個折中的取值。也就是說，默認情況下，數組大小為 16，那么當 HashMap 中元素個數超過 16*0.75=12 的時候，就把數組的大小擴展為 2*16=32，即擴大一倍，然后重新計算每個元素在數組中的位 置，而這是一個非常消耗性能的操作，所以如果我們已經預知 HashMap 中元素的個數，那么預設元素的個數能夠有效的提高 HashMap 的性能。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/u012926924/article/details/50451991
