Java基礎--HashMap源碼

• ​​1 HashMap實作的接口​​
• ​​2 HashMap繼承的類​​
• ​​3 HashMap 資料擷取​​

• ​​3.1 Iterable​​

• ​​3.1.1 Iterator​​
• ​​3.1.2 Consumer​​
• ​​3.1.3 Spliterator​​

• ​​3.2 Collection​​
• ​​3.3 AbstractCollection​​
• ​​3.4 Set​​
• ​​3.5 AbstractSet​​
• ​​3.6 KeySet -> HashMap​​
• ​​3.7 ValueSet > HashMap​​
• ​​3.8 EntrySet -> HashMap​​

• ​​4 HashMap 的疊代器​​

• ​​4.1 HashIterator​​
• ​​4.2 Iterator​​

• ​​5. Node​​

• ​​5.1 Node(連結清單)​​
• ​​5.2 TreeNode​​

• ​​6. Spliterator​​

• ​​6.1 Spliterator調用鍊​​
• ​​6.2 Spliterator屬性​​
• ​​6.3 Spliterator 操作​​
• ​​6.4 KeySpliterator,ValueSpliterator,EntrySpliterator​​

• ​​7. HashMap 其他的常用的操作​​

• ​​7.1 初始化​​
• ​​7.2 put​​
• ​​7.3 連結清單化​​
• ​​7.4 hashCode​​

• ​​8. 總結​​

說明，以下java環境都是基于jdk8u111進行。

這是使用idea的功能，檢視類的關系。

可以看到HashMap繼承了AbstractMap，實作了Map接口，Cloneable接口和Serializable接口。

但是，這個結構依然有些粗糙。

HashMap的結構，可以說一點都不簡單。

HashMap的類圖可以如下：

這什麼玩意？

不要着急，慢慢來。

1 HashMap實作的接口

可以看到，HashMap的結構主要是：繼承AbstractMap實作Map接口。

其他的Serializable和Cloneable主要是标記性接口，沒有方法定義。

Map主要定義了作為Map的操作：

Map定義了Map的通用操作。包括：size,isEmpty,containsKey,containsValue,get,put,putAll,clear,KetSet,values,entrySet操作。

對于這些操作，可以分為這些：

• Map名額：size,isEmpty
• Map操作：put,get,remove,clear,putAll
• Map查詢：containsKey,containsValue

• Map周遊：keySet,values,entrySet

  在Map内部，定義了Map實際存儲資料的資料結構是Entry

  同樣的，Map内部的Entry使用時用Map.Entry 通路。

  可以分為以下操作：

• Map.Entry操作：getKey,getValue,setValue
• Map.Entry比較操作：comparingByKey,comparingByValue

2 HashMap繼承的類

HashMap繼承了AbstractMap。而AbstractMap實作了Map的接口，其主要的作用是對Map和Map.Entry定義的接口，提供了實作。

HashMap繼承了AbstactMap，那麼， 在HashMap中，隻需要實作HashMap需要實作的方法即可。當然，作為抽象類，肯定也指定了一些必須要實作的方法：

public abstract Set<Entry<K,V>> entrySet();      

看到這裡，你一定比較奇怪，為什麼AbstractMap沒有強制子類實作keySet和valueSet?

因為，Entry是包含了key和value的。也就是說，我拿到了entry，那麼，我就拿到了key和value.

在AbstractMap中，是這樣實作的：

可以看到，他使用了AbstractSet，通過調用entrySet的方法擷取得到對應的Map.Entry，然後調用Map.Entry來實作keySet和valueSet.

至于AbstractSet，請繼續往下看。

3 HashMap 資料擷取

在1.2中，我們提到，Map定義的周遊的操作分别是:keySet,values,entrySet.通過這三個方法可以擷取到Map的資料。

為了實作這個目的，HashMap在内部定義了三個類：KeySet,Values,EntrySet。

因為在定義的時候，定義了KeySet，Values，EntrySet傳回的必須是Set.

是以，具體的實作中，傳回的是Set的抽象類AbstractSet。

其具體的結構圖如下：

而這些類是定義在HashMap類下的，是以姑且我們稱這些類内實作的類為組合類。

即，在HashMap記憶體在三個組合類：EntrySet，KetSet和Values.

這些組合類的結構如下：

