• 前言
• HashMap
• HashMap類繼承圖
• HashMap屬性
• HashMap構(gòu)造函數(shù)
  • HashMap(int initialCapacity, float loadFactor)
  • HashMap(Map<? extends K, ? extends V> m)
• HashMap常見Api解析
  • put(K key, V value)
  • putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
  • Node<K,V>[] resize()
  • get(Object key)
  • remove(Object key)
  • removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)
• HashMap與HashTable對(duì)比
• 總結(jié)

前言

本文基于jdk1.8

HashMap

先來(lái)看一下Java官方描述

• 基于哈希表的 Map 接口的實(shí)現(xiàn)。
• 允許使用 null 值和 null 鍵。
• 除了非同步和允許使用 null 之外苇本，HashMap 類與 Hashtable 大致相同喊括。
• 不保證映射的順序，特別是它不保證該順序恒久不變（擴(kuò)容后元素在底層會(huì)重散列）虏杰。
• 迭代所需的時(shí)間與 HashMap實(shí)例的“容量”（桶的數(shù)量）及鍵-值映射數(shù)成比例贱鼻。即初始容量設(shè)置得太高（或?qū)⒇?fù)載因子設(shè)置得太低）對(duì)遍歷的性能影響都很大喻奥。
  • 負(fù)載因子 = 總鍵值對(duì)數(shù) / 箱子個(gè)數(shù)(數(shù)組元素)
• HashMap 的實(shí)例有兩個(gè)參數(shù)影響其性能：初始容量 和負(fù)載因子。當(dāng)元素個(gè)數(shù)超過(guò)當(dāng)前容量(桶數(shù))與負(fù)載因子的乘機(jī)時(shí)赖欣，哈希表會(huì)對(duì)其元素rehash屑彻，底層的桶數(shù)*2。
• 默認(rèn)負(fù)載因子(0.75)顶吮，加載因子過(guò)高雖然減少了空間開銷社牲，但同時(shí)也增加了查詢成本。在設(shè)置初始容量時(shí)應(yīng)該考慮到Map中所要容納的元素?cái)?shù)量及其加載因子悴了，以便最大限度地減少rehash操作次數(shù)搏恤。如果初始容量大于最大條目數(shù)除以加載因子，則不會(huì)發(fā)生rehash操作湃交。
• 如果從一開始就知道有多少元素要存到Map中熟空，最好一開始就指定好Map初始容量，盡量避免其rehash操作搞莺。性能會(huì)大大提高
• 此實(shí)現(xiàn)不是同步的息罗。想要同步在一些列操作外手動(dòng)同步，或者使用Map m = Collections.synchronizedMap(new HashMap(...));方法來(lái)“包裝”該映射才沧。最好在創(chuàng)建時(shí)完成這一操作阱当，以防止對(duì)映射進(jìn)行意外的非同步訪問

HashMap類繼承圖

• 實(shí)現(xiàn)了Serializable，Cloneable接口
• 繼承了父類AbstractMap

image

HashMap屬性

靜態(tài)屬性：

