1.概述

HashMap是日常java開發(fā)中常用的類之一蚜迅，是java設(shè)計中非常經(jīng)典的一個類，它巧妙的設(shè)計思想與實(shí)現(xiàn)俊抵，還有涉及到的數(shù)據(jù)結(jié)構(gòu)和算法，埃碱，值得我們?nèi)ド钊氲膶W(xué)習(xí)锅纺。

簡單來說劝萤，HashMap就是一個散列表，是基于哈希表的Map接口實(shí)現(xiàn)谎替，它存儲的內(nèi)容是鍵值對 (key-value) 映射，并且鍵值允許為null(鍵的話只允許一個為null)蹋辅。

1.1 注意事項(xiàng)

①根據(jù)鍵的hashCode存儲數(shù)據(jù)钱贯。(String，和Integer侦另、Long秩命、Double這樣的包裝類都重寫了hashCode方法，String比較特殊根據(jù)ascil碼還有自己的算法計算袄友，Double做位移運(yùn)算【具體看源碼的hashcode實(shí)現(xiàn)】霹菊，Integer，Long包裝類則是自身大小int值)鸠按，
HashMap中的結(jié)構(gòu)不能有基本類型，一方面是基本類型沒有hashCode方法饶碘，還有HashMap是泛型結(jié)構(gòu)熊镣，泛型要求包容對象類型绪囱，而基本類型在java中不屬于對象鬼吵。
②HashMap的存儲單位是Node<k,v>,可以認(rèn)作為節(jié)點(diǎn)齿椅。
③Hashmap中的擴(kuò)容的個數(shù)是針對size(內(nèi)部元素(節(jié)點(diǎn))總個數(shù))涣脚，而不是數(shù)組的個數(shù)矾麻。比如說初始容量為16险耀，第十三個節(jié)點(diǎn)put進(jìn)來甩牺，不管前面十二個占的數(shù)組位置如何贬派，就開始擴(kuò)容赠群。

1.2 hashmap幾個特征

2.一些概念

2.1.位運(yùn)算

位運(yùn)算是對整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作谢肾。

在java中 >> 表示右移 若該數(shù)為正，則高位補(bǔ)0，若為負(fù)數(shù)柒桑，高位補(bǔ)1

<<表示左移 跟右移相反 如果是正數(shù)在低位補(bǔ)0

例如20的二進(jìn)制為0001 0100 20>>2為 結(jié)果為5(0000 0101) (左高右低)

20<<2 為 0101 0000 則為80

java中>>>和>>的區(qū)別

>>>表示無符號右移飘诗，也叫邏輯右移昆稿。不管數(shù)字是正數(shù)還是負(fù)數(shù)，高位都是補(bǔ)0

在hashMap源碼中有很多使用位運(yùn)算的地方喳瓣。例如:

//之所以用1 << 4不直接用16畏陕，0000 0001 -> 0001 0000 則為16，如果用16的話最后其實(shí)也是要轉(zhuǎn)換成0和1這樣的二進(jìn)制鞠绰，位運(yùn)算的計算在計算機(jī)中是非扯椿恚快的，直接用位運(yùn)算表示大小以二進(jìn)制形式去運(yùn)行曙咽，在jvm中效率更高。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  //初始化容量

注意:左移沒有<<<運(yùn)算符

2.2 位運(yùn)算符-(與(&)洒嗤、非(~)、,或(|)间唉、異或(^))

①與運(yùn)算(&)

我們都知道&在java中表示與操作&表示按位與呈野，這里的位是指二進(jìn)制位军掂。都為1才為真(1),否則結(jié)果為0良姆，舉個簡單的例子

System.out.println(9 & 8); //1&1=1，1&0 0&1 0&0都=0痊剖，因此1001 1000 -> 1000 輸出為8

②非運(yùn)算(~)

源碼 -> 取反 -> 反碼 -> 加1 -> 補(bǔ)碼 -> 取反 -> 按位非值

在Java中，所有數(shù)據(jù)的表示方法都是以補(bǔ)碼的形式表示叮贩，如果沒有特殊說明，Java中的數(shù)據(jù)類型默認(rèn)是int,int數(shù)據(jù)類型的長度是8位捺萌，一位是四個字節(jié)，就是32字節(jié)态坦，32bit.

例如5的二進(jìn)制為0101

補(bǔ)碼后為 00000000 00000000 00000000 00000101

取反后為 11111111 11111111 11111111 11111010

【因?yàn)楦呶粸? 所以源碼為負(fù)數(shù)伞梯，負(fù)數(shù)的補(bǔ)碼是其絕對值源碼取反，末尾再加1】

所以反著來末尾減1得到反碼然后再取負(fù)數(shù)

末位減1：11111111 11111111 11111111 11111001

【后八位前面4位不動 后面 減1 1010減1 相當(dāng)于 10-1為9 后四位就是 1001 】

取反后再負(fù)數(shù)： 00000000 00000000 00000000 00000110 為-6

System.out.println(~ 5); //輸出-6

③或運(yùn)算(|)

只要有一個為1，結(jié)果為1掰邢，否則都為0

System.out.println(5 | 15); //輸出為15辣之，0101或上1111,結(jié)果為1111

④異或運(yùn)算(^)

相同為0(假)，不同為真(1)

System.out.println(5 ^ 15); //輸出10 0101異或1111結(jié)果為1010

2.3 hashcode

hash意為散列，hashcode是jdk根據(jù)對象的地址或者字符串或者數(shù)字算出來的int類型的數(shù)值康铭，頂級父類Object類中含hashCode方法(native本地方法从藤，是根據(jù)地址來計算值)，有一些類會重寫該方法扫责，比如String類。

重寫的原因苏揣。為了保證一致性，如果對象的equals方法被重寫增炭，那么對象的hashcode()也盡量重寫梅垄。

