|
一,、什么時(shí)候擴(kuò)容：
網(wǎng)上總結(jié)的會(huì)有很多，但大多都總結(jié)的不夠完整或者不夠準(zhǔn)確,。大多數(shù)可能值說(shuō)了滿足我下面條件一的情況,。
擴(kuò)容必須滿足兩個(gè)條件：
1、 存放新值的時(shí)候當(dāng)前已有元素的個(gè)數(shù)必須大于等于閾值
2,、 存放新值的時(shí)候當(dāng)前存放數(shù)據(jù)發(fā)生hash碰撞（當(dāng)前key計(jì)算的hash值換算出來(lái)的數(shù)組下標(biāo)位置已經(jīng)存在值）
二,、下面我們看源碼，如下：
首先是put()方法
public V put(K key, V value) {
//判斷當(dāng)前Hashmap(底層是Entry數(shù)組)是否存值（是否為空數(shù)組）
if (table == EMPTY_TABLE) {
inflateTable(threshold);//如果為空,，則初始化
}
//判斷key是否為空
if (key == null)
return putForNullKey(value);//hashmap允許key為空
//計(jì)算當(dāng)前key的哈希值
int hash = hash(key);
//通過(guò)哈希值和當(dāng)前數(shù)據(jù)長(zhǎng)度,，算出當(dāng)前key值對(duì)應(yīng)在數(shù)組中的存放位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果計(jì)算的哈希位置有值（及hash沖突），且key值一樣,，則覆蓋原值value,，并返回原值value
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;
}
|
在put()方法中有調(diào)用addEntry()方法，這個(gè)方法里面是具體的存值,，在存值之前還有判斷是否需要擴(kuò)容
void addEntry(int hash, K key, V value, int bucketIndex) {
//1,、判斷當(dāng)前個(gè)數(shù)是否大于等于閾值
//2、當(dāng)前存放是否發(fā)生哈希碰撞
//如果上面兩個(gè)條件否發(fā)生,，那么就擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
//擴(kuò)容,，并且把原來(lái)數(shù)組中的元素重新放到新數(shù)組中
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
|
如果需要擴(kuò)容，調(diào)用擴(kuò)容的方法resize()
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//判斷是否有超出擴(kuò)容的最大值,，如果達(dá)到最大值則不進(jìn)行擴(kuò)容操作
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// transfer()方法把原數(shù)組中的值放到新數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//設(shè)置hashmap擴(kuò)容后為新的數(shù)組引用
table = newTable;
//設(shè)置hashmap擴(kuò)容新的閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);
}
|
transfer()在實(shí)際擴(kuò)容時(shí)候把原來(lái)數(shù)組中的元素放入新的數(shù)組中
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);
}
//通過(guò)key值的hash值和新數(shù)組的大小算出在當(dāng)前數(shù)組中的存放位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
|
三,、總結(jié)：
Hashmap的擴(kuò)容需要滿足兩個(gè)條件：當(dāng)前數(shù)據(jù)存儲(chǔ)的數(shù)量（即size()）大小必須大于等于閾值；當(dāng)前加入的數(shù)據(jù)是否發(fā)生了hash沖突,。
因?yàn)樯厦孢@兩個(gè)條件,，所以存在下面這些情況
（1）、就是hashmap在存值的時(shí)候（默認(rèn)大小為16,，負(fù)載因子0.75,，閾值12），可能達(dá)到最后存滿16個(gè)值的時(shí)候,，再存入第17個(gè)值才會(huì)發(fā)生擴(kuò)容現(xiàn)象,，因?yàn)榍?6個(gè)值，每個(gè)值在底層數(shù)組中分別占據(jù)一個(gè)位置,，并沒(méi)有發(fā)生hash碰撞,。
（2）、當(dāng)然也有可能存儲(chǔ)更多值（超多16個(gè)值,，最多可以存26個(gè)值）都還沒(méi)有擴(kuò)容,。原理：前11個(gè)值全部hash碰撞，存到數(shù)組的同一個(gè)位置（這時(shí)元素個(gè)數(shù)小于閾值12,，不會(huì)擴(kuò)容）,，后面所有存入的15個(gè)值全部分散到數(shù)組剩下的15個(gè)位置（這時(shí)元素個(gè)數(shù)大于等于閾值，但是每次存入的元素并沒(méi)有發(fā)生hash碰撞,，所以不會(huì)擴(kuò)容）,，前面11 15=26，所以在存入第27個(gè)值的時(shí)候才同時(shí)滿足上面兩個(gè)條件,，這時(shí)候才會(huì)發(fā)生擴(kuò)容現(xiàn)象,。
|
