面試之HashMap中的常量

HashMap中有很多常量數(shù)字,如默認初始大小(DEFAULT_INITIAL_CAPACITY)=16最大容量(MAXIMUM_CAPACITY)=2^{30},默認加載因子(DEFAULT_LOAD_FACTOR)=0.75,鏈表轉(zhuǎn)換紅黑樹的閥值(TREEIFY_THRESHOLD)=8,這些常量是根據(jù)什么定義的呢?

默認初始大小(16)

這個初始的大小是1 << 4,也就是2^{4},首先這個初始大小是2的倍數(shù),因為當length是2的倍數(shù)的時候index = h % length可以優(yōu)化成 h & (length-1),&效率高于%,其次是2的倍數(shù)為什么不是4,8,32而是16呢,如果太小的話擴容頻繁,太大的話占用內(nèi)存空間

最大容量

Map中bucket的長度限制是2^{30},這里不是說只能放2^{30}個key-value鍵值對,因為HashMap是數(shù)組加鏈表結(jié)構(gòu),這個的bucket是數(shù)組的長度,理論上Map的數(shù)據(jù)量取決于機器內(nèi)存的大小

默認加載因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;
0.75 這個默認加載因子的取值是空間跟時間的折中,源碼中有注釋:

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.
當加載因子是0.75的時候,初始大小16的情況下,存放16*0.75=12個元素的時候需要擴容成32,如果這個加載因子太小則會頻繁擴容,反之太大的話需要全部放滿才擴容容易產(chǎn)生hash碰撞

鏈表轉(zhuǎn)換紅黑樹的閥值

這個值8的話跟加載因子一樣,也是一個概率問題

參考:http://www.itdecent.cn/p/64f6de3ffcc1

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Java集合:HashMap源碼剖析 一、HashMap概述 二、HashMap的數(shù)據(jù)結(jié)構(gòu) 三、HashMap源碼...
    記住時光閱讀 775評論 2 1
  • 一、HashMap概述 HashMap基于哈希表的Map接口的實現(xiàn)。此實現(xiàn)提供所有可選的映射操作,并允許使用nul...
    小陳阿飛閱讀 673評論 0 2
  • 前言 HashMap HashMap類繼承圖 HashMap屬性 HashMap構(gòu)造函數(shù)HashMap(int i...
    HikariCP閱讀 1,928評論 0 5
  • 按照從構(gòu)造方法->常用API(增、刪、改、查)的順序來閱讀源碼,并做簡要分析。 一. 概要 概括的說HashMap...
    stoneyang94閱讀 397評論 0 1
  • 以A將信息發(fā)送給B為例 對稱加密:A生成密鑰,將密鑰給B。A使用密鑰將信息進行加密,將加密后的信息發(fā)送給B,B得到...
    he_321閱讀 657評論 0 0

友情鏈接更多精彩內(nèi)容