從這三個組合類的結構，可以分析出：key，entry不允許重複，而value允許重複。

如果key相同，那麼就是覆寫，這個 後面會詳細說明。

3.1 Iterable

這個接口非常的重要，隻有實作了這個接口的資料接口，才能擁有疊代的能力。是以，這個接口，我個人更願意了解為疊代性接口，或者能否疊代接口。

能否疊代接口共有三個方法：

1. iterator()：這個接口傳回目前資料接口的一個疊代器。
2. forEach方法：這是jdk8中增加的預設方法，傳入一個Consumer，然後在方法内使用增強for循環對每一個資料使用Consumer定義的操作。
3. spliterator方法：我更願意稱這個操作是分割器，或者說周遊器更加準确。

OK，看到這裡，發現更加迷茫了，本來是了解Iterable，怎麼Iterable沒整明白，反而又多了三個新的玩意：

Iterator，Consumer，Spliterator

3.1.1 Iterator

抱着打破砂鍋問到底的态度，我們在繼續看看Iterator是什麼玩意。

通過檢視源碼發現，Iterator共有4個方法，其中forEachRemaining是在jdk8中增加的預設方法。

其他三個操作都是我們在使用疊代器時使用的方法。

使用疊代器的幾個步驟：

① 擷取疊代器對象

② 是否存在下一個疊代對象

③ 擷取并偏移疊代指針

當然，還有一個方法是remove方法。對于jdk提供的集合架構裡面的資料結構，都不能在周遊的時候進行删除操作。因為這存在一個悖論：

當疊代最後一個元素的時候，移除了一個元素。那麼此時，整個資料結構的長度是小于目前元素正在周遊的索引位置，那麼這是數組越界的問題。但是如果認為這個是數組越界了，目前周遊的元素卻能擷取到。

為了解決這一問題，在jdk提供的結合架構的資料結構裡面，使用一個開始周遊的版本号與目前資料結構的版本号驗證的一個過程，當發現目前版本号與開始周遊的版本号不一緻，就會抛出ConcurrentModificationException異常。

既然有這樣的驗證，那為什麼在疊代的時候卻能夠進行remove操作。

首先明确一點，周遊和疊代是兩個不同的概念。

舉個簡單的例子：

for循環是周遊。

增強for循環是疊代。

而上面使用while是疊代。

疊代與周遊最大的差別是疊代在循環過程中，可以動态的修改資料的長度。

這裡有一個很大的誤區，增強for循環也無法在循環中動态的修改資料的長度，為什麼認為增強for循環也是疊代器呢？

我們通過上述的示例代碼可以得出，作為疊代器，我們需要hasNext判斷能進行下一次疊代，使用next方法進行擷取目前元素，并且将疊代指針偏移到下一個疊代的元素。

是以，我們寫一個增強for循環，然後，在hasNext的方法打個斷點，不要忘記在for循環的地方也打上斷點。

通過這個驗證，可以看到，增強for循環也是疊代器，隻是沒有提供疊代器對象。而是隐式的調用疊代器的next方法，然後将值賦予增強for循環的定義的變量。

那麼，周遊是如何寫的呢？

在之前我們閱讀數組的源碼的時候，可以通過下标擷取數組元素。但是HashMap與數組的結構完全不同。可以說，對于HashMap隻能通過疊代周遊。當然，對于HashMap的key或者value或者entry，擷取到都是數組存儲的。這時候，就可以使用數組的周遊方式進行周遊了。

有點扯遠了，在次回到Iterator，在Iterator中有4個方法，我們已經看了next和hasNext的方法的作用。接下來看看其他的方法。

我們知道，在疊代的時候，可以實作動态修改資料長度。通過調用Iterator的remove方法實作的。在數組周遊的時候，如果動态的修改數組的長度，會抛出ConcurrentModificationException異常。

原因與數組周遊的原因相同。在HashMap中有一個版本号的概念，在周遊的時候，為了避免悖論，保證開始周遊的版本号與目前版本号相同，否則就會抛出ConcurrentModificationException異常。

而疊代器的remove方法中，會進行同步版本号。

不過，也不要想着，使用HashMap的remove方法，用完後使用Iterator的remove方法進行同步版本号。這樣也是行不通的，因為在Iterator的remove方法中，會先進行版本号驗證。