• DEFAULT_INITIAL_CAPACITY: 初始容量糜工，也就是默認(rèn)會(huì)創(chuàng)建 16 個(gè)箱子弊添，箱子的個(gè)數(shù)不能太多或太少。如果太少捌木，很容易觸發(fā)擴(kuò)容油坝，如果太多舔糖，遍歷哈希表會(huì)比較慢。
• MAXIMUM_CAPACITY: 哈希表最大容量告唆，一般情況下只要內(nèi)存夠用巴帮，哈希表不會(huì)出現(xiàn)問題。
• DEFAULT_LOAD_FACTOR: 默認(rèn)的負(fù)載因子瞬女。因此初始情況下窍帝，當(dāng)鍵值對(duì)的數(shù)量大于 16 * 0.75 = 12 時(shí)，就會(huì)觸發(fā)擴(kuò)容诽偷。
• TREEIFY_THRESHOLD: 上文說(shuō)過(guò)坤学，如果哈希函數(shù)不合理，即使擴(kuò)容也無(wú)法減少箱子中鏈表的長(zhǎng)度报慕，因此 Java 的處理方案是當(dāng)鏈表太長(zhǎng)時(shí)深浮，轉(zhuǎn)換成紅黑樹。這個(gè)值表示當(dāng)某個(gè)箱子中眠冈，鏈表長(zhǎng)度大于等于 8 時(shí)飞苇，有可能會(huì)轉(zhuǎn)化成樹。
• UNTREEIFY_THRESHOLD: 在哈希表擴(kuò)容時(shí)蜗顽，如果發(fā)現(xiàn)鏈表長(zhǎng)度小于 6布卡，則會(huì)由樹重新退化為鏈表雇盖。
• MIN_TREEIFY_CAPACITY: 在轉(zhuǎn)變成樹之前羽利，還會(huì)有一次判斷，只有鍵值對(duì)數(shù)量大于 64 才會(huì)發(fā)生轉(zhuǎn)換刊懈。這是為了避免在哈希表建立初期这弧，多個(gè)鍵值對(duì)恰好被放入了同一個(gè)鏈表中而導(dǎo)致不必要的轉(zhuǎn)化。

成員屬性：

image

• table：HashMap的鏈表數(shù)組虚汛。它在自擴(kuò)容時(shí)總是2的次冪
• entrySet: HashMap實(shí)例中的Entry的Set集合匾浪。
• size: HashMap實(shí)例中映射的數(shù)量
• modCount: 這個(gè)HashMap被結(jié)構(gòu)修改的次數(shù)
• threshold: 元素的閾值
• loadFactor: 哈希表的負(fù)載因子

HashMap簡(jiǎn)單總結(jié)：

• 存取無(wú)序
• 鍵值允許為NULL
• 非同步類
• 底層是哈希表
• 初始容量和裝載因子是決定整個(gè)類性能的關(guān)鍵點(diǎn)。

HashMap構(gòu)造函數(shù)

HashMap的構(gòu)造函數(shù)共4個(gè)卷哩。

image

HashMap(int initialCapacity, float loadFactor)

我們可以看到loadFactor參數(shù)Java官方還對(duì)其進(jìn)行了Float.NaN(0.0f/0.0f)的判斷蛋辈。可以說(shuō)考慮的非常周到了

同時(shí)在構(gòu)造函數(shù)的最后一行将谊，在為threshold賦值的時(shí)候冷溶，調(diào)用了tableSizeFor()函數(shù)來(lái)對(duì)輸入的初始容量進(jìn)行判斷，來(lái)保證該初始容量是2的整數(shù)次冪尊浓。

image

函數(shù)具體釋義可參考：HashMap源碼注解 之 靜態(tài)工具方法hash()逞频、tableSizeFor()（四）

• 此時(shí)不經(jīng)要想為什么是將2的整數(shù)冪的數(shù)賦給threshold？

首先我們先來(lái)了解一下threshold這個(gè)屬性：

image

