問題: 確定只裝載10個(gè)元素, HashMap初始容量多少是最佳?

答案: 16

目的: 防止HashMap頻繁擴(kuò)容,影響性能

解析:

HashMap的底層數(shù)據(jù)結(jié)構(gòu)是由 數(shù)組 和 單向鏈表 組成

    擴(kuò)容概念: 當(dāng)所用數(shù)組的長度  大于 初始長度 * 0.75(負(fù)載因子)時(shí),數(shù)組擴(kuò)容
        Map<String, String> map = new HashMap<String, String>();
        等同于
        Map<String, String> map = new HashMap<String, String>(16);
        
        初始化容量默認(rèn)為16,當(dāng)數(shù)組使用超過 16 * 0.75 = 12 時(shí)(數(shù)組使用第13個(gè)元素時(shí))擴(kuò)容

舉例:

    map的初始容量為4,向map中放入6個(gè)元素,有可能擴(kuò)容,有可能不擴(kuò)容

    如果所用數(shù)組長度小于 4 * 0.75 = 3,不擴(kuò)容

不擴(kuò)容,數(shù)據(jù)結(jié)構(gòu)如下:

        由于key的hash值相同,產(chǎn)生碰撞,放入到數(shù)組中的同一位置,形成單向鏈表

不擴(kuò)容的數(shù)據(jù)結(jié)構(gòu)

擴(kuò)容的情況如下:

由于key的hash值不同,放入到數(shù)組中的不同位置,當(dāng)放第四個(gè)元素時(shí),HashMap擴(kuò)容為8

擴(kuò)容源碼如下:
// ++ this.size = 4      this.threshold = 4 * 0.75 = 3
if (++this.size > this.threshold) {
    this.resize();
}

擴(kuò)容數(shù)據(jù)結(jié)構(gòu)

假設(shè)10個(gè)元素尋址運(yùn)算得到的index都不相同,初始容量應(yīng)為 10 / 0.75 = 13.3向上取整,初始容量為14,此時(shí)不會(huì)擴(kuò)容

通過閱讀HashMap源碼可知,容量大小為 2 的 n次方.所以應(yīng)該取第一個(gè)大于14 的 2 的 n次方 值,為 16

新的問題: 容量大小為什么必須是 2 的 n次方?14為什么不行??

原因: 避免 哈希桶資源浪費(fèi)

解析:

 map.put("key","value")時(shí),尋址算法為 length-1 & key.hash --> 13 &  key.hash
    length-1 : 00000000000000000000000000001101
    key1.hash: 11111111111111110000111100000111
    --------------------------------
    00000000000000000000000000000101 = 5

    如果容量為14 , length-1 = 13  , 13的二進(jìn)制位1101,1101 與別的數(shù)值 進(jìn)行 & 運(yùn)算, 倒數(shù)第二位得到的永遠(yuǎn)是0,對(duì)空間造成浪費(fèi),同時(shí)會(huì)增大hash尋址得到的index相同的概率

    所以length-1 的二進(jìn)制 應(yīng)當(dāng)全部為1,將hash表的長度設(shè)為2的N次方

    2的N次方 -1 的二進(jìn)制全部為1,所有的哈希桶均有被使用的可能

    避免了上述問題,所以初始容量應(yīng)為16


    其實(shí)無論你的HashMap(x)中的x設(shè)置為多少，HashMap的大小都是2^n。2^n是大于x的第一個(gè)數(shù)。因?yàn)镠ashMap的初始化代碼中有以下這行代碼：
        static final int tableSizeFor(int var0) {
            int var1 = var0 - 1;
            var1 |= var1 >>> 1;
            var1 |= var1 >>> 2;
            var1 |= var1 >>> 4;
            var1 |= var1 >>> 8;
            var1 |= var1 >>> 16;
            return var1 < 0 ? 1 : (var1 >= 1073741824 ? 1073741824 : var1 + 1);
        }