最後一個就是forEachRemaining方法了。這個方法是jdk8中增加的，為了支援lambda表達式的forEach方法。是一個預設方法。

3.1.2 Consumer

在Iterable中的第二個方法是支援lambda方法的，其參數是Consumer。

那麼，在這個小節中，我們主要搞明白，Consumer是什麼。

Consumer是一個接口，有FunctionalInterface注解修飾。也就是說，Consumer是一個函數接口。

其内部有兩個方法：accept和andThen。那麼，這兩個方法是幹什麼的呢？

首先，accept是一個接口方法，我們通過定義lambda函數，說明我們要做的操作。然後傳入一個對象，對這個對進行操作。其傳回值是空。

這樣說可能不是非常明确，請看例子：

import java.util.Arrays;
import java.util.function.Consumer;

/**
 * @author jiayq
 * @Date 2020-05-23
 */
public class Main {

    public static void main(String[] args) {

        Consumer<Integer> consumer = x -> x = x+1;
        Consumer<String> stringConsumer = new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.println(s);
            }
        };
        int x = 88;
        consumer.accept(x);
        System.out.println(x);
        stringConsumer.accept("hello");
        Consumer<People> peopleConsumer = people -> people.name = people.name + people.name;
        People people;
        peopleConsumer.accept(people = new People("hello "));
        System.out.println(people.name);

        Consumer<Integer> integerConsumer = y -> System.out.println(y);
        Arrays.asList(1,2,3).forEach(integerConsumer.andThen(integerConsumer));

        MyConsumer myConsumer = str -> str = str + str;
        MyInterface myInterface = string -> string = string + string;
    }

    @FunctionalInterface
    interface MyConsumer{
        void accept(String string);
    }

    interface MyInterface{
        void accept(String string);
    }

    static class People{
        String name;

        People(String s){
            name = s;
        }
    }

}      

說白了，Consumer就是隻有一個方法的接口的實作，在支援lambda函數之前，我們隻能通過匿名内部類的方式實作接口方法。但是因為Consumer的接口必須隻有一個為實作的接口方法，是以，我們實作的操作一定是這個接口方法。而lambda可以用更加直覺，更少的代碼實作。

接下來是andThen方法。因為Consumer的特殊性，必須有且隻有一個未實作的接口。如果需要執行的操作比較複雜，那麼整個實作的操作就非常的複雜，不容易閱讀。是以，為了更好的将操作進行劃分，就必須将複雜的操作進行抽取操作。而抽取的操作對應了多個方法，這時候，沖突就出現了。為了解決這個沖突，Consumer可以進行鍊化。可以将多個操作進行組合。這裡是類似裝飾器實作的鍊式操作。

操作的先後順序是調用者先執行，傳入的Consumer後執行。

還有一個點，函數接口和普通的接口是一樣的，加不加注解，程式都能實作想要的目的。隻不過，加了注解後，更加的清晰。而且對于某些特殊的架構，可以進行額外的處理。

3.1.3 Spliterator

Spliterator我将其了解為分割疊代器。

這個方法我們幾乎不會用到，是以，我不會深入讨論這個方法的實作。

在Iterable中的方法是這樣實作的，通過簡單檢視其注釋，大概是一個疊代其實作的方法，通過快速失敗進行疊代。

在HashMap中存在4個Spliterator，後面會詳細說明這些的操作。

3.2 Collection

Collection和Iteraotor的關系是這樣的：

Collection定義了集合資料結構的通用操作，比如描述集合的size，是否為空；以及集合查詢的是否包含；流相關的操作，流化，并行流化；集合操作，增加，删除，清空，更新等操作。

3.3 AbstractCollection

AbstractCollection要求子類必須實作iterator和size方法，其餘是給Collection接口提供了預設實作。我個人認為，這樣的是因為，繼承了Collection的資料結構，計算總數量各不相同，而且其疊代的方式也各不相同，是以這部分要求子類必須實作。而其他的方法則都是相同的邏輯。

Collection擷取資料結構的元素的時候，使用的是疊代器的next擷取元素并偏移，調用hasNext判斷是否可以進行下一次的疊代。這樣，抽象了數組，map，set等資料結構的疊代或者說周遊的操作。

是以，疊代器在Collection中是非常重要的一個基礎。

