1.HashMap的底層實(shí)現(xiàn)圖示

如上圖所示：

HashMap底層是由? 數(shù)組+(鏈表)=(紅黑樹)?組成，每個(gè)存儲(chǔ)在HashMap中的鍵值對(duì)都存放在一個(gè)Node節(jié)點(diǎn)之中，其中包含了Key-Value之外，還包括hash值(key.hashCode()) ^ (h >>> 16)) 以及執(zhí)行下一個(gè)節(jié)點(diǎn)的指針next。

2.HashMap源碼分析

2.1 重要常量

public?class?HashMap?extends?AbstractMap????implements?Map,?Cloneable,?Serializable?{????private?static?final?long?serialVersionUID?=?362498820763181265L;????static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<

static?final?int?MAXIMUM_CAPACITY?=?1?<[]?table;

transient?Set>?entrySet;

transient?int?size;

transient?int?modCount;

int?threshold;

final?float?loadFactor;

DEFAULT_INITIAL_CAPACITY : HashMap的默認(rèn)容量，16

MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30

DEFAULT_LOAD_FACTOR：HashMap的默認(rèn)加載因子

TREEIFY_THRESHOLD：Bucket中鏈表長(zhǎng)度大于該默認(rèn)值，轉(zhuǎn)化為紅黑樹

UNTREEIFY_THRESHOLD：Bucket中紅黑樹存儲(chǔ)的Node小于該默認(rèn)值，轉(zhuǎn)化為鏈表

MIN_TREEIFY_CAPACITY：桶中的Node被樹化時(shí)最小的hash表容量。(當(dāng)桶中Node的數(shù)量大到需要變紅黑樹時(shí)，若hash表容量小于MIN_TREEIFY_CAPACITY時(shí)，此時(shí)應(yīng)執(zhí)行resize擴(kuò)容操作這個(gè)MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。)

table：存儲(chǔ)元素的數(shù)組，總是2的n次冪

entrySet：存儲(chǔ)具體元素的集

size:HashMap中存儲(chǔ)的鍵值對(duì)的數(shù)量

modCount：HashMap擴(kuò)容和結(jié)構(gòu)改變的次數(shù)。

threshold：擴(kuò)容的臨界值，=容量*填充因子

loadFactor：填充因子

2.2 重要方法

1.獲取hash值? hashstatic?final?int?hash(Object?key)?{????????int?h;????????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);

}

hash方法用傳入的key的hashCode和hashCode無符號(hào)右移16位的結(jié)果，做異或運(yùn)算后作為hash值返回。

注：之所以獲取hashCode后，還需要和右移16位的hashCode做異或運(yùn)算，原因是：在根據(jù)hash值獲取鍵值對(duì)在bucket數(shù)組中的下標(biāo)時(shí)，采用的算法是：index=h & (length-1),當(dāng)數(shù)組的length較小時(shí)，只有低位能夠參與到“與”運(yùn)算中，但是將hashCode右移16位再與本身做異或獲取到的hash，可以使高低位均能夠參與到后面的與運(yùn)算中。

下面圖說明：

2.根據(jù)鍵值對(duì)數(shù)量獲取HashMap容量方法? ?tableSizeFor