簡單來說 就是hashcode()和equals()需保持一致性，如果equals方法返回true机久，那么兩個對象的hashCode 返回也必須一樣。

否則可能會出現(xiàn)這種情況衔憨。

假設(shè)一個類重寫了equals方法，其相等條件為屬性相等就返回true码党，如果不重寫hashcode方法，那么依據(jù)就是Object的依據(jù)比較兩個對象內(nèi)存地址，則必然不相等箕慧，這就出現(xiàn)了equals方法相等但是hashcode不等的情況，這不符合hashcode的規(guī)則伐庭，這種情況可能會導(dǎo)致一系列的問題霸株。

因此，在hashMap中，key如果使用了自定義的類，最好要合理的重寫Object類的equals和hashcode方法渡嚣。

2.4 哈希桶

哈希桶的概念比較模糊，個人理解是數(shù)組表中一塊區(qū)域結(jié)果下面的單向鏈表組成的腹鹉，在hashmap中，這個單向鏈表的頭部是所在數(shù)組上第一個元素，單向鏈表如果過長超過8景殷，那么這個"桶"就可能變成了紅黑樹(前提是數(shù)組長度達(dá)到64）。

2.5 hash函數(shù)

在程序設(shè)定中亭饵，把一個對象通過某種算法或者說轉(zhuǎn)換機(jī)制對應(yīng)到一個整形踏兜。

主要用于解決沖突的。

2.6 哈希表

也稱為散列表疹尾，這也是一種數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)對象產(chǎn)生一個為整數(shù)的散列碼(hashCode)。

hash沖突

HashMap之所以有那么快的查詢速度巾腕，是因?yàn)樗牡讓邮怯蓴?shù)組實(shí)現(xiàn)，通過key計算散列碼(hashCode)決定存儲的位置，HashMap中通過key的hashCode來計算hash值狗准，只要hashCode相同，hash值也一樣，但是可能存在存的對象多了鸟召，不同對象計算出的hash值相同仆抵，這就是hash沖突。

舉個例子

HashMap<String,String> map = new HashMap<String,String>();
map.put("Aa", "haha");
map.put("BB","heihei");
System.out.println("Aa".hashCode()); //2112
System.out.println("BB".hashCode()); //2112
//這里的Aa和BB為String型，String類重寫了hashCode方法(根據(jù)ascil碼和特定的算法來計算，雖然很巧妙但也難以避免不對對象hashCode相同的情況)旱物，Aa和BB的hashCode值相同，相同的HashCode的hash值相同 
//根據(jù)源碼就算key不相同 但key.hashCode()相同 則會返回相同的hash封孙，導(dǎo)致hash沖突
static final int hash(Object key) {//取關(guān)鍵key的hash值
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//任何小于2的16次方的數(shù) 右移16位都為0 2的16次方>>>16剛好為1 任何一個數(shù)和0按位異或都為這個數(shù)本身(1和0為1 0和0為0)泡徙，所以這個hash()函數(shù)對于null的hash值 僅在hashcode大于2的16次方才會調(diào)整值,這邊16設(shè)計的很巧妙挑围，因?yàn)閕nt剛好是32位的取中間位數(shù)
}

2.7 二叉查找樹和紅黑樹

紅黑樹是一種自平衡二叉查找樹模捂。是一種數(shù)據(jù)結(jié)構(gòu)狂男，又稱二叉b樹，（→_→ 2b樹泡垃？），紅黑樹本質(zhì)上也是二叉查找樹锡溯。所以先理解下二叉查找樹祭饭。

2.7.1二叉查找樹

二叉查找樹，又稱有序二叉樹叙量，已排序二叉樹
它的三大特點(diǎn)如下
1.左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值倡蝙。
2.右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值。
3.左绞佩、右子樹也分別為二叉排序樹。

二叉樹.png

2.7.2 紅黑樹(RBTree)

由于二叉查找樹可能存在難以平衡呈線性的缺陷品山，所以出現(xiàn)的紅黑樹的概念胆建。顧名思義，紅黑樹是只有紅色和黑色節(jié)點(diǎn)的二叉樹肘交。
它的5大性質(zhì)如下笆载。
1.節(jié)點(diǎn)是紅色或黑色。
2.根節(jié)點(diǎn)是黑色涯呻。
3.每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）凉驻。
4 每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn))
5.從任一節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)复罐。

簡單來說紅黑樹是一種自平衡二叉查找樹涝登，相比于普通的二叉查找樹，它的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜效诅，但是在復(fù)雜的情況也能通過自平衡(變色缀拭，左右旋轉(zhuǎn))保持良好的性能。

關(guān)于紅黑樹填帽，很形象的一組漫畫蛛淋，查看這里

在線模擬紅黑樹增刪的地址地址1、 地址2

紅黑樹的時間復(fù)雜度為【吐槽下簡書這邊如果用數(shù)學(xué)公式太蛋疼了】：

O(logn)

它的高度為:[logN,logN+1]（理論上篡腌，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2logN褐荷，但實(shí)際上很難遇到）。*

此外嘹悼，由于它的設(shè)計任何不平衡將在三次旋轉(zhuǎn)內(nèi)解決叛甫。

紅黑樹和avl樹(最早的自平衡二叉樹)的比較：
avl更加平衡层宫，查詢速率稍強(qiáng)于紅黑樹，但是插入和刪除紅黑樹完爆avl樹其监，可能由于hashMap的增刪也挺頻繁的萌腿，所以綜合考慮而選擇紅黑樹。

總結(jié)：紅黑樹是種可以通過變色旋轉(zhuǎn)的自平衡二叉查找樹抖苦，對于hashMap來說毁菱，使用紅黑樹的好處在于，當(dāng)有多個元素hash相同在同一數(shù)組下標(biāo)的時候锌历，使用紅黑樹在查找這些hash沖突的元素更快贮庞，它的時間復(fù)雜度從遍歷鏈表O(n)降到O(logN)。

