HashMap中的幾個重要變量
默認初始容量,必須是2的n次方
|
1
|
static final int DEFAULT_INITIAL_CAPACITY = 16; |
最大容量，當通過構造方法傳入的容量比它還大時，就用這個最大容量，必須是2的n次方
|
1
|
static final int MAXIMUM_CAPACITY = 1 << 30; |
默認負載因子
|
1
|
static final float DEFAULT_LOAD_FACTOR = 0.75f; |
用來存儲鍵值對，可以看到鍵值對都是存儲在Entry中的
|
1
2
3
4
|
transient Entry<K,V>[] table;//capacity * load factor,超過這個數就會進行再哈希int threshold; |
HashMap中的元素是用名為table的Entry數組來保存的，默認大小是16
- capacity:數組的容量
- load_factor:負載因子
- threshold：實際能承載的容量，等于上面兩個相乘，當size大于threshold時，就會進行rehash
jdk7中在面對key為String的時候采用了區別對待，會有alternative hashing，但是這個在jdk8中已經被刪除了
存儲結構
Entry是一個鏈表結構，不僅包含key和value，還有可以指向下一個的next
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } ... |
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; } |
首先通過hash方法對hashcode進行處理：
|
1
2
3
4
5
6
7
|
final int hash(Object k) { int h = 0; h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } |
可以看到只是在key的hashcode值上做了一些處理，通過hash計算出來的值將會使用indexFor方法找到它應該所在的table下標：
|
1
2
3
|
static int indexFor(int h, int length) { return h & (length-1); } |
這個方法其實相當于對table.length取模。
當需要插入的key為null時，調用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;} |
putForNullKey方法只從table[0]這個位置開始遍歷，因為key為null只放在table中的第一個位置，下標為0，在遍歷中如果發現已經有key為null了，則替換新value，返回舊value，結束；如果還沒有key為null，調用addEntry方法增加一個Entry:
|
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); } |
可以看到jdk7中resize的條件已經發生改變了，只有當 size>=threshold并且 table中的那個槽中已經有Entry時，才會發生resize。即有可能雖然size>=threshold，但是必須等到每個槽都至少有一個Entry時，才會擴容。還有注意每次resize都會擴大一倍容量
|
1
2
3
4
5
|
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++; } |
最后看createEntry，它先保存這個桶中的第一個Entry，創建新的Entry放入第一個位置，將原來的Entry接在后面。這里采用的是頭插法插入元素。
get方法
其實get方法和put方法如出一轍，怎么放的怎么拿
|
1
2
3
4
5
6
7
|
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } |
key為null時，還是去table[0]去取：
|
1
2
3
4
5
6
7
|
private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } |
否則調用getEntry方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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; } |
這個方法也是通過key的hashcode計算出它應該所在的下標，再遍歷這個下標的Entry鏈，如果key的內存地址相等（即同一個引用）或者equals相等，則說明找到了
hash的原則
A、等冪性。不管執行多少次獲取Hash值的操作，只要對象不變，那么Hash值是固定的。如果第一次取跟第N次取不一樣，那就用起來很麻煩.
B、對等性。若兩個對象equal方法返回為true，則其hash值也應該是一樣的。舉例說明：若你將objA作為key存入HashMap中，然后new了一個objB。在你看來objB和objA是一個東西（因為他們equal），但是使用objB到hashMap中卻取不出來東西。
C、互異性。若兩個對象equal方法返回為false，hash值有可能相同，但最好是不同的，這個不是必須的，只是這樣做會提高hash類操作的性能（碰撞幾率低）。
解決hash碰撞的方法：
- 開放地址法
- 鏈地址法
hashmap采用的就是鏈地址法，這種方法好處是無堆積現象，但是next指針會占用額外空間
和jdk8中的HashMap區別
在jdk8中，仍然會根據key.hashCode()計算出hash值，再通過這個hash值去定位這個key，但是不同的是，當發生沖突時，會采用鏈表和紅黑樹兩種方法去處理，當結點個數較少時用鏈表（用Node存儲），個數較多時用紅黑樹（用TreeNode存儲），同時結點也不叫Entry了，而是分成了Node和TreeNode。再最壞的情況下，鏈表查找的時間復雜度為O(n),而紅黑樹一直是O(logn),這樣會提高HashMap的效率。jdk8中的HashMap中定義了一個變量TREEIFY_THRESHOLD，當節點個數>= TREEIFY_THRESHOLD - 1時，HashMap將采用紅黑樹存儲
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。