static?final?int?tableSizeFor(int?cap)?{????????int?n?=?cap?-?1;

n?|=?n?>>>?1;

n?|=?n?>>>?2;

n?|=?n?>>>?4;

n?|=?n?>>>?8;

n?|=?n?>>>?16;????????return?(n?=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;

}

tabSizeFor方法，主要根據(jù)傳入的鍵值對(duì)容量，來返回大于容量的最小的二次冪數(shù)值。

算法如下：

將傳入的容量-1：至于這里為什么需要減1，是為了防止cap已經(jīng)是2的冪。如果cap已經(jīng)是2的冪, 又沒有執(zhí)行這個(gè)減1操作,則執(zhí)行完后面的幾條無符號(hào)右移操作之后,返回的capacity將是這個(gè)cap的2倍，各位可自行驗(yàn)證：

假設(shè)原始n:? ? 0001? xxxx xxxx xxxx第一次右移1位+或運(yùn)算：二進(jìn)制序列出現(xiàn)至少兩個(gè)連續(xù)的1，如?0001?1xxx?xxxx?xxxx；第二次右移2位+或運(yùn)算：二進(jìn)制序列出現(xiàn)至少四個(gè)連續(xù)的1，如?0001?111x?xxxx?xxxx；

第三次右移4位+或運(yùn)算：二進(jìn)制序列出現(xiàn)至少八個(gè)連續(xù)的1,?如?0001?1111?1111?xxxx;

第四次右移8位+或運(yùn)算：二進(jìn)制序列至少出現(xiàn)16個(gè)連續(xù)的1，如?0001?1111?1111?1111;第五次右移16位+或運(yùn)算：二進(jìn)制序列至少出現(xiàn)32個(gè)連續(xù)的1，如?0001?1111?1111?1111;上述運(yùn)算中，若出現(xiàn)右移后為0，則或運(yùn)算得到的結(jié)果和原始值一致，則后續(xù)推導(dǎo)過程可以忽略。

此時(shí)可以保證，原始序列從包含1的最高位，到最低位，全部都變成了1.

最后+1，返回的結(jié)果就是大于原值的最小二次冪數(shù)。

3.插入方法? ?putVal

1??final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,?2????????????????????boolean?evict)?{?3?????????????????????4?????????Node[]?tab;????//存儲(chǔ)Node節(jié)點(diǎn)的數(shù)組tab?5?????????Node?p;?????????//單個(gè)Node節(jié)點(diǎn)p?6?????????int?n,?i;????????????//HashMap的容量n?7?????????//初始化數(shù)組桶table?8?????????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)?9?????????????n?=?(tab?=?resize()).length;10?????????//如果數(shù)組桶中不包含要插入的元素，將新鍵值對(duì)作為新Node存入數(shù)組，11?????????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)????//此處p初始化，p和需要存儲(chǔ)的鍵值對(duì)下標(biāo)相同且P是鏈表的第一個(gè)元素12?????????????tab[i]?=?newNode(hash,?key,?value,?null);13?????????????14?????????//桶中包含要插入的元素15?????????else?{16?????????????Node?e;?K?k;17?????????????//如果key和鏈表第一個(gè)元素p的key相等18?????????????if?(p.hash?==?hash?&&19?????????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))20?????????????//則將e指向該鍵值對(duì)21?????????????????e?=?p;22?????????????//若p是TreeNode類型，則使用紅黑樹的方法插入到樹中23?????????????else?if?(p?instanceof?TreeNode)24?????????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);25?????????????//else：鍵值對(duì)的引用不在鏈表的第一個(gè)節(jié)點(diǎn)，此時(shí)需要遍歷鏈表????26?????????????else?{27?????????????????for?(int?binCount?=?0;?;?++binCount)?{28?????????????????????//將e指向p的下一個(gè)元素，直到其next為null時(shí)，將鍵值對(duì)作為新Node放到p的尾部或樹中。29?????????????????????if?((e?=?p.next)?==?null)?{30?????????????????????????p.next?=?newNode(hash,?key,?value,?null);31?????????????????????????//如果遍歷鏈表的長(zhǎng)度大于等于8，則變成樹32?????????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st33?????????????????????????????treeifyBin(tab,?hash);34?????????????????????????break;???//新元素已追加到鏈表尾部或樹中，退出遍歷35?????????????????????}36?????????????????????//在沖突鏈表中找到另一個(gè)具有相同key值的節(jié)點(diǎn)，退出遍歷37?????????????????????if?(e.hash?==?hash?&&38?????????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))39?????????????????????????break;40?????????????????????????41?????????????????????//將e指向p,便于下次遍歷e?=?p.next42?????????????????????p?=?e;43?????????????????}44?????????????????//上述for循環(huán)執(zhí)行完畢后，e要么指向了存儲(chǔ)的新節(jié)點(diǎn)，要么是原來已有的元素，具有和新節(jié)點(diǎn)一樣key值45?????????????}46?????????????//當(dāng)e非空時(shí)，說明e是原來HashMap中的元素，具有和新節(jié)點(diǎn)一樣的key值47?????????????if?(e?!=?null)?{?//?existing?mapping?for?key48?????????????????V?oldValue?=?e.value;49?????????????????if?(!onlyIfAbsent?||?oldValue?==?null)????//onlyIfAbsent?表示是否僅在?oldValue?為?null?的情況下更新鍵值對(duì)的值50?????????????????????e.value?=?value;51?????????????????//空實(shí)現(xiàn)，LinkedHashMap用52?????????????????afterNodeAccess(e);53?????????????????return?oldValue;54?????????????}55?????????}56?????????//HashMap結(jié)構(gòu)更改，modCount+157?????????++modCount;58?????????//判斷是否需要擴(kuò)容59?????????if?(++size?>?threshold)60?????????????resize();61?????????//空實(shí)現(xiàn)，LinkedHashMap用62?????????afterNodeInsertion(evict);63?????????return?null;64?????}

HashMap中進(jìn)行存儲(chǔ)的入口方法是：put(K，V)，但是核心方法是putVal方法，該方法一共有以下步驟：初始化數(shù)組桶

判斷數(shù)組桶中對(duì)應(yīng)下標(biāo)是否無元素存在，是，就直接存入

若數(shù)組桶中對(duì)應(yīng)下標(biāo)有元素存在，則開始遍歷，根據(jù)長(zhǎng)度將元素存入鏈表尾部或樹中。

判斷是否需要擴(kuò)容

4.擴(kuò)容方法? ?resize

1?final?Node[]?resize()?{??2?????????Node[]?oldTab?=?table;??3?????????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;????//原HashMap的容量??4?????????int?oldThr?=?threshold;????????????????????????????????//原HashMap的擴(kuò)容臨界值??????????????????5?????????int?newCap,?newThr?=?0;??6?????????//case1:odlCap>0,說明桶數(shù)組已經(jīng)初始化過??7?????????if?(oldCap?>?0)?{??8?????????????//原HashMap的越界檢查??9?????????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{?10?????????????????threshold?=?Integer.MAX_VALUE;?11?????????????????return?oldTab;?12?????????????}?13?????????????//容量擴(kuò)大一倍后的越界檢查?14?????????????else?if?((newCap?=?oldCap?<=?DEFAULT_INITIAL_CAPACITY)?16?????????????????newThr?=?oldThr?<0，桶數(shù)組尚未初始化,當(dāng)調(diào)用帶初始化容量的構(gòu)造函數(shù)時(shí)會(huì)發(fā)生該情況?19?????????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold?20?????????????//在前面HashMap的初始化中，將Initial?capcity暫存在threshold中?21?????????????newCap?=?oldThr;?//未初始化，則用Initial?capcity作為新的容量?22??????????????23?????????????//若oldThr?=?threshold?=?0，則說明未傳入初始化容量參數(shù)?24??????????????25?????????//case3：oldCap=0?&&?oldThr?=?0，當(dāng)調(diào)用無參構(gòu)造函數(shù)時(shí)會(huì)發(fā)生該情況，此時(shí)使用默認(rèn)容量初始化?26?????????else?{???????????????//?zero?initial?threshold?signifies?using?defaults?27?????????????newCap?=?DEFAULT_INITIAL_CAPACITY;????//默認(rèn)容量?28?????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);????//默認(rèn)擴(kuò)容臨界值?29?????????}?30??????????31?????????//?當(dāng)newThr?為?0?時(shí)，閾值按照計(jì)算公式進(jìn)行計(jì)算?32?????????if?(newThr?==?0)?{?33?????????????float?ft?=?(float)newCap?*?loadFactor;?34?????????????newThr?=?(newCap?[]?newTab?=?(Node[])new?Node[newCap];?46?????????table?=?newTab;?47?????????//若oldTab非空，則需要將原來桶數(shù)組的元素取出來放到新的桶數(shù)組中?48?????????if?(oldTab?!=?null)?{?49?????????????for?(int?j?=?0;?j??e;?51?????????????????if?((e?=?oldTab[j])?!=?null)?{?52?????????????????????oldTab[j]?=?null;????//將原桶數(shù)組的元素占用的空間釋放，便于GC?53?????????????????????if?(e.next?==?null)????

54?????????????????????????//若桶中元素的next為空，獲取index后直接將其放入新桶數(shù)組中?55?????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;?56?????????????????????????//若桶中元素的next是樹節(jié)點(diǎn)?57?????????????????????else?if?(e?instanceof?TreeNode)?58?????????????????????????//采用樹的方式插入?59?????????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);?60?????????????????????????//若桶中元素的next是鏈表節(jié)點(diǎn)?61?????????????????????else?{?//?preserve?order?62?????????????????????????Node?loHead?=?null,?loTail?=?null;?63?????????????????????????Node?hiHead?=?null,?hiTail?=?null;?64?????????????????????????Node?next;?65??????????????????????????66?????????????????????????/*遍歷原鏈表，按照原來的順序進(jìn)行分組?67?????????????????????????*/?68??????????????????????????69??????????????????????????70?????????????????????????/*原始鏈表中的元素，在resize之后，其下標(biāo)有兩種可能，一種是在原來下標(biāo)處，另一種是原來下標(biāo)+oldCap處?71?????????????????????????*舉例說明：??若原來的容量?-1后?只有n位，低位有n個(gè)1，去下標(biāo)公式為：i?=?(oldCap?-?1)?&?hash，若hash值只有低n為有值，則與運(yùn)算后獲得的值和?72?????????????????????????*擴(kuò)容前是一樣的，若hash不止第n位有值，那采用與運(yùn)算后，結(jié)果比原來剛好大oldCap。?下面有圖片示例)?73?????????????????????????*/?74

75??????????????????????????76?????????????????????????do?{?77?????????????????????????????next?=?e.next?78?????????????????????????????//若e.e.hash?&?oldCap?結(jié)果為0，則下標(biāo)在新桶數(shù)組中不用改變，此時(shí)，將元素存放在loHead為首的鏈表中?79?????????????????????????????if?((e.hash?&?oldCap)?==?0)?{?80?????????????????????????????????if?(loTail?==?null)?81?????????????????????????????????????loHead?=?e;?82?????????????????????????????????else?83?????????????????????????????????????loTail.next?=?e;?84?????????????????????????????????loTail?=?e;?85?????????????????????????????}?86??????????????????????????????87?????????????????????????????//若e.e.hash?&?oldCap?結(jié)果不為0，則下標(biāo)在新桶數(shù)組等于原下標(biāo)+oldCap，此時(shí)，將元素存放在hiHead為首的鏈表中?88?????????????????????????????else?{?89?????????????????????????????????if?(hiTail?==?null)?90?????????????????????????????????????hiHead?=?e;?91?????????????????????????????????else?92?????????????????????????????????????hiTail.next?=?e;?93?????????????????????????????????hiTail?=?e;?94?????????????????????????????}?95?????????????????????????}?while?((e?=?next)?!=?null);?96??????????????????????????97??????????????????????????98??????????????????????????99?????????????????????????if?(loTail?!=?null)?{????????//loHead為首的鏈表中，下標(biāo)不改變100?????????????????????????????loTail.next?=?null;101?????????????????????????????newTab[j]?=?loHead;102?????????????????????????}103?????????????????????????if?(hiTail?!=?null)?{????????//hiHead為首的鏈表中，下標(biāo)=原下標(biāo)+oldCap104?????????????????????????????hiTail.next?=?null;105?????????????????????????????newTab[j?+?oldCap]?=?hiHead;106?????????????????????????}107?????????????????????}108?????????????????}109?????????????}110?????????}111?????????return?newTab;????????

112?????}

上述代碼分析較長(zhǎng)，總結(jié)如下：

1.獲取不同情況下的 新的容量 和 新的擴(kuò)容臨界值

2.根據(jù)新容量創(chuàng)建新的桶數(shù)組tab。

3.根據(jù)節(jié)點(diǎn)類型，樹節(jié)點(diǎn)和鏈表節(jié)點(diǎn)分別采用對(duì)應(yīng)方法放入新的桶數(shù)組

5.移除元素? remove

1??final?Node?removeNode(int?hash,?Object?key,?Object?value,?2????????????????????????????????boolean?matchValue,?boolean?movable)?{?3?????????Node[]?tab;?Node?p;?int?n,?index;?4??????????5?????????//通過hash值獲取下標(biāo)，下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)p不為空?6?????????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&?7?????????????(p?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{?8?????????????Node?node?=?null,?e;?K?k;?V?v;?9?????????????//若節(jié)點(diǎn)p的key和待移除的節(jié)點(diǎn)key相等10?????????????if?(p.hash?==?hash?&&11?????????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))12?????????????????//則p就是待移除節(jié)點(diǎn)13?????????????????node?=?p;????//將p指向待移除節(jié)點(diǎn)14?????????????//p的key和待移除的節(jié)點(diǎn)key不相等，遍歷p作為頭的鏈表或者樹15?????????????else?if?((e?=?p.next)?!=?null)?{16?????????????????//若p是樹節(jié)點(diǎn)17?????????????????if?(p?instanceof?TreeNode)18?????????????????????//采用樹節(jié)點(diǎn)方式獲得要移除的節(jié)點(diǎn)19?????????????????????node?=?((TreeNode)p).getTreeNode(hash,?key);20?????????????????else?{//p是鏈表的頭節(jié)點(diǎn)21?????????????????????do?{22?????????????????????????//采用循環(huán)，當(dāng)p.next不為空，比對(duì)它和傳入的key，直到找到相等的key23?????????????????????????if?(e.hash?==?hash?&&24?????????????????????????????((k?=?e.key)?==?key?||25??????????????????????????????(key?!=?null?&&?key.equals(k))))?{26?????????????????????????????//找到后，將節(jié)點(diǎn)指向node27?????????????????????????????node?=?e;????//將e指向待移除節(jié)點(diǎn)，此時(shí)相當(dāng)于p.next就是待移除的節(jié)點(diǎn)node，可自行驗(yàn)證循環(huán)便知28?????????????????????????????break;29?????????????????????????}30?????????????????????????p?=?e;??

31?????????????????????}?while?((e?=?e.next)?!=?null);32?????????????????}33?????????????}34?????????????//若node非空，傳入的matchValue參數(shù)為flase或?node的value等于傳入value35????????????if?(node?!=?null?&&?(!matchValue?||?(v?=?node.value)?==?value?||36??????????????????????????????????(value?!=?null?&&?value.equals(v))))?{37?????????????????//若node是樹節(jié)點(diǎn)38?????????????????if?(node?instanceof?TreeNode)39?????????????????????//采用樹節(jié)點(diǎn)的方式移除40?????????????????????((TreeNode)node).removeTreeNode(this,?tab,?movable);41?????????????????????//若待移除節(jié)點(diǎn)是鏈表頭，將其指向待移除元素的next，移除對(duì)node的引用42?????????????????else?if?(node?==?p)43?????????????????????tab[index]?=?node.next;

