前言：
HashMap的size大于等于(容量*加載因子)的時(shí)候,會(huì)觸發(fā)擴(kuò)容的操作,這個(gè)是個(gè)代價(jià)不小的操作。
為什么要擴(kuò)容呢?HashMap默認(rèn)的容量是16,隨著元素不斷添加到HashMap里,出現(xiàn)hash沖突的機(jī)率就更高,那每個(gè)桶對(duì)應(yīng)的鏈表就會(huì)更長(zhǎng),
這樣會(huì)影響查詢(xún)的性能,因?yàn)槊看味夹枰闅v鏈表,比較對(duì)象是否相等,一直到找到元素為止。
為了提升查詢(xún)性能,只能擴(kuò)容,減少hash沖突,讓元素的key盡量均勻的分布。
擴(kuò)容基本點(diǎn)
加載因子默認(rèn)值是0.75
|
1
|
static final float DEFAULT_LOAD_FACTOR = 0.75f; |
容量的默認(rèn)值是16
|
1
|
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 等于16 |
HashMap提供了一個(gè)構(gòu)造參數(shù),可以在創(chuàng)建的時(shí)候指定容量和加載因子。
|
1
|
public HashMap(int initialCapacity, float loadFactor) |
默認(rèn)的情況下,HashMap 的size一旦大于等于16*0.75=12的話,
同時(shí)每個(gè)Entry(或者叫桶)里面至少有一個(gè)元素的時(shí)候就會(huì)進(jìn)行擴(kuò)容。
|
1
2
3
4
5
|
if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length);} |
擴(kuò)容的時(shí)候,容器容量翻倍
|
1
|
resize(2 * table.length); |
擴(kuò)容的時(shí)候需要重新計(jì)算元素的數(shù)組下標(biāo)
1、重新分配一個(gè)新的Entry數(shù)組
2、重新計(jì)算原來(lái)元素的在新數(shù)組中的下標(biāo)(比較耗資源)
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
原文鏈接：http://blog.csdn.net/linsongbin1/article/details/54695986