2.8 復(fù)雜度

算法復(fù)雜度分時間復(fù)雜度和空間復(fù)雜度究西。

時間復(fù)雜度：執(zhí)行算法所需要的計算工作量
空間復(fù)雜度：執(zhí)行算法所需要內(nèi)存空間大小
時間和空間都是計算機(jī)資源的體現(xiàn)窗慎，算法的復(fù)雜性體現(xiàn)在運(yùn)行該算法時計算機(jī)所需資源的大小。

這里重點(diǎn)講下時間復(fù)雜度

(1)時間頻度
用T(n)表示
一個算法執(zhí)行所消耗的時間卤材，理論上不能算出來而是通過運(yùn)行測試得知遮斥，但不可能也沒必要對每個算法都做上機(jī)測試，只需知道哪個算法花費(fèi)時間多哪個花費(fèi)少即可扇丛。在算法中一個算法花費(fèi)的時間和這個算法執(zhí)行的次數(shù)成正比术吗。
在一個算法中，語句執(zhí)行次數(shù)稱為時間頻度(或稱為語句頻度)晕拆，記做為T(n)，這里的n代表問題的規(guī)模材蹬。暫且不考慮這個T是啥实幕，把它理解為一個函數(shù)。
(2)時間復(fù)雜度 
用Ｏ(f(n))表示
當(dāng)n變化時堤器，時間頻度T(n)也會不斷變化昆庇，但是它是個不確定的函數(shù)，我們想知道它呈現(xiàn)的規(guī)律是什么樣的闸溃。這個時候引入了時間復(fù)雜度的概念整吆。
前面說T(n)是個不確定的函數(shù)，它代表算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)辉川。
假設(shè)有某個輔助函數(shù)f(n),當(dāng)n趨近∞表蝙，T(n)/f(n)的極限值不為0切位常數(shù)，那么可以認(rèn)為f(n)和T(n)為同一數(shù)量級的函數(shù)乓旗，記做為T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時間復(fù)雜度府蛇，簡稱時間復(fù)雜度。

f(n)雖然沒有規(guī)定但一般都盡可能取簡單的函數(shù)
例如 O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) 省去了系數(shù),只保留最高階項(xiàng)屿愚。
時間頻度不同時汇跨，時間復(fù)雜度有可能相同务荆，例如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同穷遂，都為O(n2)函匕。

總結(jié)兩者關(guān)系:時間復(fù)雜度就是對時間頻度函數(shù)的一層包裝，它的特點(diǎn)(大O表示法)為
①省去系數(shù)為1處理②保留最高項(xiàng)
如果把T(n)當(dāng)做為一棵樹蚪黑，那么O(f(n))只關(guān)心其主干部分盅惜。

常見算法的時間復(fù)雜度從小到大依次為

復(fù)雜度比較

求解算法的時間復(fù)雜度具體步驟為：
①找出算法中執(zhí)行次數(shù)最多的基本語句，一般是最內(nèi)層的循環(huán)體祠锣。
②計算基本語句的數(shù)量級
③將基本語句執(zhí)行次數(shù)的數(shù)量級放入大O記號中

舉幾個例子

O(1),又稱常數(shù)階酷窥，一般來說算法中沒有循環(huán)體，執(zhí)行次數(shù)為常數(shù)那么時間復(fù)雜度就為O(1)伴网，例如

int sum = 0,n = 100; //執(zhí)行一次  
sum = (1+n)*n/2; //執(zhí)行一次  
System.out.println (sum); //執(zhí)行一次 
//上面的算法運(yùn)行次數(shù)為f(n)=3,那么根據(jù)大O表示法蓬推，該算法的時間復(fù)雜度為O(1)

為什么O(logN)，對數(shù)階不用底數(shù)

如紅黑樹的查找復(fù)雜為O(logN)

這里面有個可能存在的疑問澡腾，有時候時間復(fù)雜度都用包含O(logN)這樣的描述 但是沒有明確說明n的底數(shù)是多少沸伏，通常底數(shù)為2來計算

這種描述其實(shí)也是合理的，算法中l(wèi)og級別的時間復(fù)雜度都是由于使用了分治思想,這個底數(shù)直接由分治的復(fù)雜度決定动分。當(dāng)n趨近于無窮大毅糟，兩個大小比較也只是一個常數(shù)，所以這種時候O(logN)統(tǒng)一代表對數(shù)復(fù)雜度澜公。

其它簡單舉例

3. HashMap的內(nèi)部實(shí)現(xiàn)(基于jdk1.8)

剛開始看hashMap源碼的時候殷费，感覺思路很亂不知道寫的啥東西印荔，所以還是得從它的【數(shù)據(jù)結(jié)構(gòu)】開始入手。

不同于一般類的數(shù)據(jù)結(jié)構(gòu)详羡，從結(jié)構(gòu)來講 HashMap = 數(shù)組 + 鏈表 + 紅黑樹(1.8開始加入仍律，大程度的優(yōu)化了HashMap的性能)
arrayList  數(shù)組
linkedList 雙向鏈表 查詢效率慢，需通過遍歷实柠，新增或刪除快染苛，比如說刪除一個元素 知道那個元素的上下引用 并改變關(guān)聯(lián)上下元素的引用指向即可。

3.1 數(shù)組和鏈表

數(shù)組和鏈表.png

3.2 HashMap數(shù)據(jù)結(jié)構(gòu)(數(shù)組+鏈表+紅黑樹)

在jdk8以前，如果發(fā)生頻繁碰撞的話茶行，查找時間復(fù)雜度是O(1) + O(n) (先找在數(shù)組的位置再找鏈表)躯概，n如果比較大則嚴(yán)重影響了查找性能，而到了jdk8引入紅黑樹,O(1) + O(logN)畔师。

hashmap.png

大致思路

