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.源碼分析
2.1幾個(gè)重要常量
static final int DEFAULT_INITIAL_CAPACITY =1 <<4;??HashMap的默認(rèn)容量畅形，16
static final int MAXIMUM_CAPACITY =1 <<30;? HashMap的最大支持容量养距，2^30
static final float DEFAULT_LOAD_FACTOR =0.75f;??HashMap的默認(rèn)加載因子
static final int TREEIFY_THRESHOLD =8;??Bucket中鏈表長(zhǎng)度大于該默認(rèn)值，轉(zhuǎn)化為紅黑樹
static final int UNTREEIFY_THRESHOLD =6;??Bucket中紅黑樹存儲(chǔ)的Node小于該默認(rèn)值日熬，轉(zhuǎn)化為鏈表
static final int MIN_TREEIFY_CAPACITY =64;?桶中的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倍耘纱。）
transient Node[] table;??存儲(chǔ)元素的數(shù)組，總是2的n次冪
transient Set>entrySet;??存儲(chǔ)具體元素的集
transient int size;?HashMap中存儲(chǔ)的鍵值對(duì)的數(shù)量
transient int modCount;?HashMap擴(kuò)容和結(jié)構(gòu)改變的次數(shù)毕荐。
int threshold;?擴(kuò)容的臨界值束析，=容量*填充因子
final float loadFactor;??填充因子
2.2幾個(gè)重要方法
1）無參構(gòu)造方法
public HashMap() {
????this.loadFactor =DEFAULT_LOAD_FACTOR;// all other fields defaulted
}
無參構(gòu)造方法，設(shè)定了負(fù)載因子為0.75的默認(rèn)值
2）指定容量的構(gòu)造方法
public HashMap(int initialCapacity) {
????this(initialCapacity,DEFAULT_LOAD_FACTOR);
}
這種構(gòu)造方法憎亚，最后會(huì)調(diào)用3中的指定容量和負(fù)載因子的構(gòu)造方法员寇，將負(fù)載因子設(shè)置為默認(rèn)值
3）指定容量和負(fù)載因子的構(gòu)造方法
public HashMap(int initialCapacity,float loadFactor) {
????if (initialCapacity <0)
????????throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
????if (initialCapacity >MAXIMUM_CAPACITY)
????????initialCapacity =MAXIMUM_CAPACITY;
????if (loadFactor <=0 || Float.isNaN(loadFactor))
????????throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
????this.loadFactor = loadFactor;
????this.threshold =tableSizeFor(initialCapacity);
}
這個(gè)構(gòu)造方法來確定負(fù)載因子和擴(kuò)容臨界值，最后調(diào)用tableSizeFor方法來計(jì)算擴(kuò)容臨界值
4）根據(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 <0) ?1 : (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倍。
假設(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ù)挠乳。
5）hash方法
static 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)算中马靠。
下面圖說明：
6）插入方法? ?putVal
final V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict) {
????Node<K,V>[] tab; Node<K,V> p;int n, i;??//存儲(chǔ)Node節(jié)點(diǎn)的數(shù)組tab,單個(gè)Node節(jié)點(diǎn)p,HashMap的容量n
????if ((tab =table) ==null || (n = tab.length) ==0)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//初始化數(shù)組桶table （首次進(jìn)入初始化）
????????n = (tab = resize()).length;
????if ((p = tab[i = (n -1) & hash]) ==null)? ?????//如果數(shù)組桶中不包含要插入的元素，將新鍵值對(duì)作為新Node存入數(shù)組（當(dāng)前tab中無沖突元素）
????????tab[i] = newNode(hash, key, value,null);
????else {? ?????????????????????????????????????????????????????????????????????????????????????????????????????//桶中包含要插入的元素（tab中已有元素蔼两，發(fā)生沖突）
????????Node<K,V> e;K k;? ? ? ? ? //e用來保存當(dāng)前key已存在時(shí)的節(jié)點(diǎn)
????????if (p.hash == hash &&((k = p.key) == key || (key !=null && key.equals(k))))? ??//如果key和鏈表第一個(gè)元素p的key相等
????????????e = p;
????????else if (pinstanceof TreeNode)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???//若p是TreeNode類型甩鳄，則使用紅黑樹的方法插入到樹中
????????????e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
????????else {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//鍵值對(duì)的引用不在鏈表的第一個(gè)節(jié)點(diǎn)，此時(shí)需要遍歷鏈表
????????????for (int binCount =0; ; ++binCount) {
????????????????if ((e = p.next) ==null) {? ? ? ? ? ? ? //將p.next指向e额划，并判斷p是否為最后一個(gè)節(jié)點(diǎn)妙啃，若是插入新節(jié)點(diǎn)，此時(shí)e==null
????????????????????p.next = newNode(hash, key, value,null);
????????????????????if (binCount >=TREEIFY_THRESHOLD -1)// -1 for 1st? ?俊戳，若鏈表長(zhǎng)度大于等于8揖赴，變紅黑樹，退出遍歷
? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
????????????????????break;
????????????????}
????????????????if (e.hash == hash &&((k = e.key) == key || (key !=null && key.equals(k))))? ?//找到與當(dāng)前key值相同的節(jié)點(diǎn)
????????????????????break;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //退出遍歷（此時(shí)抑胎，e指向與當(dāng)前key值相同的舊節(jié)點(diǎn)）
????????????????p = e;? ?????????????????????//將e指向p,便于下次遍歷e = p.next
????????????}
????????}
????????if (e !=null) {// existing mapping for key? ? ??當(dāng)e非空時(shí)燥滑，說明e是原來HashMap中的元素，具有和新節(jié)點(diǎn)一樣的key值
? ? ? ? ? ? V oldValue = e.value;
????????????if (!onlyIfAbsent || oldValue ==null)? ? ?????//onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對(duì)的值
????????????????e.value = value;
????????????afterNodeAccess(e);? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//空實(shí)現(xiàn)圆恤，LinkedHashMap用
????????????return oldValue;
????????}
????}
????++modCount;????????????????????????????????????????//HashMap結(jié)構(gòu)更改突倍，modCount+1
????if (++size >threshold)????????????????????????????//判斷是否需要擴(kuò)容
????????resize();
????afterNodeInsertion(evict);? ? ? ? ? ? ? ? ? ? ?//空實(shí)現(xiàn)，LinkedHashMap用
????return null;
}
HashMap中進(jìn)行存儲(chǔ)的入口方法是：put（K盆昙，V）羽历，但是核心方法是putVal方法，該方法一共有以下步驟：
1.初始化數(shù)組桶
2.判斷數(shù)組桶中對(duì)應(yīng)下標(biāo)是否無元素存在淡喜，是秕磷，就直接存入
3.若數(shù)組桶中對(duì)應(yīng)下標(biāo)有元素存在，則開始遍歷炼团，根據(jù)長(zhǎng)度將元素存入鏈表尾部或樹中澎嚣。
4.判斷是否需要擴(kuò)容
7）擴(kuò)容方法? ?resize
? final Node[] resize() {
????Node[] oldTab =table;
????int oldCap = (oldTab ==null) ?0 : oldTab.length;? ? ? ? ? ? ?//原HashMap的容量
????int oldThr =threshold;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//原HashMap的擴(kuò)容臨界值
????int newCap, newThr =0;
????if (oldCap >0) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//case1 : odlCap>0,說明桶數(shù)組已經(jīng)初始化過
????????if (oldCap >=MAXIMUM_CAPACITY) {??//原HashMap的越界檢查
????????????threshold = Integer.MAX_VALUE;
????????????return oldTab;
????????}
????????else if ((newCap = oldCap <<1) <?MAXIMUM_CAPACITY &&? oldCap >=DEFAULT_INITIAL_CAPACITY)? ??//容量擴(kuò)大一倍后的越界檢查
????????????newThr = oldThr <<1;// double threshold
? ? }
????????//case2：oldCap=0 && oldThr >0，桶數(shù)組尚未初始化,當(dāng)調(diào)用帶初始化容量的構(gòu)造函數(shù)時(shí)會(huì)發(fā)生該情況
????else if (oldThr >0)// initial capacity was placed in threshold??
? ? ? ? newCap = oldThr;??????//在前面HashMap的初始化中瘟芝，將Initial capcity暫存在threshold中,新的閥值按照下面newThr==0中的公式進(jìn)行計(jì)算
????????//case3：oldCap=0 && oldThr = 0易桃，當(dāng)調(diào)用無參構(gòu)造函數(shù)時(shí)會(huì)發(fā)生該情況，此時(shí)使用默認(rèn)容量初始化
????else {// zero initial threshold signifies using defaults
? ? ? ? newCap =DEFAULT_INITIAL_CAPACITY;??//默認(rèn)容量
????????newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY);??//默認(rèn)擴(kuò)容臨界值
????}
????if (newThr ==0) {? ? //case2中锌俱，調(diào)用Initial capcity構(gòu)造方法時(shí)晤郑，該閥值為0，需計(jì)算閥值
????????float ft = (float)newCap *loadFactor;
????????newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 35(int)ft : Integer.MAX_VALUE);
????}
????threshold = newThr;
????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[] newTab = (Node[])new Node[newCap];??//上面獲取到的新的Capcity贸宏，來創(chuàng)建一個(gè)新的桶數(shù)組 newTab造寝，并指向table
????table = newTab;
????if (oldTab !=null) {? ??//若oldTab非空，則需要將原來桶數(shù)組的元素取出來放到新的桶數(shù)組中
????????for (int j =0; j < oldCap; ++j) {
????????????Node e;
????????????if ((e = oldTab[j]) !=null) {
????????????????oldTab[j] =null;? ??//將原桶數(shù)組的元素占用的空間釋放吭练，便于GC
????????????????if (e.next ==null)? ?//若桶中元素的next為空诫龙，獲取index后直接將其放入新桶數(shù)組中
????????????????????newTab[e.hash & (newCap -1)] = e;
? ? ? ? ? ? ? ? else if (einstanceof TreeNode)? ?//若桶中元素的next是樹節(jié)點(diǎn)
????????????????????((TreeNode)e).split(this, newTab, j, oldCap);? ??//采用樹的方式插入
????????????????else {// preserve order? ? ? ? ??若桶中元素的next是鏈表節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? Node loHead =null, loTail =null;
????????????????????Node hiHead =null, hiTail =null;
????????????????????Node next;
? ? ? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? ? ? ? next = e.next;
? ? ? ? ? ? ? ? ? ? ? ? ? if ((e.hash & oldCap) ==0) {? ??//若e.e.hash & oldCap 結(jié)果為0，則下標(biāo)在新桶數(shù)組中不用改變，此時(shí)，將元素存放在loHead為首的鏈表中
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (loTail ==null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ?else {? ? ? ? ? ? ? ? ? ? ? ? //若e.e.hash & oldCap 結(jié)果不為0赖瞒，則下標(biāo)在新桶數(shù)組等于原下標(biāo)+oldCap崖媚，此時(shí)，將元素存放在hiHead為首的鏈表中
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (hiTail ==null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?hiHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?hiTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ?}while ((e = next) !=null);
? ? ? ? ? ? ? ? ? ? ? ? ?if (loTail !=null) {? ? ? //將小于原來容量的頭節(jié)點(diǎn)放入原來數(shù)組中位置
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?loTail.next =null;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?newTab[j] = loHead;
? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ?if (hiTail !=null) {? ? ??//將大于原來容量的頭節(jié)點(diǎn)放入（原來數(shù)組+擴(kuò)容大星诳）中位置
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?hiTail.next =null;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?newTab[j + oldCap] = hiHead;
? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ?return newTab;
}
/*原始鏈表中的元素，在resize之后，其下標(biāo)有兩種可能括丁，一種是在原來下標(biāo)處，另一種是原來下標(biāo)+oldCap處?
?*舉例說明： 若原來的容量 -1后 只有n位伶选，低位有n個(gè)1史飞，去下標(biāo)公式為：i = (oldCap - 1) & hash，若hash值只有低n為有值仰税，則與運(yùn)算后獲得的值和?
?*擴(kuò)容前是一樣的构资，若hash不止第n位有值，那采用與運(yùn)算后陨簇，結(jié)果比原來剛好大oldCap吐绵。 下面有圖片示例）?
*/
上述代碼分析較長(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ù)組
8）查找元素方法 getNode
final Node getNode(int hash, Object key) {
????Node[] tab; Node first, e;int n;K k;
????if ((tab =table) !=null && (n = tab.length) >0 && (first = tab[(n -1) & hash]) !=null) {? ??//根據(jù)hash值唉窃，獲取對(duì)應(yīng)下標(biāo)的第一個(gè)元素first
????????if (first.hash == hash && ((k = first.key) == key || (key !=null && key.equals(k))))// always check first node? 如果first的key和待查詢的key相等，返回first
????????????return first;
????????if ((e = first.next) !=null) {? ?//若first不是待查詢的元素
????????????if (firstinstanceof TreeNode)? ??//若first是樹節(jié)點(diǎn)纹笼，采用樹節(jié)點(diǎn)的方式獲取
????????????????return ((TreeNode)first).getTreeNode(hash, key);
????????????do {
????????????????if (e.hash == hash && ((k = e.key) == key || (key !=null && key.equals(k))))? ?//first是鏈表節(jié)點(diǎn)頭纹份，使用循環(huán)獲取
????????????????????return e;
????????????}while ((e = e.next) !=null);
????????}
????}
????return null;
}
查詢?cè)氐娜肟诜椒ㄊ牵簆ublic V get(Object key)，返回值是node的value廷痘，核心方法是getNode(int hash, Object key)蔓涧。
9）刪除元素 removeNode方法
final Node removeNode(int hash, Object key, Object value,?boolean matchValue,boolean movable) {
????Node[] tab; Node p;int n, index;
????//通過hash值獲取下標(biāo)，下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)p不為空
????if ((tab =table) !=null && (n = tab.length) >0 && (p = tab[index = (n -1) & hash]) !=null) {?
????????Node node =null, e;K k;V v;
????????if (p.hash == hash && ((k = p.key) == key || (key !=null && key.equals(k))))? ??//若節(jié)點(diǎn)p的key和待移除的節(jié)點(diǎn)key相等
????????????node = p;? ?//將p指向待移除節(jié)點(diǎn)
????????else if ((e = p.next) !=null) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//p的key和待移除的節(jié)點(diǎn)key不相等笋额，遍歷p作為頭的鏈表或者樹
????????????if (pinstanceof TreeNode)? ? ? ? ? ? ? ?//采用樹節(jié)點(diǎn)方式獲得要移除的節(jié)點(diǎn)
????????????????node = ((TreeNode)p).getTreeNode(hash, key);
????????????else {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//p是鏈表的頭節(jié)點(diǎn)
????????????????do {
? ? ? ? ? ? ? ? ? ? //采用循環(huán)元暴，當(dāng)p.next不為空，比對(duì)它和傳入的key兄猩，直到找到相等的key
????????????????????if (e.hash == hash && ((k = e.key) == key || (key !=null && key.equals(k)))) {
????????????????????????node = e;? ?//找到后昨寞，將節(jié)點(diǎn)指向node
????????????????????????break;? ? ? ?//將e指向待移除節(jié)點(diǎn)，此時(shí)相當(dāng)于p.next就是待移除的節(jié)點(diǎn)node
? ? ? ? ? ? ? ? ????}
????????????????????p = e;
????????????????}while ((e = e.next) !=null);
????????????}
????????}
????????//若node非空厦滤，傳入的matchValue參數(shù)為flase或 node的value等于傳入value
????????if (node !=null && (!matchValue || (v = node.value) == value || (value !=null && value.equals(v)))) {
????????????if (nodeinstanceof TreeNode)? ? ??//若node是樹節(jié)點(diǎn)
????????????????((TreeNode)node).removeTreeNode(this, tab, movable);
????????????else if (node == p)? ? ??//若待移除節(jié)點(diǎn)是鏈表頭援岩，將其指向待移除元素的next，移除對(duì)node的引用
????????????????tab[index] = node.next;
????????????else? ? ? ? ? ? ? ? ? ? ? ? ? ?//待移除元素是鏈表中的元素掏导，此時(shí)其等于p.next
? ? ? ? ? ? ? ? p.next = node.next;? ? ? ? ? ? ?//將p.next指向node.next享怀，移除了對(duì)node的引用
????????????++modCount;?
????????????--size;
????????????afterNodeRemoval(node);
????????????return node;
????????}
????}
????return null;
}
移除節(jié)點(diǎn)的入口方法是：?public V remove(Object key)? ，其核心方法是removeNode趟咆，主要做了以下幾個(gè)工作：
1.通過用key獲取的hash添瓷，來獲取下標(biāo)。
2.若下標(biāo)對(duì)應(yīng)處無元素值纱，返回null鳞贷。
3.若下標(biāo)對(duì)應(yīng)處有元素，判斷是樹或者鏈表虐唠，采用對(duì)應(yīng)方法移除搀愧。
3.常見問題
3.1HashMap的容量為什么必須是2的n次冪？
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)?&"運(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)
綜上:? 當(dāng)容量是2的n次冪時(shí)辆亏，不同的key獲取在桶數(shù)組中的下標(biāo)相同的概率減小风秤，發(fā)生Hash碰撞幾率減少，元素分布更加均勻扮叨，見下圖缤弦。
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.5HashMap 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)
摘自：https://www.cnblogs.com/LearnAndGet/p/9971526.html