44?????????????????else//待移除元素是鏈表中的元素，此時(shí)其等于p.next45?????????????????????//將p.next指向node.next，移除了對(duì)node的引用46?????????????????????p.next?=?node.next;47?????????????????//增加結(jié)構(gòu)修改計(jì)數(shù)器48?????????????????++modCount;49?????????????????//size-150?????????????????--size;51?????????????????//空實(shí)現(xiàn)，LinkedHashMap用52?????????????????afterNodeRemoval(node);53?????????????????54?????????????????//返回移除的節(jié)點(diǎn)node55?????????????????return?node;56?????????????}57?????????}58?????????return?null;59?????}

移除節(jié)點(diǎn)的入口方法是：?public V remove(Object key)? ，其核心方法是removeNode，主要做了以下幾個(gè)工作：通過用key獲取的hash，來獲取下標(biāo)。

若下標(biāo)對(duì)應(yīng)處無元素，返回null。

若下標(biāo)對(duì)應(yīng)處有元素，判斷是樹或者鏈表，采用對(duì)應(yīng)方法移除。

6.查找元素方法 get

1?????final?Node?getNode(int?hash,?Object?key)?{?2?????????Node[]?tab;?Node?first,?e;?int?n;?K?k;?3?????????//根據(jù)hash值，獲取對(duì)應(yīng)下標(biāo)的第一個(gè)元素first?4?????????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&?5?????????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{?6?????????????//如果first的key和待查詢的key相等，返回first?7?????????????if?(first.hash?==?hash?&&?//?always?check?first?node?8?????????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))?9?????????????????return?first;10?????????????//若first不是待查詢的元素11?????????????if?((e?=?first.next)?!=?null)?{12?????????????????//若first是樹節(jié)點(diǎn)，采用樹節(jié)點(diǎn)的方式獲取13?????????????????if?(first?instanceof?TreeNode)14?????????????????????return?((TreeNode)first).getTreeNode(hash,?key);15?????????????????//first是鏈表節(jié)點(diǎn)頭，使用循環(huán)獲取16?????????????????do?{17?????????????????????if?(e.hash?==?hash?&&18?????????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))19?????????????????????????return?e;20?????????????????}?while?((e?=?e.next)?!=?null);21?????????????}22?????????}23?????????return?null;24?????}

查詢?cè)氐娜肟诜椒ㄊ?#xff1a;public V get(Object key)，返回值是node的value，核心方法是getNode(int hash, Object key)。