3.4 Set

在HashMap中一共有三個資料周遊器，分别是KeySet,ValueSet,EntrySet.

通過檢視各個疊代器的繼承關系，一個重要的差別是valueSet沒有實作Set的接口，也沒有繼承AbstrctSet抽象類。

這小節主要是閱讀Set接口。

這是Set的繼承關系圖。

看下Set主要定義了些什麼操作：

可以很清楚的看出，Set并沒有增加自己獨特的接口方法，都是實作器繼承類的方法：Collection和Iterable.

那麼，Set不可重複，是誰來保證呢？我們繼續往下看。

3.5 AbstractSet

AbstractSet繼承了AbstractCollection的同時，實作了Set接口。但是Set接口并沒有定義新的操作，是以Abstract隻是實作了自己的hashCode和equals和removeAll操作。并沒有定義新的操作，也沒有做很大的改動。

3.6 KeySet -> HashMap

終于到第一個正主了，KeySet應該是我們使用的最多的資料集了，一般都使用增強for循環周遊hashMap的key，然後使用map.get方法擷取key對應的value,然後在對value進行操作。

那麼，HashMap中的keySet是如何實作的呢？

通過檢視其代碼實作，keySet更像是一個代理或者說通路者，我們通過ketSet方法，獲得了一個set，然後使用增強for循環的文法糖，進行周遊HashMap的key.

而增強for循環用到的疊代器是HashMap中的keyIterator。

3.7 ValueSet > HashMap

說實話，工作學習中，我自己很少用到ValueSet這個資料集，甚至，在閱讀源碼之前都不知道有ValueSet這個資料集。但是有時候，我們确實需要周遊全體HashMap，然後根據HashMap的值進行一些操作或者運算，那麼，我認為此時使用valueSet資料集，比使用KeySet資料集可能更好一些。

3.8 EntrySet -> HashMap

EntrySet資料集也是比較少用的一個資料集，使用EntrySet可以擷取HashMap中的一個存儲節點。這個資料集與其他兩個資料集最大的差別就是，通過一次疊代，可以既擷取key，又擷取value.對于需要根據key和value同時進行運算或者操作的時候，可以減少一次疊代的次數。在一定程度上可以增加代碼密度。

4 HashMap 的疊代器

在1.3中我們讨論了HashMap的資料周遊，但是通過代碼檢視，資料周遊的資料集都是一個個的代理，實際指向了疊代器。接下來我們看看HashMap的疊代器。

在HashMap中實作了4個疊代器，其中一個是抽象的疊代器HashIterator,其餘的疊代器都是繼承了這個抽象的疊代器。

4.1 HashIterator

HashIterator沒有繼承任何借口和抽象類，這個抽象類隻是把HashMap的一些基本操作進行封裝，同時定義了，一個HashMap的疊代器進行疊代需要的一些屬性。

• expectedModCount是開始疊代的版本号
• index是目前疊代的哈希槽索引
• current是目前疊代的節點
• next是下一個疊代的節點

請注意這個抽象疊代器的構造方法，裡面設定了開始疊代的版本号為建立疊代器的HashMap的版本号。

同時将第一個疊代的節點移動到哈希桶或者說哈希槽的第一個節點。

這個do-while循環将index移動到了哈希槽的第一個槽位。

current和next是為了實作remove方法。一般情況下，我們調用next方法擷取節點元素，然後通過判斷節點元素的值是否符合條件，然後根據判斷結果進行remove。

但是，請不要忘記，在我們調用next的時候，已經将疊代指針移動到了下一個節點了即next，然後目前節點儲存在current。我們調用了remove操作，會重新定位疊代指針，也會重新建構節點存儲。說簡單點，就是節點的指針需要進行更新，需要做一個删除節點的操作。此時current的節點的指針就會被用于擷取目前元素的下一個元素，然後将目前元素的上一個元素的指針指向下一個元素。

打個比方，你從自行車鍊條中取下一個鍊條節點，需要将這個鍊條節點的前一個和後一個連起來。

在remove方法裡面，remove之前或進行版本驗證，remove之後，會同步版本号。

關于Iterator的4個方法：hasNext,next,remove，HashIterator已經實作了2個，隻剩下next方法未實作。不過它實作了nextNode方法。這個方法就是擷取并偏移節點的方法。