threshold這個(gè)成員變量是閾值栋齿，決定了是否要將散列表擴(kuò)容充重散列苗胀。它的值應(yīng)該是：(capacity * loadfactor）才對(duì)的襟诸。

• 那我們就更奇怪了，那這里還給他賦值干什么基协？

其實(shí)這里僅僅是對(duì)該值的一個(gè)初始化歌亲，tableSizeFor函數(shù)賦予了該值一個(gè)最接近initialCapacity值的2的整數(shù)冪的值，當(dāng)調(diào)用putVul函數(shù)需要往元素容器中真正添加元素的時(shí)候澜驮，也就是真正創(chuàng)建哈希表的時(shí)候陷揪，該值才會(huì)在resize函數(shù)中根據(jù)一些條件判斷來(lái)重新定義賦值的。

HashMap(Map<? extends K, ? extends V> m)

image

這個(gè)構(gòu)造函數(shù)其實(shí)本質(zhì)上和剛才我們所看的給初始容量和負(fù)載因子的構(gòu)造函數(shù)一致杂穷。函數(shù)最終做的除了參數(shù)上可以看出來(lái)的悍缠，把一個(gè)Map實(shí)例中的元素都插入到HashMap實(shí)例中外，由于負(fù)載因子沒有顯示指定所以賦予了loadFactory默認(rèn)值亭畜。

并且把具體的Map迭代放在了調(diào)用的putMapEntries函數(shù)中。從該函數(shù)注釋中看出迎卤，該函數(shù)是服務(wù)于putAll函數(shù)和constructor構(gòu)造函數(shù)的拴鸵。

從putMapEntries函數(shù)注釋中也可以看出，如果這個(gè)函數(shù)在初始化Map時(shí)被調(diào)用evict參數(shù)傳入的是false蜗搔。而如果這個(gè)函數(shù)是在afterNodeInsertion函數(shù)后調(diào)用的劲藐，那么則需要傳入的是true。

從putMapEntries函數(shù)的具體代碼實(shí)現(xiàn)上可以看出樟凄，其在Map第一次初始化的時(shí)候和我們剛才所看的構(gòu)造函數(shù)一致聘芜，都是在真正構(gòu)造HashMap前先為閾值賦予一個(gè)可靠地初值。然后才迭代入?yún)ap集合缝龄，將其元素都插入到HashMap中汰现。

其余的構(gòu)造函數(shù)都是大同小異。就不一一贅述了

總結(jié)：

從構(gòu)造函數(shù)中我們可以看出叔壤，HashMap的構(gòu)造函數(shù)其實(shí)工作就只有一個(gè)瞎饲。賦值

• 賦值負(fù)載因子
• 賦值閾值

HashMap常見Api解析