①數(shù)組的優(yōu)點(diǎn)是查詢快娶靡，鏈表的優(yōu)點(diǎn)是增刪快，紅黑樹查詢性能較好看锉，hashMap的存儲方式結(jié)合了它們的優(yōu)點(diǎn)姿锭，那么hashMap的存儲單元又可以在數(shù)組里，又可以在某個數(shù)組下的鏈表里伯铣。還有可能在紅黑樹當(dāng)中呻此。
②我們已經(jīng)知道HashMap是鍵值對的存在，且可以為各種類型腔寡，那么它又是以鍵值對的方式存在焚鲜，它的最小存儲單位是以Node節(jié)點(diǎn)為存儲單位。
這個Node結(jié)構(gòu)大概有Key放前，Value忿磅，記錄所在數(shù)組索引，以及記錄鏈表指針的東西凭语。
大概結(jié)構(gòu)如下
static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
  ...
}

③新來的Node節(jié)點(diǎn)怎么放?
HashMap利用hashcode來確定存放的位置葱她，但是又有個疑問，假設(shè)map對象key為String型
HashMap<String, String> map = new HashMap<String, String>();
map.put("1", "first");

//這個時候看put方法 
put方法的大致思路為
①對key做hash運(yùn)算似扔，通過hash值計算index下標(biāo)位置
②如果沒沖突直接放在桶上
③如果沖突了吨些，以鏈表的形式存在桶里面，達(dá)到一定條件鏈表變?yōu)榧t黑樹
④如果節(jié)點(diǎn)已經(jīng)存在炒辉，則替換舊的value(保證唯一性)
⑤如果桶的個數(shù)超過了 加載因子乘當(dāng)前容量豪墅，則做resize操作

//可以注意到有個hash函數(shù)
public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
}

//hash函數(shù) 
static final int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//上述代碼String類型的1的Hashcode為49超過了HashMap的初始長度16，這個時候"1"這個key放在哪辆脸。這里
//通過巧妙的設(shè)計存放在合適的位置 4.3.3做分析
p = tab[i = (n - 1) & hash]但校，


//這里的p為Node<K,V>對象螃诅，n為當(dāng)前哈希桶數(shù)組長度啡氢，進(jìn)行與運(yùn)算后，因?yàn)檫@是第一個插入的元素术裸，無需擴(kuò)容長度為16,那么49 & 15 = 1倘是，說明在的第二個位置厕鹃。

④新節(jié)點(diǎn)插入后什么時候開始擴(kuò)容
接下來不斷的插入的元素 經(jīng)過hash函數(shù)和計算索引位置后随闪，都可以根據(jù)它的散列性插入到不同的16個位置，
當(dāng)元素個數(shù)達(dá)到16 * 0.75 即12時秒梅，繼續(xù)插入新的時候，開始擴(kuò)容瘤睹。
【這里注意一下并不是說占滿12個位置才開始擴(kuò)容升敲，而是12個節(jié)點(diǎn)，根據(jù)散列性分布12個節(jié)點(diǎn)轰传，占...5驴党，6，7获茬，8...個位置都有可能,比如說key為Integer類型港庄，假如key為Integer類型，有五個節(jié)點(diǎn)key分別為3恕曲，19鹏氧，12，28佩谣，44這個時候3把还，19在同一個位置，12稿存，28笨篷，44在同一個位置，這個時候5個節(jié)點(diǎn)就占了兩個位置】


⑤resize()方法進(jìn)行擴(kuò)容操作瓣履。
1.先判斷節(jié)點(diǎn)數(shù)組是否為空率翅，并取它的容量(節(jié)點(diǎn)個數(shù))，創(chuàng)建新數(shù)組袖迎，大小時新的capacity
如果不為空：
如果容量超過最大值不做擴(kuò)容冕臭，否則位運(yùn)算一位做容量乘2處理，
如果為空：
桶數(shù)組容量為默認(rèn)容量16燕锥，即有默認(rèn)放16個桶辜贵，閾值默認(rèn)為默認(rèn)容量乘默認(rèn)加載因子 12
2.將舊數(shù)組的元素放到新數(shù)組中，重新做映射
如果舊的數(shù)組不為空归形，則遍歷桶數(shù)組托慨，并將鍵值對映射到新的桶數(shù)組中[樹節(jié)點(diǎn)和鏈表節(jié)點(diǎn)做不同操作]

4.源碼分析

4.1 基本存儲單位Node節(jié)點(diǎn)

