Life is not a ridiculous number of life, the meaning of life lies in life itself
HashMap源碼
散列集
數組和鏈表可以保持元素插入的順序,對數組來說,他的優點是擁有連續的存儲空間,因此可以使用元素下標快速訪問,但缺點在于如果要在數組中第n位刪除或插入一個新元素,就需要移動n后面的所有元素,比如在ArrayList中刪除某個元素就是調用系統的arraycopy方法將數組要刪除的元素后面的所有元素向前復制一位得到的。
private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)// 將elementData中從index + 1開始的numMoved長度的元素復制到elementData的index位置System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work
}
并且定義數組時必須指定容量,如果需要擴容就得重新申請一個更大的數組,然后把原來的數據復制到新數組中,
這就導致數組查詢很快,但增刪性能不高。
而對鏈表來說,它的內存空間不是連續的,也就不需要考慮容量問題,但這就導致鏈表的查詢需要逐個遍歷LinkedList中雖然可以通過索引來get元素,但也是從頭部開始遍歷的(如果索引大于size/2就從尾部遍歷),效率很低。
散列集(hash table)可以說是數組與鏈表的組合,
往散列集中添加元素時,通過hash函數可以得到一個該元素的一個哈希值,Java中哈希值的范圍在-2147483648~2147483647
之間,Object類的hashCode()
方法可以返回對象的哈希值,通過hashCode可以確定將該元素存到哪一個數組中,
不能直接使用hashCode,因為它的范圍將近40億,不可能有這么大的數組空間,所以需要對hashCode值做一定的處理,使之在數組容量范圍內,最簡單的辦法是對數組容量取余,但取余有效率問題,所以Java使用了&操作,
如果key是null, 就返回0,否則返回原來哈希值與哈希值右移16位后的結果
比如一個元素的hashCode經過運算得到的值是5,他就會被放在第六個數組中。
應為數組容量是有限的,就一定存在運算后得到同樣索引值的情況,稱為哈希碰撞,解決哈希碰撞有兩種方法:開放地址法和拉鏈法 ,開放地址法是指如果當前的數組已經有元素了,就通過別的算法算出一個新位置插入,像python中dict的實現就使用了開放地址法;而Java中則使用了后者——拉鏈法,他的思路是如果當前位置有元素了,就把新元素鏈到舊元素上。
jdk 1.7 以及之前拉鏈使用一個鏈表實現,每次有沖突的新元素過來就會把新元素放到數組中,原來的舊鏈鏈接到新元素后面【頭插法】;
jdk 1.8 開始加入了紅黑樹,如果數組某個位置的長度超過8并且數組容量超過32就會把鏈表轉換為紅黑樹,如果紅黑樹經過刪除節點數小于6,就會把樹重新轉換回鏈表,以此來提高效率。
JDK 1.7 中的實現
jdk 1.7 以及之前那個數組是Entry類型的,里面封裝了key和value,也就是鏈表的一個節點。
static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;
}
基本屬性
// 數組的默認大小,必須是2的倍數, 默認16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 數組最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;// 默認負載因子,如果數組中75%被占滿,就要擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;// hashMap中數據的數量
transient int size;// 與快速失敗有關
transient int modCount;
put方法
public V put(K key, V value) {if (table == EMPTY_TABLE) {// 初始化一個數組inflateTable(threshold);}// key為null的情況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;
}
如果當前table是空的的時候(實例化后第一次執行put),需要通過inflateTable()
對哈希表進行初始化
private void inflateTable(int toSize) {// Find a power of 2 >= toSize// 計算實際的數組大小int capacity = roundUpToPowerOf2(toSize);// 計算出擴容的臨界值thresholdthreshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);// 實例化一個新數組table = new Entry[capacity];initHashSeedAsNeeded(capacity);
}
由于數組容量要求是2的倍數,所以這個方法會先通過roundUpToPowerOf2()
根據我們指定的數組容量計算出真實的數組容量capacity,然后實例化一個capacity大小的Entry數組。最后這個initHashSeedAsNeeded()
允許你配置一個哈希種子,來手動影響散列結果。
初始化后,由于HashMap允許null作為key值,所以如果key是null,就執行putForNullKey()
方法把null: value
存入哈希表.
private V putForNullKey(V value) {// 遍歷數組0位的鏈表for (Entry<K,V> e = table[0]; e != null; e = e.next) {// 如果數組0位鏈表某個節點key也是null,就替換該節點的值,返回舊值。if (e.key == null) {V oldValue = e.value;e.value = value;// 空方法e.recordAccess(this);return oldValue;}}// 如果0位沒有key為null的節點,就創建新節點并加入鏈表modCount++;addEntry(0, null, value, 0);return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {// 如果HashMap中元素的數量大于臨界值并且發生了沖突,就擴容if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}// 創建新的Entry對象createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {// 原來的鏈表Entry<K,V> e = table[bucketIndex];// 實例化一個新的Entry對象,next指向舊的鏈表etable[bucketIndex] = new Entry<>(hash, key, value, e);// 元素個數加一size++;
}
- HashMap允許null作為key,并且這個元素始終放在數組第0位
回到正常情況,key是null就確定它存放在數組0位,但其他的key就需要通過計算得到index值,jdk1.7中首先在hash()
方法中對對象原本的hashCode做一系列移位操作后,再在indexFor()
方法中與數組長度做與運算得出對象最終應該被放在數組的哪一位。
final int hash(Object k) {// 可以設置環境變量來提供一個哈希種子int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}// 這個種子會通過與對象原來的hashCode做異或從而影響最終散列效果h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {return h & (length-1);
}
出于性能的考慮,在獲得最終的index時,Java采用了&
操作而不是更簡單的取余,這就導致數組長度必須是2的倍數,同時hash()
方法中多次移位和異或也是應為這樣。
比如一個字符串 “重地” 通過
hashCode()
方法得到它原先的hashCode值為 1179395,假設數組沒擴容,哈希種子是默認值0,那它計算index的過程應該是:
與hashSeed做異或,得到的還是它本身
右移20位的結果與右移12位的結果做異或
h = : 0000 0000 0001 0001 1111 1111 0000 0011 (1179395) a = h >>> 20: 0000 0000 0000 0000 0000 0000 0000 0001 (1) b = h >>> 12: 0000 0000 0000 0000 0000 0001 0001 1111? (287) ---------------------------------------------------------------- a ^ b = : 0000 0000 0000 0000 0000 0001 0001 1110 (286) h = : 0000 0000 0001 0001 1111 1111 0000 0011 (1179395) ---------------------------------------------------------------- h = : 0000 0000 0001 0001 1111 1110 0001 1101 (1179165) c = h >>> 7 : 0000 0000 0000 0000 0010 0011 1111 1100 ---------------------------------------------------------------- h ^ c = : 0000 0000 0001 0001 1101 1101 1110 0001 d = h >>> 4 : 0000 0000 0000 0001 0001 1101 1101 1110 ---------------------------------------------------------------- h ^ d = : 0000 0000 0001 0000 1100 0000 0011 1111 len - 1 : 0000 0000 0000 0000 0000 0000 0000 1111 ---------------------------------------------------------------- index & : 0000 0000 0000 0000 0000 0000 0000 1111
到最后發現,真正參與運算的只有低四位,之所以做多次位移和異或運算,就是為了把hashCode的高位也參與到最后的與運算中,讓得到的index盡量分散,如果把最高位用A表示,可以看到經過上面的算法,最高位究竟影響了哪些位置:
h = : A000 0000 0001 0001 1111 1111 0000 0011 (1179395) a = h >>> 20: 0000 0000 0000 0000 000A 0000 0000 0001 (1) b = h >>> 12: 0000 0000 0000 A000 0000 0001 0001 1111? (287) ---------------------------------------------------------------- a ^ b = : 0000 0000 0000 A000 000A 0001 0001 1110 (286) h = : 0000 0000 0001 0001 1111 1111 0000 0011 (1179395) ---------------------------------------------------------------- h = : 0000 0000 0001 A001 111A 1110 0001 1101 (1179165) c = h >>> 7 : 0000 0000 0000 0000 001A 0011 11A1 1100 ---------------------------------------------------------------- h ^ c = : 0000 0000 0001 A001 110A 1101 11A0 0001 d = h >>> 4 : 0000 0000 0000 0001 A001 110A 1101 11A0 ---------------------------------------------------------------- h ^ d = : 0000 0000 0001 A000 110A 000A 00A1 11A1 len - 1 : 0000 0000 0000 0000 0000 0000 0000 1111 ---------------------------------------------------------------- index & : 0000 0000 0000 A000 000A 000A 00A0 11A1
最高位最后影響了低四位。
為什么數組容量要是2的倍數
讓與運算之后的結果分布在 0 ~ (len -1) 之間
算出index之后的代碼邏輯就和putForNullKey差不多了,唯一的區別在于:
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){...}
這樣設計的原因在于:
- 哈希值不同一定不是同一個對象
- 同一個對象哈希值不一定相同
擴容
是否擴容的判斷在addEntry方法中,如果滿足擴容條件,是先擴容,再添加新元素
void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {// 2倍擴容resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}
擴容需要滿足兩個條件:
- HashMap中元素個數大于等于threshold
- 即將要新插入的元素發生了沖突
第一個條件 size是總元素個數,但threshold是根據數組容量算的。
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
void resize(int newCapacity) {// 得到舊數組的引用Entry[] oldTable = table;int oldCapacity = oldTable.length;// 如果舊數組已經不能再長了,就不擴容了if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}// 創建一個2倍舊數組大小的新數組Entry[] newTable = new Entry[newCapacity];// 將舊數組的元素轉移到新數組transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;// 重新計算擴容臨界值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
擴容最核心的就是數據轉移,也就是transfer()
方法
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;// 第一重循環遍歷數組for (Entry<K,V> e : table) {// 第二重循環遍歷鏈表while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);// 到這又變成了尾插e.next = newTable[i];newTable[i] = e;e = next;}}
}
由于數組容量變了兩倍,所以index也許需要重新計算,但計算中其實前面的步驟都一樣,只不過最后一步時 length - 1 在最前面多了一個1,所以哪怕index值改變,變化后的index與原來的也是2的倍數關系(1.8中用到了這個規律)
擴容過程中出現的循環鏈表的情況
這是兩個線程進入transfer后一開始的情況(兩個線程現在都有了自己新的數組),如果線程1正常執行完成,線程2阻塞在Entry<K,V> next = e.next;
之后,那結果就是:
然后線程2開始執行
就出現了循環鏈表的情況。
參考
參考2