put(K key, V value)

 /**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以看出put函數(shù)具體實(shí)現(xiàn)其實(shí)是調(diào)用了putVal函數(shù)。并且從注釋中可以得知如果該映射存在炼绘，新值會(huì)替換掉舊值嗅战。

還可以看到的是傳入了5個(gè)參數(shù)，我們來(lái)了解簡(jiǎn)單一下這5個(gè)參數(shù)俺亮。

 /**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {

注釋很直白解釋的很清楚驮捍，按序號(hào)來(lái)

1. key的哈希值
2. key
3. value
4. 如果映射存在不替換原值？
5. 如果是false脚曾，代表當(dāng)前HashMap正處于創(chuàng)建階段东且。

我們大概知道了這5個(gè)參數(shù)是干嘛的了，就可以針對(duì)第一個(gè)參數(shù)具體的去了解一下key的哈希值是如何計(jì)算得了本讥。

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

這里就比較疑惑了苇倡，為什么不直接用key類型對(duì)應(yīng)的hashcode函數(shù)直接得到對(duì)應(yīng)的哈希碼呢富纸？從這段代碼可以看出來(lái)Java官方拿key的哈希碼和其哈希碼向右移位16位的結(jié)果進(jìn)行異或操作。我們知道右移高位補(bǔ)0旨椒，由于哈希碼返回的是一個(gè)4字節(jié)32位int類型的值晓褪。所以總共可以看成是高16位，低16位組成的综慎。

而這里對(duì)其哈希碼進(jìn)行右移16位之后高位空缺補(bǔ)0涣仿，原高位到了現(xiàn)低位。然后再拿原哈希碼與現(xiàn)哈希碼進(jìn)行異或操作示惊，而我們知道任何數(shù)跟0異或都是其本身好港。所以可以看出Java官方最終目的，是想讓哈希碼原低16位與其高16位進(jìn)行異或操作米罚。而原高16位卻不變钧汹，原來(lái)如此~

image

但為什么要這樣呢？

其實(shí)這個(gè)與HashMap中元素插入時(shí)對(duì)應(yīng)位置table數(shù)組下標(biāo)的計(jì)算有關(guān)录择。

image

核心代碼：

n = (tab = resize()).length;
i =（n-1） & hash

我們暫且不看resize函數(shù)拔莱，putVal函數(shù)在初次進(jìn)來(lái)的時(shí)候該resize函數(shù)做的其實(shí)就是哈希表初始化的工作。由于DEFAULT_INITIAL_CAPACITY變量的存在隘竭，我們暫且認(rèn)為該哈希表的大小length為16塘秦。即n=16

那么在計(jì)算元素插入位置的時(shí)候，由于底層是數(shù)組动看。所以真正存儲(chǔ)的位置就是[0-15]尊剔。所以n-1。

而因?yàn)榱饨裕瑃able的length屬性都是2的冪须误，因此i僅與hash值的低n位有關(guān)（此n非table.length，而是2的冪指數(shù)）
假設(shè)table.length=2^4=16仇轻。

image

由上圖可以看到霹期，32位的hash值只有低4位參與了運(yùn)算。
僅有4位的異或很容易產(chǎn)生碰撞拯田。但是由于table.length的大小只能由插入數(shù)據(jù)的多少來(lái)改變历造，而hash值得高16位又由于與操作置0了，所以設(shè)計(jì)人員相出一個(gè)好辦法就是通過(guò)對(duì)key的hash值進(jìn)行高16位與低16位異或來(lái)將高位與低位整合船庇。這樣不但可以保留原來(lái)key哈希值的差異性(高位地位同時(shí)作用)吭产，同時(shí)來(lái)增加低16位2進(jìn)制數(shù)值在計(jì)算時(shí)的差異性進(jìn)而減少這種哈希沖突的情況。

參考：HashMap源碼注解 之 靜態(tài)工具方法hash()鸭轮、tableSizeFor()（四）

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

接下來(lái)便可以繼續(xù)分析真正的put函數(shù)了臣淤。

總結(jié)下來(lái)就是：

• 散列表初次put數(shù)組任為NULL時(shí)，調(diào)用resize函數(shù)(單獨(dú)拉出來(lái)說(shuō))來(lái)初始化散列表
• 當(dāng)根據(jù)元素的哈希值可以確認(rèn)分配到散列表的下標(biāo)時(shí)窃爷，如果此處沒有元素邑蒋，那么就直接插入
  • 當(dāng)該元素就是和我一樣的元素姓蜂。即此處元素的hash值和key值都與要插入的元素相等時(shí)。通過(guò)變量e指向該元素医吊。
  • 當(dāng)該元素已經(jīng)不是一個(gè)鏈表結(jié)構(gòu)而是一個(gè)紅黑樹結(jié)構(gòu)的時(shí)候(元素肯定過(guò)6)钱慢，將該元素插入到紅黑樹中，并用e指向該元素
  • 否則該處就是一個(gè)鏈表卿堂，鏈表頭結(jié)點(diǎn)不是要插入的元素束莫，但不能排除其他節(jié)點(diǎn)不是。所以然后遍歷這個(gè)數(shù)組草描，當(dāng)該鏈表中遍歷到的節(jié)點(diǎn)的下一節(jié)點(diǎn)為空時(shí)將該元素插入到鏈表尾览绿，循環(huán)跳出。如果不為空的話穗慕，對(duì)下一節(jié)點(diǎn)進(jìn)行判斷看是否是待插入節(jié)點(diǎn)饿敲。如果是跳出
• 程序進(jìn)行到綠框時(shí)，此時(shí)程序只有兩種情況逛绵。元素最后找到空出插入了怀各，但是e無(wú)法指向∈畲啵或者說(shuō)元素找到和自己一樣的元素了渠啤，并且由變量e指向狐肢。
  • 新舊值替換添吗，根據(jù)函數(shù)一開始傳入的參數(shù)onlyIfAbsent或者oldValue的特殊情況來(lái)決定是否替換。
    • key對(duì)應(yīng)的舊值如果為NULL份名，那么無(wú)論onlyIfAbsent是否決定替換碟联。都將被替換。
    • key對(duì)應(yīng)的舊值如果不為NULL僵腺，那么如果onlyIfAbsent是false就替換鲤孵。
  • 最后返回被替換掉的值。
• 修改了實(shí)例結(jié)構(gòu)所以modCount+1辰如。
• 加入元素后判斷元素個(gè)數(shù)是否超過(guò)了閾值普监。如果是resize函數(shù)擴(kuò)桶數(shù)

這樣我們的putVal函數(shù)其實(shí)思路就理清了，看上去很復(fù)雜琉兜，其實(shí)宗旨沒變凯正，也就是判斷，擴(kuò)容豌蟋，找位置廊散，去除特殊情況，元素插入梧疲，只不過(guò)數(shù)據(jù)結(jié)構(gòu)的差異性導(dǎo)致其特殊情況較多允睹，判斷的復(fù)雜了些运准。接下來(lái)該分析resize函數(shù)了。我們可以明顯的看到putVal函數(shù)多出調(diào)用了resize函數(shù)缭受。所以要想徹底理清HashMap實(shí)例是如何構(gòu)建的胁澳，resize函數(shù)必然需要了解一下。

目前對(duì)resize的了解：table==null時(shí)贯涎，調(diào)用resize初始化table听哭。元素?cái)?shù)量>=threshold時(shí)，調(diào)用resize擴(kuò)容塘雳。

Node<K,V>[] resize()

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table
 */