2.3 構(gòu)造方法

1.無參構(gòu)造函數(shù)public?HashMap()?{????????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted

}

使用所有默認(rèn)參數(shù)來構(gòu)造一個(gè)HashMap，我們常用的就是這種。

2.給出容量的構(gòu)造函數(shù)public?HashMap(int?initialCapacity)?{????????this(initialCapacity,?DEFAULT_LOAD_FACTOR);

}

此處調(diào)用了下面這個(gè)構(gòu)造函數(shù)，將給出的容量傳入和默認(rèn)負(fù)載因子。

3.給出容量和負(fù)載因子的構(gòu)造函數(shù)

public?HashMap(int?initialCapacity,?float?loadFactor)?{

//容量越界檢查????????if?(initialCapacity?

initialCapacity);????????if?(initialCapacity?>?MAXIMUM_CAPACITY)

initialCapacity?=?MAXIMUM_CAPACITY;

//負(fù)載因子非負(fù)非空檢查????????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))????????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+

loadFactor);

this.loadFactor?=?loadFactor;

this.threshold?=?tableSizeFor(initialCapacity);??//此處將初始化的容量暫存到threshold中

}

4.用一個(gè)map來初始化的構(gòu)造函數(shù)public?HashMap(Map?extends?K,???extends?V>?m)?{????????this.loadFactor?=?DEFAULT_LOAD_FACTOR;

putMapEntries(m,?false);

}