static class Node<K,V> implements Map.Entry<K,V> { //實(shí)現(xiàn)Entry接口 存儲的是鍵值對的映射
    final int hash; //hash值，用于記錄數(shù)組所在位置
    final K key; //用于匹配
    V value; //值
    Node<K,V> next; //用于記錄單鏈表下一節(jié)點(diǎn) 用于解決hash沖突(即hash值一樣該存在哪里的問題)
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {//賦值
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

4.2 HashMap中的幾個重要實(shí)現(xiàn)：hash函數(shù)暇榴，put厚棵、get、resize

//put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //哈希表數(shù)組節(jié)點(diǎn) 
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果為空 調(diào)用resize以默認(rèn)大小16擴(kuò)容 
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //通過(n - 1) & hash計算存放索引位置 此處設(shè)計很巧妙
    if ((p = tab[i = (n - 1) & hash]) == null)
      //如果tab[i]為空 該下標(biāo)下沒有節(jié)點(diǎn) 則直接新建一個Node放在該位置 
        tab[i] = newNode(hash, key, value, null);
    else {
        //下標(biāo)上有節(jié)點(diǎn) 說明有hash沖突
        Node<K,V> e; K k;
        //如果插入的新節(jié)點(diǎn)key已經(jīng)存在蔼紧，那么直接覆蓋整個節(jié)點(diǎn)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果為紅黑樹節(jié)點(diǎn)
        else if (p instanceof TreeNode)
            //調(diào)用紅黑樹插入鍵值對的putTreeVal方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //不管tab[index]是否為空婆硬，p節(jié)點(diǎn)已經(jīng)為 tab[index]上
            //如果有沖突 且不為紅黑樹節(jié)點(diǎn) 那么此時遍歷鏈表節(jié)點(diǎn) binCount計算鏈表長度
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                   //鏈表長度大于8，調(diào)用treeifyBin對鏈表進(jìn)行樹化 -1為第一個
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //遍歷鏈表時發(fā)現(xiàn)重復(fù) 覆蓋并跳出循環(huán)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //插入成功后 再根據(jù)實(shí)際判斷是否到到閾值 比如說現(xiàn)在容量16(桶的個數(shù)16) 正在插第13個元素時 到達(dá)則擴(kuò)容 
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //先定位鍵值對在所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                //如果是紅黑樹節(jié)點(diǎn) 通過紅黑樹查找方法查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //對鏈表查找
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

4.4.5 resize()

擴(kuò)容就是重新定義容量奸例，在hashmap中彬犯，如果不斷的put元素，而hashMap對象中的數(shù)組無法裝得下更多對象時，對象就需要進(jìn)行擴(kuò)容谐区，擴(kuò)大數(shù)組長度湖蜕。這邊注意的是：

①假如初始大小為默認(rèn)值16，什么時候擴(kuò)容宋列，我們可以知道閾值是160.75即12重荠，這個12是指hashMap的size(全局變量，每次put+1.remove-1)虚茶，put后為大于12即13時開始執(zhí)行resize方法擴(kuò)容戈鲁。*

②在java中數(shù)組是不能夠自動擴(kuò)容的，是采用一個新的大容量數(shù)組代替原有的小數(shù)組嘹叫，就好比用一個小桶裝水婆殿，如果想用一個桶裝更多的水，就換一個大桶再把原來小桶的水裝過去罩扇。

③擴(kuò)容后婆芦，普通鏈表上的節(jié)點(diǎn)包括紅黑樹都得重新映射。

對于hashmap來說
什么時候換大桶：達(dá)到閾值的時候
換多大的桶：原有小桶的兩倍大小
但桶的大小也是有限的喂饥，對于hashMap消约，最大的桶能容納包含2^30個數(shù)，大于的話就不再擴(kuò)容员帮，就隨里面碰撞了或粮。(實(shí)際上也很難用到這么大的容量)

final Node<K,V>[] resize() {
    //table為全局變量transient Node<K,V>[] table; 賦值給oldTab
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//舊表數(shù)組個數(shù)
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { //如果舊容量大于0    
        //超過最大值就不擴(kuò)容了，隨它碰撞去吧 -捞高。-
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //×2還沒超過最大值氯材，新數(shù)組就擴(kuò)容為原來兩倍 閾值也做×2處理
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 
    }
    //如果原來的閾值 > 0且舊容量為0，則將新容量設(shè)為原來的閾值硝岗，初始化有參給threshold賦值會有此情況
    else if (oldThr > 0) 
        newCap = oldThr;
    else { // zero initial threshold signifies using defaults
        //默認(rèn)初始化無參構(gòu)造的情況 
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"}) //屏蔽無關(guān)緊要的警告
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //如果舊數(shù)組不為空 
    if (oldTab != null) {
        //遍歷數(shù)組
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //數(shù)組中的節(jié)點(diǎn)不為空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果該桶只有一個節(jié)點(diǎn)(說明下面沒有鏈表氢哮，或者說只有一個鏈表節(jié)點(diǎn))
                if (e.next == null)
                    //e.hash & (newCap - 1)確定元素存放位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //紅黑樹節(jié)點(diǎn)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    //鏈表節(jié)點(diǎn)且當(dāng)前鏈表節(jié)點(diǎn)不止1個
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //根據(jù)e.hash & oldCap 判斷節(jié)點(diǎn)存放位置
                        //如果為0 擴(kuò)容還在原來位置 如果為1 新的位置為 舊的index + oldCap 下面如何擴(kuò)容有做介紹
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);//舊鏈表遷移到新鏈表
                    if (loTail != null) {
                        loTail.next = null;//將鏈表的尾節(jié)點(diǎn)的next設(shè)置為空
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;// 將鏈表的尾節(jié)點(diǎn) 的next 設(shè)置為空
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

4.3 HashMap經(jīng)典代碼 p = tab[i = (n - 1) & hash])

p = tab[i = (n - 1) & hash])

當(dāng)hashCode小于65536，散列是很規(guī)律的型檀，基本上索引的位置就是

因?yàn)樾∮谶@個數(shù)右移16為都為0冗尤，且和占位符都為0的值異或后的hashcode就是自身的值。

這個值比較特殊

轉(zhuǎn)換為二進(jìn)制：00000000000000010000000000000000胀溺，右移16的話00000000000000000000000000000001并不全為0

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

key的hashcode為65536

轉(zhuǎn)為二進(jìn)制：h=key.hashCode() 00000000000000010000000000000000

跟右移16位的再做異或操作 00000000000000000000000000000001

hash = h ^(h>>>16) 00000000000000010000000000000001

?

計算hash 00000000000000010000000000000001

? 00000000000000000000000000001111

結(jié)果 1

但是65536 % 16 = 0

key的hashcode為17 異或相同為0 不同為假

轉(zhuǎn)為二進(jìn)制：h=key.hashCode() 00000000000000000000000000010001

跟右移16位的再做異或操作 00000000000000000000000000000000

hash = h ^(h>>16) 00000000000000000000000000010001

計算hash 00000000000000000000000000010001

? 00000000000000000000000000001111

? 00000000000000000000000000000001

做個小測試裂七，假設(shè)這個時候桶的個數(shù)為16，代碼如下

for (int key = 65533; key < 65543; key++) { //從65536開始變得有點(diǎn)"特別"
    System.out.println("key為：" + key +  "月幌，索引位置：" + ((key ^ (key >>> 16)) & 15));//假設(shè)初始容量為16 測試沒擴(kuò)容時這些數(shù)的索引位置
}
//輸出結(jié)果為碍讯，可以發(fā)現(xiàn)從65536開始不為0而是1悬蔽，有點(diǎn)特殊扯躺，然后相鄰兩個索引位置呈1,3的增長，具體可畫圖嘗試
i為：65533，輸出13
i為：65534录语，輸出14
i為：65535倍啥，輸出15
i為：65536，輸出1
i為：65537澎埠，輸出0
i為：65538虽缕，輸出3
i為：65539，輸出2
i為：65540蒲稳，輸出5
i為：65541氮趋，輸出4
i為：65542，輸出7

這段代碼主要是計算索引位置的江耀，HashMap 底層數(shù)組的長度總是 2 的 n 次方

當(dāng) length 總是 2 的倍數(shù)時剩胁，h& (length-1)，將是一個非常巧妙的設(shè)計：

可以看到計算得到的索引值總是位于 table 數(shù)組的索引之內(nèi)祥国。并且通常分布的比較均勻

4.4 樹形化treeifyBin()

在jdk8以前昵观，如果發(fā)生頻繁碰撞的話，查找時間復(fù)雜度是O(1) + O(n) (先找在數(shù)組的位置再找鏈表)舌稀，n如果比較大則嚴(yán)重影響了查找性能啊犬，而到了jdk8引入紅黑樹,O(1) + O(logN)。

jdk1.8中壁查，如果一個桶中元素個數(shù)超過TREEIFY_THRESHOLD(8)時觉至，就用紅黑樹替換鏈表以提升速度(主要是查找)

//將桶內(nèi)所有鏈表節(jié)點(diǎn)換成紅黑樹節(jié)點(diǎn)
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果當(dāng)前哈希表為空 或者哈希表中元素 MIN_TREEIFY_CAPACITY默認(rèn)為64，對于這個值可以認(rèn)為睡腿，如果節(jié)點(diǎn)數(shù)組長度小于64康谆，就沒必要去進(jìn)行結(jié)構(gòu)轉(zhuǎn)換，而是通過resize()操作嫉到，這樣原先一個鏈表的元素可能會進(jìn)行重新分配沃暗。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); //擴(kuò)容
    //大于等于64 就樹化 鏈表上的普通節(jié)點(diǎn)變成樹節(jié)點(diǎn)
    else if ((e = tab[index = (n - 1) & hash]) != null) {      
        TreeNode<K,V> hd = null, tl = null; //定義首、尾節(jié)點(diǎn)
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null); //普通節(jié)點(diǎn) -> 樹節(jié)點(diǎn)
            if (tl == null) //如果尾節(jié)點(diǎn)為空 說明還沒有根節(jié)點(diǎn)
                hd = p; //首節(jié)點(diǎn)(根節(jié)點(diǎn)) 指向當(dāng)前節(jié)點(diǎn)
            else { //尾節(jié)點(diǎn)不為空 
                p.prev = tl; //當(dāng)前樹節(jié)點(diǎn)前一個節(jié)點(diǎn)指向尾節(jié)點(diǎn)
                tl.next = p; //尾節(jié)點(diǎn)后一個節(jié)點(diǎn) 指向當(dāng)前節(jié)點(diǎn)
            }
            tl = p; 
        } while ((e = e.next) != null); //繼續(xù)遍歷鏈表
      
