JDK7中的HashMap
HashMap可以看成是一個(gè)數(shù)組奄薇，每個(gè)數(shù)組元素是一個(gè)單向鏈表贩据。
請(qǐng)輸入圖片描述
其中芥驳，每個(gè)鏈表的節(jié)點(diǎn)可以看成一個(gè)Entry實(shí)例，Entry由兩部分(或者4個(gè)屬性)組成：key, value, hash 值和用于單向鏈表的 next谭期。
一堵第、初始化
在第一個(gè)元素插入 HashMap 的時(shí)候做一次數(shù)組的初始化，就是先確定初始的數(shù)組大小隧出，并計(jì)算數(shù)組擴(kuò)容的閾值踏志。
private void inflateTable(int toSize) {
// 保證數(shù)組大小一定是 2 的 n 次方。
// 比如這樣初始化：new HashMap(20)胀瞪，那么處理成初始數(shù)組大小是 32
int capacity = roundUpToPowerOf2(toSize);
// 計(jì)算擴(kuò)容閾值：capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 算是初始化數(shù)組吧
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
小結(jié)：
- 數(shù)組的初始化大小一定為
2^n针余，這是因?yàn)楦斓亩ㄎ辉厮潜桑粋€(gè)有趣的算法一個(gè)數(shù)x對(duì)2^n取模，等價(jià)于x&(2^n-1)圆雁，例如：11%4 = 11&(4-1)忍级，與運(yùn)算相比取模運(yùn)算在計(jì)算機(jī)看來快得多。 - 不論我們指定容器的容量為多少伪朽，初始化的時(shí)候大小自動(dòng)設(shè)置為最相近的
2^n那么大轴咱，例如，手動(dòng)指定初始化容量為11烈涮，其實(shí)初始化的時(shí)候朴肺，大小為16，手動(dòng)指定為17坚洽，初始化大小則為32戈稿。 - 在new HashMap的時(shí)候不會(huì)初始化數(shù)組的大小，只有當(dāng)put第一個(gè)元素到容器中的時(shí)候才會(huì)初始化讶舰。
二鞍盗、get過程分析
分三步：
- 根據(jù) key 計(jì)算 hash 值。
- 找到相應(yīng)的數(shù)組下標(biāo)(key的hash值對(duì)數(shù)組的長度取模)：hash & (length - 1)跳昼。
- 遍歷該數(shù)組位置處的鏈表橡疼，直到找到相等(==或equals)的 key。
public V get(Object key) {
// key 為 null 的話庐舟，會(huì)被放到 table[0]，所以只要遍歷下 table[0] 處的鏈表就可以了
if (key == null) return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
getEntry(key):
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 確定數(shù)組下標(biāo)住拭，然后從頭開始遍歷鏈表挪略，直到找到為止
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;
}
小結(jié)：
- HashMap的key和value都可以為null，并將它放在數(shù)組的0號(hào)位置上滔岳。
- 當(dāng)key為null的時(shí)候杠娱，這個(gè)key對(duì)應(yīng)的hash值為0。
三谱煤、put過程分析
public V put(K key, V value) {
// 當(dāng)插入第一個(gè)元素的時(shí)候摊求，需要先初始化數(shù)組大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);// 見【一】
}
// 如果 key 為 null，最終會(huì)將這個(gè) entry 放到 table[0] 中
if (key == null) return putForNullKey(value);
// 1. 求 key 的 hash 值
int hash = hash(key);
// 2. 找到對(duì)應(yīng)的數(shù)組下標(biāo)刘离，見【四】
int i = indexFor(hash, table.length);
// 3. 遍歷一下對(duì)應(yīng)下標(biāo)處的鏈表室叉，看是否有重復(fù)的 key 已經(jīng)存在，
// 如果有硫惕，直接覆蓋茧痕，put 方法返回舊值就結(jié)束了
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++;
// 4. 不存在重復(fù)的 key，將此 entry 添加到鏈表中恼除，見【五】
addEntry(hash, key, value, i);
return null;
}
小結(jié)：
- 當(dāng)插入第一個(gè)元素的時(shí)候踪旷，才會(huì)初始化數(shù)組大小。
- 當(dāng)put一個(gè)不存在的key時(shí)，返回null令野，put一個(gè)存在的key則返回原來的舊值舀患。
- 1.7中沒有紅黑樹概念，假如數(shù)據(jù)量很大气破，發(fā)生Hash沖突的概率很大聊浅，會(huì)致使鏈表過長，查詢效率嚴(yán)重下降堵幽。
四狗超、計(jì)算數(shù)組位置
使用key的hash值對(duì)數(shù)組長度進(jìn)行取模
static int indexFor(int hash, int length) {
return hash & (length-1);
}
五、添加節(jié)點(diǎn)到鏈表中
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果當(dāng)前 HashMap 大小已經(jīng)達(dá)到了閾值朴下，并且新值要插入的數(shù)組位置已經(jīng)有元素了努咐，那么要擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 需要擴(kuò)容，先擴(kuò)容殴胧，見【六】渗稍，再插入
resize(2 * table.length);
// 擴(kuò)容以后，重新計(jì)算 hash 值
hash = (null != key) ? hash(key) : 0;
// 重新計(jì)算擴(kuò)容后的新的下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
// 在下面
createEntry(hash, key, value, bucketIndex);
}
// 其實(shí)就是將新值放到鏈表的表頭团滥，然后 size++
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++;
}
這個(gè)方法的主要邏輯就是先判斷是否需要擴(kuò)容竿屹，需要的話先擴(kuò)容，然后再將這個(gè)新的數(shù)據(jù)插入到擴(kuò)容后的數(shù)組的相應(yīng)位置處的鏈表的表頭灸姊。
小結(jié)：
- 出現(xiàn)Hash沖突的時(shí)候拱燃，采用鏈地址法，將新元素插入到舊鏈表的頭部力惯。
- 需要擴(kuò)容的話碗誉，先擴(kuò)容再插入，區(qū)別于1.8父晶。
六哮缺、數(shù)組的擴(kuò)容
在插入新值的時(shí)候，如果當(dāng)前的 size 已經(jīng)達(dá)到了閾值甲喝，并且要插入的數(shù)組位置上已經(jīng)有元素尝苇，那么就會(huì)觸發(fā)擴(kuò)容，擴(kuò)容后埠胖，數(shù)組大小為原來的 2 倍糠溜。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新的數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將原來數(shù)組中的值遷移到新的更大的數(shù)組中
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;
// 循環(huán)舊數(shù)組的每個(gè)元素
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);
}
// 重新計(jì)算該元素在新數(shù)組中的下標(biāo)
int i = indexFor(e.hash,newCapacity);
// 下面三行代碼就是交換位置，將舊元素e押袍，遷移到新數(shù)組的i號(hào)位置诵冒，即newCapacityp[i]
e.next = newCapacityp[i];
newCapacity[i] = e;
e = next;
}
}
}
擴(kuò)容就是用一個(gè)新的大數(shù)組替換原來的小數(shù)組，將所有的元素重新計(jì)算Hash值谊惭，并將原來數(shù)組中的值遷移到新的數(shù)組中汽馋。原來 table[i] 中的鏈表的所有節(jié)點(diǎn)侮东，分拆到新的數(shù)組的 newTable[i] 和 newTable[i + oldLength] 位置上。比如原來數(shù)組長度是 16豹芯，那么擴(kuò)容后悄雅，原來 table[0] 處的鏈表中的所有元素會(huì)被分配到新數(shù)組中 newTable[0] 和 newTable[16] 這兩個(gè)位置。
小結(jié)：
- 多線程并發(fā)中铁蹈，
transfer方法可能會(huì)致使新數(shù)組生成環(huán)狀鏈表宽闲，這樣再查詢這個(gè)鏈表上沒有的元素的時(shí)候，會(huì)形成死循環(huán)握牧，CPU飆升容诬。 - 遷移數(shù)據(jù)的時(shí)候需要將所有舊數(shù)組上的元素重新計(jì)算一次Hash，區(qū)別于1.8沿腰。