此處將map中所有元素放入HashMap進(jìn)行初始化。

3.常見問題解答

3.1 HashMap的容量為什么必須是2的n次冪？

答：當(dāng)容量是2的n次冪時(shí)，不同的key獲取在桶數(shù)組中的下標(biāo)相同的概率減小，發(fā)生Hash碰撞幾率減少，元素分布更加均勻，見下圖。

結(jié)論：

1.由上述實(shí)例可以看出，當(dāng)HashMap容量為2的n次冪的時(shí)候，length-1，可以使得在計(jì)算index的"&"運(yùn)算過程中，hash值的對(duì)應(yīng)位都能參與到計(jì)算；若HashMap容量不等于2的n次冪，leng-1后必然有一些位是等于0的，那么在計(jì)算index的"&"運(yùn)算過程中，對(duì)應(yīng)位的數(shù)字無論是0或者1，都未能參與到運(yùn)算中。導(dǎo)致Hash沖突概率增大。

2.初次之外，若HashMap容量不為2的n次冪，無論Hash值如何變化，始終有一些下標(biāo)值無法取得，因?yàn)?#34;&"運(yùn)算過程中，必然有一些位置結(jié)果始終為0，如實(shí)例所示，其最低位始終為0，因此下標(biāo) 1(二進(jìn)制0000 0001)、3(二進(jìn)制0000 0011)、5(二進(jìn)制0000 0101)、7(二進(jìn)制0000 0111)等下標(biāo)、永遠(yuǎn)都獲取不了。造成了容量的浪費(fèi)