        //這個時候只是把Node對象變成TreeNode對象何恶，把單向鏈表變成雙向鏈表
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

5.思考

1.HashMap和HashTable的區(qū)別是什么

HashMap和Hashtable都實(shí)現(xiàn)了Map接口

HashMap功能上幾乎可以等價于Hashtable孽锥，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)细层，而Hashtable則不行)惜辑。
HashMap是非synchronized，而Hashtable是synchronized疫赎，這意味著Hashtable是線程安全的
由于Hashtable是線程安全的也是synchronized盛撑，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步捧搞，只需要單一線程抵卫，那么使用HashMap性能要好過Hashtable狮荔。
HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

由于性能問題介粘，以及HashTable處理Hash沖突比HashMap遜色很多殖氏，現(xiàn)在HashTable已經(jīng)很少使用了。但由于線程安全以及以前的項(xiàng)目還在使用姻采，SUN依然還保留著它并沒有加Deprecated過時注解雅采。

摘自hashtable源碼

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

簡單來說就是不需要線程安全，那么使用HashMap慨亲，如果需要線程安全婚瓜，那么使用ConcurrentHashMap。

2.HashMap為什么線程不安全刑棵，如果想要線程安全怎么做

因?yàn)閔ashmap為了性能闰渔，它的put，resize等操作都不是同步的铐望，假設(shè)兩個線程同一時間做put操作,可能最后計算的size并不正確冈涧，值得一提的是jdk1.8以前多線程put甚至?xí)?dǎo)致閉環(huán)死循環(huán)，1.8開始不會有這個問題但依然存在線程安全問題正蛙。

jdk8前的閉環(huán)死循環(huán)督弓。

這種問題在單線程下不存在，但在多線程下可能引起死循環(huán)導(dǎo)致cpu占用過高乒验。

如果hash沖突大愚隧，同一鏈表下下有多個節(jié)點(diǎn)容易出現(xiàn)這種問題。具體參考老生常談锻全，HashMap的死循環(huán)

若想要線程安全
1狂塘、使用ConcurrentHashMap。(線程安全的hashMap)
2鳄厌、使用Collections.synchronizedMap(Mao<K,V> m)方法把HashMap變成一個線程安全的Map荞胡。

3.HashMap是怎么解決Hash沖突的