final Node<K,V>[] resize() {
}

從該函數(shù)的開頭我們也可以確認(rèn)我們剛才的觀點(diǎn)陆盘。用來(lái)初始化和給table擴(kuò)容的。

總結(jié)下來(lái)就是：

哈細(xì)表擴(kuò)容：

• 當(dāng)舊表容量大于0時(shí)败明，即舊表被初始化過(guò)了
  • 并且如果其容量大于或等于int的最大值隘马。那么閾值設(shè)置為int的最大值。并返回舊舊表妻顶，此時(shí)表已經(jīng)不能再擴(kuò)容了酸员，能做的只有置閾值為其能到大的最大值，盡可能的減少擴(kuò)容次數(shù)讳嘱。
  • 當(dāng)舊表容量不及最大容量的一半時(shí)幔嗦，并且舊表容量大于默認(rèn)容量16時(shí)。由于函數(shù)resize被調(diào)用了沥潭。所以需要滿足外界擴(kuò)容需求邀泉，舊表閾值<<1。
• 當(dāng)舊表沒被初始化钝鸽，但HashMap實(shí)例被初始化了汇恤。
  • 否則當(dāng)舊表還未被初始化時(shí)，只是在初始化HashMap實(shí)例的時(shí)候賦予了閾值和負(fù)載因子(結(jié)合構(gòu)造函數(shù)思考)拔恰，當(dāng)舊閾值>0時(shí)因谎，哈希表初始容量設(shè)置為閾值。
  • 否則颜懊，當(dāng)構(gòu)造HashMap實(shí)例時(shí)如果連閾值也沒有賦值(默認(rèn)為0)只是初始化了負(fù)載因子的話(默認(rèn)無(wú)參構(gòu)造函數(shù))财岔。初始化哈希表容量為DEFAULT_INITIAL_CAPACITY即16，閾值為DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY即12河爹。
• 當(dāng)閾值=0時(shí)匠璧，新閾值=新容量*負(fù)載因子。當(dāng)HashMap實(shí)例被被初始化時(shí)閾值也被初始化時(shí)會(huì)走這一分支
• 最后確定容量和閾值后初始化哈細(xì)表昌抠。

數(shù)據(jù)遷移：

• 當(dāng)舊哈細(xì)表存在時(shí)患朱，迭代哈細(xì)表每個(gè)元素。因?yàn)槊總€(gè)元素中存的都是鏈表或者紅黑樹炊苫。根據(jù)每個(gè)元素的哈希值重新散列到新哈希表的對(duì)應(yīng)位置上裁厅。底層數(shù)據(jù)結(jié)構(gòu)和節(jié)點(diǎn)的存儲(chǔ)位置很大程度上會(huì)更改冰沙。

get(Object key)

