聲明，本文用得是jdk1.8
前面已經(jīng)講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹的基礎(chǔ)了：
本篇主要講解HashMap，以及涉及到一些與hashtable的比較~
看這篇文章之前最好是有點(diǎn)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)：
當(dāng)然了，如果講得有錯(cuò)的地方還請(qǐng)大家多多包涵并不吝在評(píng)論去指正～
一、HashMap剖析
首先看看HashMap的頂部注釋說了些什么：
再來看看HashMap的類繼承圖：
下面我們來看一下HashMap的屬性：
成員屬性有這么幾個(gè)：
再來看一下hashMap的一個(gè)內(nèi)部類Node：
我們知道Hash的底層是散列表，而在Java中散列表的實(shí)現(xiàn)是通過數(shù)組+鏈表的~
再來簡(jiǎn)單看看put方法就可以印證我們的說法了：數(shù)組+鏈表-->散列表
我們可以簡(jiǎn)單總結(jié)出HashMap：
無序，允許為null，非同步
底層由散列表(哈希表)實(shí)現(xiàn)
初始容量和裝載因子對(duì)HashMap影響挺大的，設(shè)置小了不好，設(shè)置大了也不好
1.1HashMap構(gòu)造方法
HashMap的構(gòu)造方法有4個(gè)：
在上面的構(gòu)造方法最后一行，我們會(huì)發(fā)現(xiàn)調(diào)用了tableSizeFor()，我們進(jìn)去看看：
這是位運(yùn)算算法，具體流程可參考：
https://www.cnblogs.com/loading4/p/6239441.html
https://blog.csdn.net/fan2012huan/article/details/51097331
看完上面可能會(huì)感到奇怪的是：為啥是將2的整數(shù)冪的數(shù)賦給threshold？
threshold這個(gè)成員變量是閾值，決定了是否要將散列表再散列。它的值應(yīng)該是：capacity * load factor才對(duì)的。
其實(shí)這里僅僅是一個(gè)初始化，當(dāng)創(chuàng)建哈希表的時(shí)候，它會(huì)重新賦值的：
至于別的構(gòu)造方法都差不多，這里我就不細(xì)講了：
1.2put方法
put方法可以說是HashMap的核心，我們來看看：
我們來看看它是怎么計(jì)算哈希值的：
為什么要這樣干呢？？我們一般來說直接將key作為哈希值不就好了嗎，做異或運(yùn)算是干嘛用的？？
我們看下來：
我們是根據(jù)key的哈希值來保存在散列表中的，我們表默認(rèn)的初始容量是16，要放到散列表中，就是0-15的位置上。也就是tab[i = (n - 1) & hash]?？梢园l(fā)現(xiàn)的是：在做&運(yùn)算的時(shí)候，僅僅是后4位有效~那如果我們key的哈希值高位變化很大，低位變化很小。直接拿過去做&運(yùn)算，這就會(huì)導(dǎo)致計(jì)算出來的Hash值相同的很多。
而設(shè)計(jì)者將key的哈希值的高位也做了運(yùn)算(與高16位做異或運(yùn)算，使得在做&運(yùn)算時(shí)，此時(shí)的低位實(shí)際上是高位與低位的結(jié)合)，這就增加了隨機(jī)性，減少了碰撞沖突的可能性！
下面我們?cè)賮砜纯戳鞒淌窃趺礃拥模?/p>
新值覆蓋舊值，返回舊值測(cè)試：
接下來我們看看resize()方法，在初始化的時(shí)候要調(diào)用這個(gè)方法，當(dāng)散列表元素大于capacity * load factor的時(shí)候也是調(diào)用resize()
1.3get方法
接下來我們看看getNode()是怎么實(shí)現(xiàn)的：
1.4remove方法
再來看看removeNode()的實(shí)現(xiàn)：
二、HashMap與Hashtable對(duì)比
從存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)來講基本上都是相同的。它和HashMap的最大的不同是它是線程安全的，另外它不允許key和value為null。Hashtable是個(gè)過時(shí)的集合類，不建議在新代碼中使用，不需要線程安全的場(chǎng)合可以用HashMap替換，需要線程安全的場(chǎng)合可以用ConcurrentHashMap替換
Hashtable具體閱讀源碼可參考：
https://blog.csdn.net/panweiwei1994/article/details/77427010
https://blog.csdn.net/panweiwei1994/article/details/77428710
三、總結(jié)
在JDK8中HashMap的底層是：數(shù)組+鏈表(散列表)+紅黑樹
在散列表中有裝載因子這么一個(gè)屬性，當(dāng)裝載因子*初始容量小于散列表元素時(shí)，該散列表會(huì)再散列，擴(kuò)容2倍！
裝載因子的默認(rèn)值是0.75，無論是初始大了還是初始小了對(duì)我們HashMap的性能都不好
裝載因子初始值大了，可以減少散列表再散列(擴(kuò)容的次數(shù))，但同時(shí)會(huì)導(dǎo)致散列沖突的可能性變大(散列沖突也是耗性能的一個(gè)操作，要得操作鏈表(紅黑樹)！
裝載因子初始值小了，可以減小散列沖突的可能性，但同時(shí)擴(kuò)容的次數(shù)可能就會(huì)變多！
初始容量的默認(rèn)值是16，它也一樣，無論初始大了還是小了，對(duì)我們的HashMap都是有影響的：
初始容量過大，那么遍歷時(shí)我們的速度就會(huì)受影響~
初始容量過小，散列表再散列(擴(kuò)容的次數(shù))可能就變得多，擴(kuò)容也是一件非常耗費(fèi)性能的一件事~
從源碼上我們可以發(fā)現(xiàn)：HashMap并不是直接拿key的哈希值來用的，它會(huì)將key的哈希值的高16位進(jìn)行異或操作，使得我們將元素放入哈希表的時(shí)候增加了一定的隨機(jī)性。
還要值得注意的是：并不是桶子上有8位元素的時(shí)候它就能變成紅黑樹，它得同時(shí)滿足我們的散列表容量大于64才行的~