在實(shí)際應(yīng)用中，無論怎么構(gòu)造哈希函數(shù)了嚎，沖突也難以完全避免泪漂。
HashMap根據(jù)鏈地址法(拉鏈法)來解決沖突,jdk8中如果鏈表長度大于8且節(jié)點(diǎn)數(shù)組長度大于64的時候，就把鏈表下所有節(jié)點(diǎn)轉(zhuǎn)為紅黑樹歪泳，位于數(shù)組上的節(jié)點(diǎn)為根節(jié)點(diǎn)萝勤，來維護(hù)hash沖突的元素，鏈表中沖突的元素可以通過key的equals()方法來確定呐伞。

4.HashMap是怎么擴(kuò)容的

先寫個例子測試hashMap有沒有在擴(kuò)容敌卓。

public static void main(String[] args) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
    HashMap<Integer,String> o = new HashMap<>(1);
    System.out.println(o.size()); //0 size為元素個數(shù)
    //擴(kuò)容條件是 如果沒有定義初始容量 默認(rèn)擴(kuò)容至16 如果沒有 根據(jù)put的情況擴(kuò)容
    //put的過程中 如果插入一個元素過后的size > 閾值(加載因子 * 最近容量)
    /**
     * 代碼體現(xiàn) put后執(zhí)行
     *   if (++size > threshold)
     *         resize();
     */
    //有定義容量的話會采用大于這個數(shù)的最小二次冪 第一次初始化為1 則輸出為2 4 5 11  111 11
    HashMap<Integer,String> map = new HashMap<>(1);
    map.put(1, "一");
    //由于方法由final修飾 利用反射機(jī)制獲取容量值
    Class<?> mapType = map.getClass();
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true); //由于capacity方法由final修飾 暴力獲取
    System.out.println("capacity : " + capacity.invoke(map)); //capacity : 2
 
    map.put(2, "二");
    capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map)); //capacity : 4 當(dāng)前容量為2 插入該元素后size為 2 > 2 * 3/4 開始擴(kuò)容

    //當(dāng)前容量為4 此時已有2個 3 = 4 * 3/4 不進(jìn)行擴(kuò)容
    map.put(3, "三");
    capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map)); //capacity : 4 當(dāng)前容量為2 插入該元素后size為 3 = 4 * 3/4 不擴(kuò)容

    map.put(4, "四");
    capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));//capacity : 8  當(dāng)前容量為4 此時已有4個 4 > 4 * 3/4 開始擴(kuò)容
}

上面的例子可以看出put后，hashmap確實(shí)有進(jìn)行擴(kuò)容伶氢，hashMap的擴(kuò)容機(jī)制與其它的集合邊長不太一樣趟径，它是通過當(dāng)前hash桶個數(shù)乘2進(jìn)行擴(kuò)容

hashMap主要是通過resize()方法擴(kuò)容

假設(shè)oldTable的key的hash為15瘪吏，7，4舵抹，5，8劣砍，1惧蛹，hashMap為初始容量為8的數(shù)組桶，存儲位置如下

當(dāng)put一個新元素 假設(shè)為9香嗓，且加載因子使用默認(rèn)的0.75，在內(nèi)存空間中新的存儲位置如下

可以看到擴(kuò)容之后8跑到了第9個位置装畅，15跑到了第16個位置靠娱，舊的8，1掠兄，4像云，5在各自的鏈表上只有一個節(jié)點(diǎn)

根據(jù) e.hash & (newCap - 1) 相當(dāng)于 與上15后，都為自己本身所以位置保持不變

但是鏈表上不止有一個節(jié)點(diǎn)的情況蚂夕，比如說上面的7迅诬，15存放的位置

這個時候是先根據(jù) e.hash & oldCap判斷元素在數(shù)組的位置是否需要移動

比如說 7 & 8 = 0111 & 1000 = 0 ; 15 & 8 = 1111 & 1000 = 1，規(guī)律是比較高位的第一個 比如說15為高位婿牍，第一個為1侈贷，如果高位為1那么與后結(jié)果也為1

當(dāng)e.hash & oldCap == 0時

鏈表上節(jié)點(diǎn)位置保持不變

當(dāng)e.hash & oldCap == 1時

鏈表上節(jié)點(diǎn)的位置為原位置的index + oldCap 比如說15，新的索引位置為7+8為15

值得一提的是等脂，jdk1.8的resize()方法相比與之前做了點(diǎn)優(yōu)化俏蛮，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候上遥，如果在新表的數(shù)組索引位置相同搏屑，則鏈表元素會倒置，但JDK1.8不會倒置粉楚，jdk8通過e.hash & oldCap睬棚，通過0和1的值均勻把之前的沖突的節(jié)點(diǎn)分散到新的bucket了，這樣做更為高效解幼。

代碼見【4.4.5 resize()方法】

5.loadFactor加載因子為何為0.75f

加載因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度抑党，它衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高撵摆，反之越小底靠。
簡單來說就是如果加載因子太小，空間利用率低特铝，且太容易擴(kuò)容對性能不太友好暑中，設(shè)置太高壹瘟，不及時擴(kuò)容容易導(dǎo)致沖突幾率大，將提高了查詢成本鳄逾。所以0.75是很合適的值稻轨，經(jīng)過試驗(yàn)，在理想情況下,使用隨機(jī)哈希碼,節(jié)點(diǎn)出現(xiàn)的頻率在hash桶中遵循泊松分布【在頻率附近發(fā)生概率高雕凹，向兩邊對稱下降殴俱。】
詳細(xì)見 為什么HashMap中默認(rèn)加載因子為0.75

6.hashMap中一般使用什么類型的元素作為key枚抵，為什么线欲？