3.2 HashMap的時(shí)間復(fù)雜度？

答：O(1)或者O(log(n))或O(n),分析如下:

根據(jù)第一節(jié)的內(nèi)容可知，根據(jù)HashMap的數(shù)據(jù)結(jié)構(gòu)，可能有以下三種情況：

1.無鏈表和紅黑樹，理想狀態(tài)。每個(gè)桶只有一個(gè)或0個(gè)元素，不存在Hash沖突，此時(shí)時(shí)間復(fù)雜度為O(1);但此時(shí)耗費(fèi)的內(nèi)存空間較大。

2.只有鏈表，此時(shí)因?yàn)樾枰h(huán)鏈表來獲取元素，時(shí)間復(fù)雜度為O(n)

3.只有紅黑樹，此時(shí)時(shí)間復(fù)雜度為紅黑樹查找的時(shí)間復(fù)雜度，O(log(n)).

4.鏈表和紅黑樹均有，此時(shí)時(shí)間復(fù)雜度依據(jù)紅黑樹的層數(shù)和鏈表長(zhǎng)度而定。為O(n)或者O(log(n)).

3.3 負(fù)載因子LoadFactor為何默認(rèn)值為0.75。

當(dāng)負(fù)載因子過大時(shí)，Hash沖突概率增加、讀寫的時(shí)間復(fù)雜度也大大增加，當(dāng)負(fù)載因子過小時(shí)，Hash沖突概率較小，時(shí)間復(fù)雜度較低，但占用內(nèi)存空間較大。