從注釋中可以看出，返回 null 值并不一定 表明該映射不包含該鍵的映射關(guān)系执虹；也可能該映射將該鍵顯示地映射為 null拓挥。可使用 containsKey 操作來(lái)區(qū)分這兩種情況袋励。

 /**
 * ·····
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 * ·····
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

函數(shù)具體查詢邏輯封裝到了getNode函數(shù)侥啤。

簡(jiǎn)單來(lái)說(shuō)：

• key對(duì)應(yīng)的哈希值計(jì)算出來(lái)落到哈希表對(duì)應(yīng)的地方上，如果有元素存在茬故。
• 有元素存在就需要比較了盖灸，因?yàn)樵厣峡赡艽娴氖擎湵砘蛘呒t黑樹。
  • 第一個(gè)元素就是搜尋的key本身
  • 第一個(gè)不是磺芭，但其是紅黑樹結(jié)構(gòu)赁炎。參數(shù)傳遞并去紅黑樹中找
  • 不是紅黑樹結(jié)構(gòu)，那么就是鏈表結(jié)構(gòu)钾腺，進(jìn)行迭代尋找徙垫，獲取key對(duì)應(yīng)的value。

remove(Object key)

/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

從函數(shù)的注釋中可以看出放棒，該函數(shù)刪除key對(duì)應(yīng)的Entry并返回與 key 關(guān)聯(lián)的舊值姻报；如果 key 沒有任何映射關(guān)系，則返回 null间螟。但需要注意的是： 返回 null 還可能表示該映射之前將 null 與 key 關(guān)聯(lián)吴旋。

函數(shù)再次把元素的通過(guò)hash函數(shù)包裝傳了進(jìn)去，這很好理解寒亥，因?yàn)榈讓邮枪１砺镉矢贿@樣怎么能找到key到底在哈希表什么位置呢荧关。我們可以看到刪除邏輯的具體邏輯封裝到了removeNode函數(shù)中溉奕。

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

先來(lái)對(duì)removeNod函數(shù)的多個(gè)參數(shù)進(jìn)行一番分析。

 * @param hash hash for key 
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing

1. hash(key)
2. key
3. 對(duì)應(yīng)matchValue參數(shù)忍啤，如果matchValue為true加勤。那么刪除key時(shí)其value必須與value相等，否則跳過(guò)這次刪除
4. 如果true同波。只有當(dāng)值相等時(shí)才刪除鳄梅。
5. 如果為false，那么在刪除節(jié)點(diǎn)時(shí)不移動(dòng)其他節(jié)點(diǎn)未檩。

總的來(lái)說(shuō)：

• 先判斷key是否可以映射到哈希表上戴尸。

  • 如果可以，判斷一下映射的位置頭元素是否為該查找的元素冤狡。
  • 如果頭元素不是要找元素孙蒙，判斷一下頭元素后有無(wú)其他元素项棠。如果有再判斷一下這個(gè)元素的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹，如果是挎峦，用node變量指向該key對(duì)應(yīng)在紅黑樹中的節(jié)點(diǎn)香追。
  • 如果不是那說(shuō)明哈希表該索引處是一個(gè)鏈表結(jié)構(gòu)，然后對(duì)鏈表元素迭代尋找該元素坦胶，并用node節(jié)點(diǎn)指向?qū)ふ业降脑撛赝傅洹Ｐ枰⒁獾氖牵?code>p變量的邏輯定位，由于do while循環(huán)體中break語(yǔ)句相對(duì)于p=e語(yǔ)句置前顿苇，p變量在循環(huán)退出時(shí)指向的是node節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)峭咒。

• 經(jīng)歷過(guò)橘黃色和紅色兩大塊邏輯判斷，成功找到了待刪除節(jié)點(diǎn)的位置纪岁，并用node節(jié)點(diǎn)指向讹语。如果該Node節(jié)點(diǎn)被成功找到了的話。

  • 紅黑樹：如果node節(jié)點(diǎn)所在哈希表的位置元素的存儲(chǔ)結(jié)構(gòu)式是紅黑樹的話蜂科。調(diào)用紅黑樹的刪除方法
  • 鏈表：如果頭節(jié)點(diǎn)就是待刪除節(jié)點(diǎn)的話顽决，那么待刪除節(jié)點(diǎn)的next節(jié)點(diǎn)做頭結(jié)點(diǎn)
  • 鏈表：如果待刪除節(jié)點(diǎn)是鏈表中間部分的某個(gè)節(jié)點(diǎn)。借助p變量進(jìn)行刪除导匣。

• modCount+1才菠，size-1，并將刪除的節(jié)點(diǎn)返回贡定。

HashMap與HashTable對(duì)比

我們從一開始就曾說(shuō)赋访，兩者從存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)來(lái)講基本上都是相同的。兩者最大的差別就是HashTable是線程安全的缓待，而HashMap是線程不安全的蚓耽。并且在數(shù)據(jù)存儲(chǔ)時(shí)，HashMap允許key和value為null旋炒。而HashTable則鍵值均不允許為null步悠。并且HashTable規(guī)定用作鍵的對(duì)象必須實(shí)現(xiàn) hashCode 方法和 equals 方法。

HashTable在Map映射中的地位有點(diǎn)兒像Vector在List集合中的定位瘫镇。也是比較過(guò)時(shí)的類鼎兽，設(shè)計(jì)上有一些缺陷，不需要線程安全的情況下可以使用HashMap替代它铣除，而需要線程安全的情況下也可以用ConcurrentHashMap來(lái)替代它谚咬。

總結(jié)

• HashMap的底層是：數(shù)組+鏈表+紅黑樹
• HashMap的實(shí)例有兩個(gè)重要參數(shù)影響其性能。負(fù)載因子和初始容量尚粘，(裝載因子*初始容量)< 散列表元素時(shí)择卦，該散列表會(huì)擴(kuò)容2倍，并重散列。
  • 負(fù)載因子：默認(rèn)0.75秉继，無(wú)論是初始大了還是初始小了對(duì)HashMap的性能都不好
    • 初始值大了潘明，可以減少散列表再散列(擴(kuò)容的次數(shù))，但同時(shí)會(huì)導(dǎo)致散列沖突的可能性變大(散列沖突也是耗性能的一個(gè)操作秕噪，要得操作鏈表(紅黑樹)
    • 初始值小了钳降，可以減小散列沖突的可能性，但同時(shí)擴(kuò)容的次數(shù)可能就會(huì)變多腌巾！
  • 初始容量：默認(rèn)值是16遂填，無(wú)論初始大了還是小了對(duì)HashMap都是有影響的
    • 初始容量過(guò)大，那么遍歷時(shí)速度就會(huì)受影響~
    • 初始容量過(guò)小澈蝙，散列表再散列(擴(kuò)容的次數(shù))可能就變得多吓坚，擴(kuò)容也是一件非常耗費(fèi)性能的一件事
  • 參考公式：閾值 = 容量 * 負(fù)載因子
• HashMap在計(jì)算元素在哈希表中存儲(chǔ)位置的時(shí)候，并不是直接拿key的哈希值來(lái)用的灯荧，會(huì)先對(duì)key的哈希值進(jìn)行右移16位礁击，然后再與其key的哈希值進(jìn)行異或操作。根本上就是高位不變逗载，低位變?yōu)楦?6位和低16位的異或結(jié)果哆窿，使得元素在存儲(chǔ)時(shí)的隨機(jī)性更大了。分布更加均勻了厉斟，減少了哈希沖突發(fā)生的概率
• 并不是箱子上元素大于等于8位元素的時(shí)候該哈希表的元素底層就能變成紅黑樹挚躯，它得同時(shí)滿足哈希表總?cè)萘看笥?4才行，同時(shí)當(dāng)紅黑樹元素?cái)?shù)量低于8時(shí)擦秽，并不是會(huì)立馬變回鏈表码荔。而是在其元素小于6時(shí)才會(huì)。