4.2 Iterator

是以，剩下的對應的Iterator隻需要擷取對應的節點的屬性即可。

這個抽象的很厲害，很巧妙。

代碼密度相當高。

5. Node

在HashMap中，一個個的哈希槽中存儲的是一個個的Node。

那麼，這個Node是什麼？

5.1 Node(連結清單)

衆所周知，HashMap在存儲的時候，有兩種存儲狀态：連結清單，紅黑樹。

連結清單實作繼承了Map.Entry接口。

連結清單的節點實作重寫了hashCode，對key和value進行hash異或。

5.2 TreeNode

這是一個紅黑樹。紅黑樹相當複雜，我自己都沒有了解透徹。

這裡放兩篇文章：

​​https://3g.163.com/news/article/FDA40U250511FQO9.html?from=history-back-list​​​​https://www.jianshu.com/p/e136ec79235c​​

提供一個動态示範的網站：

​​https://rbtree.phpisfuture.com/​​

6. Spliterator

其實吧，我開始閱讀源碼的時候，也在疑惑，我們有了疊代器，那麼還要什麼分割疊代器呢？

這個分割疊代器在數組中也存在。

深入的看到哪裡用了分割疊代器，才開始了解，分割疊代器的意義所在了。

6.1 Spliterator調用鍊

我們以KeySpliterator為例

在流的操作的時候，我們可能對元素比較多的HashMap或者資料結構，進行多線程處理。但是多線程處理存在并發問題，此時，就需要對資料結構中的元素進行分割，類似于資料分片，一個線程處理一片資料，這樣避免并發問題。

這就是分割疊代器存在的意義。

6.2 Spliterator屬性

• map:疊代對象
• current:目前節點
• index:該分割疊代器的開始哈希槽索引
• fence:該分割疊代器的結束哈希槽索引
• est:疊代節點的個數
• expectedModCount:開始疊代的版本号

6.3 Spliterator 操作

getFence初始化分割疊代器

estimateSize初始化并擷取分割疊代器的大小

6.4 KeySpliterator,ValueSpliterator,EntrySpliterator

trySplit嘗試分割。

forEachRemaining是forEach的函數操作。

tryAdvance和forEachmaining最大的差別是：tryAdvance隻會執行一次或者0次，而forEachMaining會對資料結構中全部的元素都執行。

characteristics暫時還不知道是幹什麼的。

7. HashMap 其他的常用的操作

7.1 初始化

預設的擴容因子是0.75，即，75%擴容。

HashMap在new的時候不會立即配置設定記憶體。

這裡需要注意，擴容擴的是哈希槽數組的容量，不是擴容整個HashMap的容量。

因為HashMap内部使用連結清單或者紅黑樹進行存儲資料，不存在容量限制。

隻有哈希槽是使用數組存儲，有擴容的問題。

如果在初始化的時候指定了大小，那麼會設定大小，擴容因子以及擴容門檻值。擴容的門檻值是指定大小+1.

當然，指定大小加1是一般情況下。

實際計算比這複雜：

7.2 put

在7.1中知道，new 了HashMap并不會立即配置設定記憶體，而是第一次put操作的時候，會配置設定記憶體。

HashMap通過key的hashCode計算哈希槽，使用的hashCode是擷取key的Object的hashCode,即記憶體位址相關的hashCode，然後将key的hashCode的高位和低位進行異或運算。異或運算後，hashCode在一定程度上具有了記憶體相關的hashCode的高位和地位特征。

如果哈希槽還未配置設定記憶體，那麼會調用resize進行配置設定記憶體。

使用無參構造，此時舊的大小和門檻值都是0.

預設大小是16，預設擴容門檻值是16*0.75=12

是以說，當單個哈希槽下的節點個數大于等于8的時候，就會進行樹化，從連結清單轉為紅黑樹。

++modCount版本号增加

resize當數量大于哈希槽庫容門檻值，進行擴容。

**HashMap的key和value可空。**這和數組不同。

7.3 連結清單化

我們從7.2知道了，當哈希槽節點數量大于等于8的時候，會進行樹化，如果紅黑樹的節點數量小于等于6的時候，會進行連結清單化。

7.4 hashCode

HashMap的hashCode是将所有的節點的hashCode累加後的hashCode

8. 總結