至于為什么默認(rèn)值是0.75，這是一個(gè)基于時(shí)間和空間復(fù)雜度的綜合考慮的結(jié)果，可以參考這篇文章：HashMap的loadFactor為什么是0.75？

3.4 作為HasHMap的key有什么條件？

使用HashMap，若用int/String等作為key值，因?yàn)镮nteger類和String類都以及重寫了equals()和hashCode()方法.

但是如果key是自定義的類，就必須重寫hashcode()和equals()。理由如下：

//在插入元素中，根據(jù)hash值后，與length-1做&運(yùn)算獲取下標(biāo)???????//獲取hash

static?final?int?hash(Object?key)?{????????int?h;????????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);

}???????//獲取下標(biāo)

p?=?tab[i?=?(n?-?1)?&?hash]????//用equals方法比對(duì)key值和節(jié)點(diǎn)的key值，來確認(rèn)是否遍歷到所需元素

(key?!=?null?&&?key.equals(k)))

/*對(duì)比hash值，如果不重寫hashCode方法，那么采用Object類的默認(rèn)的hash方法是獲取內(nèi)存地址，此時(shí)即使兩個(gè)key對(duì)象相等，但其內(nèi)存地址不可能相等，所以必須重寫hashCode方法。*//*equals方法若不重寫，采用的Object的equals方法，比對(duì)的是內(nèi)存地址，如果不重寫，會(huì)造成兩個(gè)一樣的key值都插入，存在重復(fù)元素*/

//同理，在查找過程中，在第二節(jié)putVal方法中有分析，會(huì)用到hash值，以及用到key.equals方法，因此如果不重寫equals()和hashCode()，會(huì)造成雖然元素存在，但是因內(nèi)存地址不一致，差找不到對(duì)應(yīng)元素。

3.5 HashMap key允許為空嗎？，最多幾個(gè)？

答：允許但只允許一個(gè)key值為空。當(dāng)key值為空時(shí)，其hash值為0，因此在桶數(shù)組中位置是0，即第一個(gè)元素。

那么為什么不能有兩個(gè)key值為null呢，原因是兩個(gè)key為null，是一樣的，后面put進(jìn)去的(null,value2)會(huì)覆蓋先put進(jìn)去的(null,value1)。驗(yàn)證如下：

3.6 HashMap value允許為空嗎？最多幾個(gè)？

答：允許，可以有多個(gè)value為null，查看源碼可知，在putVal中沒有對(duì)value進(jìn)行限制，驗(yàn)證如下：

寫在最后：

1.本文中設(shè)計(jì)到數(shù)操作的都沒有詳細(xì)介紹，因?yàn)榧t黑樹本身概念較為抽象復(fù)雜，打算下一篇文章中再來詳細(xì)分析一下，還有其他一些類似于“map.clear()、map.ContainsKey()”等等邏輯較為簡(jiǎn)單的方法也未作贅述。

2.不得不感嘆一些設(shè)計(jì)Java集合類的大牛是真的牛，看似一個(gè)簡(jiǎn)單的HashMap中、對(duì)于位運(yùn)算、鏈表。紅黑樹的應(yīng)用可謂是爐火純青，看起來都不能一目了然，設(shè)計(jì)時(shí)那更是天馬行空，匠心獨(dú)運(yùn)。

總結(jié)

以上是生活随笔為你收集整理的查询已有链表的hashmap_源码分析系列1：HashMap源码分析（基于JDK1.8）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。