常用String，Integer這樣的key
主要原因?yàn)?br> 這些類是Immutable(不可變的)汽摹，String和基本類型的包裝類規(guī)范的重寫了hashCode()和equals()方法李丰。作為不可變類天生是線程安全的，而且可以很好的優(yōu)化比如可以緩存hash值逼泣，避免重復(fù)計算等等趴泌，如果采用可變的對象類型，可能出現(xiàn)put進(jìn)去就無法查詢到的情況拉庶。
如果想用自定義的類型作為鍵踱讨，那么需要遵守equals()和hashCode()方法的定義規(guī)則且不可變，對象插入到map后就不會再改變砍的。

HashMap的key可以是可變對象嗎痹筛？

7.源碼中為什么要用transient修飾桶數(shù)組table

transient Node<K,V>[] table;

在java中，被transient關(guān)鍵字修飾的變量不會被默認(rèn)的序列化機(jī)制序列化廓鞠。

hashMap實(shí)現(xiàn)了Serializable接口帚稠，通過實(shí)現(xiàn)readObject/writeObject兩個方法自定義了序列化的內(nèi)容，size不用多說了床佳，一般涉及到大小可以直接計算的就沒必要再序列化滋早。

為什么不序列化table？原因有下

1.table大多數(shù)情況是無法存滿的砌们。比如說桶數(shù)組容量是16杆麸，只put了一個元素，這會造成序列化未使用的部分浪感。造成浪費(fèi)昔头。

2.同一個鍵值對在不同jvm下，所處桶的位置可能是不同的影兽，在不同的jvm下反序列化可能發(fā)生錯誤揭斧。(hashmap的get/put/remove等方法剛開始都是通過hash找到鍵所在的桶位置，就是數(shù)組下標(biāo)峻堰，但如果鍵沒有重寫hashCode方法讹开，就會調(diào)用Object的hashCode方法盅视，而Object的hashcode方法是navtive(本地方法)的，這里的hashcode是對對象內(nèi)存地址的映射得出的int結(jié)果旦万，具體怎么計算不得而知闹击，但是在不同jvm下，可能有不同的hashcode實(shí)現(xiàn)成艘，這樣產(chǎn)生的hash也不一樣)赏半。

8.HashMap的key如果為null，怎么查找值

我們知道hashMap只允許一個為null的key狰腌，如果key為null除破，因?yàn)閗ey為null牧氮，那么hash為0琼腔，那么p = tab[i = (n - 1) & hash 也一定為0，所以是從數(shù)組上第一個位置的鏈表下查找踱葛。

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

6.使用建議

1.默認(rèn)情況下HashMap的容量是16丹莲，但是，如果用戶通過構(gòu)造函數(shù)指定了一個數(shù)字作為容量尸诽，那么Hash會選擇大于該數(shù)字的第一個2的冪作為容量甥材。(1->2、7->8性含、9->16)

在初始化HashMap的時候洲赵，應(yīng)該盡量指定其大小。尤其是當(dāng)你已知map中存放的元素個數(shù)時商蕴。（《阿里巴巴Java開發(fā)規(guī)約》）

這邊可以看下hashMap的4個構(gòu)造方法叠萍，一般采用3，但如果已經(jīng)知道個數(shù)绪商，建議用2(加載因子0.75很合適不建議改動)

//1 自定義傳初始容量和加載因子
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);
}

//2 自定義初始大小 調(diào)1構(gòu)造方法苛谷，加載因子使用默認(rèn)大小
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//3 最常用的無參構(gòu)造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//4 將別的map對象映射到自身存儲，很少用
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

這邊講解一下tableSizeFor方法格郁。簡述一下該方法的作用：

如果自定義容量大小時(調(diào)1或2的構(gòu)造方法)腹殿，傳入一個初始容量大小，大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù)例书。比如10锣尉，則返回16，75返回128

不這么做的缺點(diǎn)

假設(shè)HashMap需要放置1024個元素决采，由于沒有設(shè)置初始容量大小悟耘，隨著元素不斷增加，容量7次被迫擴(kuò)大织狐。而resize過程需要重建hash表暂幼，這會嚴(yán)重影響性能筏勒。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    //cap-1的目的是因?yàn)槿绻鹀ap是2的冪數(shù)不做-1操作的話 那么最后執(zhí)行完右移操作的話，返回的值將會是原有值得兩倍旺嬉。如果n為0的話管行，即cap=1，經(jīng)過后面幾次操作返回的為0邪媳，最后返回的capacity仍然為1(最后有加1的操作)
    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;
}

解釋一下這段代碼

在java中捐顷，|=的作用是比較兩個對象是否相等

a|=b的意思就是把a(bǔ)和b按位或然后賦值給a

以10為例整體流程大致如下

算法流程

簡單來說，這種運(yùn)算最后會導(dǎo)致1占滿了它自己所占位雨效，比如說250迅涮，它的二進(jìn)制為

11111010，經(jīng)過上面的或運(yùn)算之后徽龟，最終將變?yōu)?1111111叮姑，這種情況在加上1，就是大于這個數(shù)的最小二次冪据悔。

7.總結(jié)

HashMap的設(shè)計與實(shí)現(xiàn)十分的巧妙传透。jdk8更是有很多提升，還沒寫這篇博客對于HashMap的理解僅僅只在表面极颓。閱讀源碼后才發(fā)現(xiàn)里面還有不少的學(xué)問朱盐，由于本人水平有限，雖然花了很多時間寫了很多但還有很多細(xì)節(jié)并不了解菠隆，比如說紅黑樹的代碼實(shí)現(xiàn)細(xì)節(jié)兵琳，也有可能有幾個地方描述錯誤或者不到位，如果文章有誤請指正骇径，以便于我及時修改和學(xué)習(xí)躯肌。

8.參考鏈接

HashMap 源碼詳細(xì)分析(JDK1.8)

HashMap resize方法的理解（一)

JDK 源碼中 HashMap 的 hash 方法原理是什么

hashMap死循環(huán)問題

淺談jdk8為何線程不安全