Java之怎么實(shí)現(xiàn)從Map到HashMap

本篇內(nèi)容主要講解“Java之怎么實(shí)現(xiàn)從Map到HashMap”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Java之怎么實(shí)現(xiàn)從Map到HashMap”吧!

 一、 Map

1.1 Map 接口

在 Java 中, Map 提供了鍵——值的映射關(guān)系。映射不能包含重復(fù)的鍵,并且每個(gè)鍵只能映射到一個(gè)值。

以 Map 鍵——值映射為基礎(chǔ)，java.util 提供了 HashMap（最常用）、 TreeMap、Hashtble、LinkedHashMap 等數(shù)據(jù)結(jié)構(gòu)。

衍生的幾種 Map 的主要特點(diǎn)：

•  HashMap：最常用的數(shù)據(jù)結(jié)構(gòu)。鍵和值之間通過(guò) Hash函數(shù) 來(lái)實(shí)現(xiàn)映射關(guān)系。當(dāng)進(jìn)行遍歷的 key 是無(wú)序的

•  TreeMap：使用紅黑樹(shù)構(gòu)建的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榧t黑樹(shù)的原理，可以很自然的對(duì) key 進(jìn)行排序，所以 TreeMap 的 key 遍歷時(shí)是默認(rèn)按照自然順序（升序）排列的。

•  LinkedHashMap: 保存了插入的順序。遍歷得到的記錄是按照插入順序的。

1.2 Hash 散列函數(shù)

Hash （散列函數(shù)）是把任意長(zhǎng)度的輸入通過(guò)散列算法變換成固定長(zhǎng)度的輸出。Hash 函數(shù)的返回值也稱為 哈希值 哈希碼 摘要或哈希。Hash作用如下圖所示:

Hash 函數(shù)可以通過(guò)選取適當(dāng)?shù)暮瘮?shù)，可以在時(shí)間和空間上取得較好平衡。

解決 Hash 的兩種方式：拉鏈法和線性探測(cè)法

1.3 鍵值關(guān)系的實(shí)現(xiàn)

interface Entry<K,V>

在 HashMap 中基于鏈表的實(shí)現(xiàn)

static class Node<K,V> implements Map.Entry<K,V> {          final int hash;          final K key;          V value;          Node<K,V> next;          Node(int hash, K key, V value, Node<K,V> next) {              this.hash = hash;              this.key = key;              this.value = value;              this.next = next;          }

用樹(shù)的方式實(shí)現(xiàn)：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {          TreeNode<K,V> parent;  // red-black tree links          TreeNode<K,V> left;          TreeNode<K,V> right;          TreeNode<K,V> prev;    // needed to unlink next upon deletion          boolean red;          TreeNode(int hash, K key, V val, Node<K,V> next) {              super(hash, key, val, next);          }

1.4 Map 約定的 API

1.4.1 Map 中約定的基礎(chǔ) API

基礎(chǔ)的增刪改查：

int size();  // 返回大小  boolean isEmpty(); // 是否為空  boolean containsKey(Object key); // 是否包含某個(gè)鍵  boolean containsValue(Object value); // 是否包含某個(gè)值  V get(Object key); // 獲取某個(gè)鍵對(duì)應(yīng)的值   V put(K key, V value); // 存入的數(shù)據(jù)   V remove(Object key); // 移除某個(gè)鍵  void putAll(Map<? extends K, ? extends V> m); //將將另一個(gè)集插入該集合中  void clear();  // 清除  Set<K> keySet(); //獲取 Map的所有的鍵返回為 Set集合  Collection<V> values(); //將所有的值返回為 Collection 集合  Set<Map.Entry<K, V>> entrySet(); // 將鍵值對(duì)映射為 Map.Entry，內(nèi)部類 Entry 實(shí)現(xiàn)了映射關(guān)系的實(shí)現(xiàn)。并且返回所有鍵值映射為 Set 集合。   boolean equals(Object o);   int hashCode(); // 返回 Hash 值  default boolean replace(K key, V oldValue, V newValue); // 替代操作  default V replace(K key, V value);

1.4.2 Map 約定的較為高級(jí)的 API

default V getOrDefault(Object key, V defaultValue); //當(dāng)獲取失敗時(shí)，用 defaultValue 替代。 default void forEach(BiConsumer<? super K, ? super V> action)  // 可用 lambda 表達(dá)式進(jìn)行更快捷的遍歷  default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function);   default V putIfAbsent(K key, V value);  default V computeIfAbsent(K key,              Function<? super K, ? extends V> mappingFunction); default V computeIfPresent(K key,              BiFunction<? super K, ? super V, ? extends V> remappingFunction);  default V compute(K key,              BiFunction<? super K, ? super V, ? extends V> remappingFunction)  default V merge(K key, V value,              BiFunction<? super V, ? super V, ? extends V> remappingFunction)

1.4.3 Map 高級(jí) API 的使用

•  getOrDefault() 當(dāng)這個(gè)通過(guò) key獲取值，對(duì)應(yīng)的 key 或者值不存在時(shí)返回默認(rèn)值，避免在使用過(guò)程中 null 出現(xiàn)，避免程序異常。

•  ForEach() 傳入 BiConsumer 函數(shù)式接口，表達(dá)的含義其實(shí)和 Consumer 一樣，都 accept 擁有方法，只是 BiConsumer 多了一個(gè) andThen() 方法，接收一個(gè)BiConsumer接口，先執(zhí)行本接口的，再執(zhí)行傳入的參數(shù)的 accept 方法。   

Map<String, String> map = new HashMap<>();       map.put("a", "1");       map.put("b", "2");       map.put("c", "3");       map.put("d", "4");       map.forEach((k, v) -> {           System.out.println(k+"-"+v);       });   }

更多的函數(shù)用法：

https://www.cnblogs.com/king0/p/runoob.com/java/java-hashmap.html

1.5 從 Map 走向 HashMap

HashMap 是 Map的一個(gè)實(shí)現(xiàn)類，也是 Map 最常用的實(shí)現(xiàn)類。

1.5.1 HashMap 的繼承關(guān)系

public class HashMap<K,V> extends AbstractMap<K,V>      implements Map<K,V>, Cloneable, Serializable

在 HashMap 的實(shí)現(xiàn)過(guò)程中，解決 Hash沖突的方法是拉鏈法。因此從原理來(lái)說(shuō) HashMap 的實(shí)現(xiàn)就是 數(shù)組 + 鏈表（數(shù)組保存鏈表的入口）。當(dāng)鏈表過(guò)長(zhǎng)，為了優(yōu)化查詢速率，HashMap 將鏈表轉(zhuǎn)化為紅黑樹(shù)（數(shù)組保存樹(shù)的根節(jié)點(diǎn)），使得查詢速率為 log(n)，而不是鏈表的 O(n)。

二、HashMap

/*   * @author  Doug Lea   * @author  Josh Bloch   * @author  Arthur van Hoff   * @author  Neal Gafter   * @see     Object#hashCode()   * @see     Collection   * @see     Map   * @see     TreeMap   * @see     Hashtable   * @since   1.2   */

首先 HashMap 由 Doug Lea 和 Josh Bloch 兩位大師的參與。同時(shí) Java 的 Collections 集合體系，并發(fā)框架 Doug Lea 也做出了不少貢獻(xiàn)。

2.1 基本原理

對(duì)于一個(gè)插入操作，首先將鍵通過(guò) Hash 函數(shù)轉(zhuǎn)化為數(shù)組的下標(biāo)。若該數(shù)組為空，直接創(chuàng)建節(jié)點(diǎn)放入數(shù)組中。若該數(shù)組下標(biāo)存在節(jié)點(diǎn),即 Hash 沖突，使用拉鏈法，生成一個(gè)鏈表插入。

引用圖片來(lái)自 https://blog.csdn.net/woshimaxiao1/article/details/83661464

如果存在 Hash 沖突，使用拉鏈法插入，我們可以在這個(gè)鏈表的頭部插入，也可以在鏈表的尾部插入，所以在 JDK 1.7 中使用了頭部插入的方法，JDK 1.8 后續(xù)的版本中使用尾插法。

JDK 1.7 使用頭部插入的可能依據(jù)是最近插入的數(shù)據(jù)是最常用的，但是頭插法帶來(lái)的問(wèn)題之一，在多線程會(huì)鏈表的復(fù)制會(huì)出現(xiàn)死循環(huán)。所以 JDK 1.8 之后采用的尾部插入的方法。關(guān)于這點(diǎn)，可以看：Java8之后，HashMap鏈表插入方式->為何要從頭插入改為尾插入

在 HashMap 中，前面說(shuō)到的 數(shù)組+鏈表 的數(shù)組的定義

transient Node<K,V>[] table;

鏈表的定義：

static class Node<K,V> implements Map.Entry<K,V>

2.1.2 提供的構(gòu)造函數(shù)

public HashMap() { // 空參        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted    }    public HashMap(int initialCapacity) { //帶有初始大小的，一般情況下，我們需要規(guī)劃好 HashMap 使用的大小，因?yàn)閷?duì)于一次擴(kuò)容操作，代價(jià)是非常的大的        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    public HashMap(int initialCapacity, float loadFactor); // 可以自定義負(fù)載因子  public HashMap(int initialCapacity, float loadFactor); // 可以自定義負(fù)載因子

三個(gè)構(gòu)造函數(shù)，都沒(méi)有完全的初始化 HashMap，當(dāng)我們第一次插入數(shù)據(jù)時(shí)，才進(jìn)行堆內(nèi)存的分配，這樣提高了代碼的響應(yīng)速度。

2.2 HashMap 中的 Hash函數(shù)定義

static final int hash(Object key) {          int h;          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 將 h 高 16 位和低 16 位 進(jìn)行異或操作。      }  // 采用 異或的原因：兩個(gè)進(jìn)行位運(yùn)算，在與或異或中只有異或到的 0 和 1 的概率是相同的，而&和|都會(huì)使得結(jié)果偏向0或者1。

這里可以看到，Map 的鍵可以為 null，且 hash 是一個(gè)特定的值 0。

Hash 的目的是獲取數(shù)組 table 的下標(biāo)。Hash 函數(shù)的目標(biāo)就是將數(shù)據(jù)均勻的分布在 table 中。

讓我們先看看如何通過(guò) hash 值得到對(duì)應(yīng)的數(shù)組下標(biāo)。第一種方法：hash%table.length()。但是除法操作在 CPU 中執(zhí)行比加法、減法、乘法慢的多，效率低下。第二種方法 table[(table.length - 1) & hash] 一個(gè)與操作一個(gè)減法，仍然比除法快。這里的約束條件為  table.length = 2^N。

table.length =16  table.length -1 = 15 1111 1111  //任何一個(gè)數(shù)與之與操作，獲取到這個(gè)數(shù)的低 8 位，其他位為 0

上面的例子可以讓我們獲取到對(duì)應(yīng)的下標(biāo),而 (h = key.hashCode()) ^ (h >>> 16) 讓高 16 也參與運(yùn)算，讓數(shù)據(jù)充分利用，一般情況下 table 的索引不會(huì)超過(guò) 216，所以高位的信息我們就直接拋棄了，^ (h >>> 16) 讓我們?cè)跀?shù)據(jù)量較少的情況下，也可以使用高位的信息。如果 table 的索引超過(guò) 216， hashCode() 的高 16 為 和 16 個(gè) 0 做異或得到的 Hash 也是公平的。

2.3 HashMap 的插入操作

上面我們已經(jīng)知道如果通過(guò) Hash 獲取到 對(duì)應(yīng)的 table 下標(biāo)，因此我們將對(duì)應(yīng)的節(jié)點(diǎn)加入到鏈表就完成了一個(gè) Map 的映射，的確 JDK1.7 中的 HashMap 實(shí)現(xiàn)就是這樣。讓我們看一看 JDK 為實(shí)現(xiàn)現(xiàn)實(shí)的 put 操作。

定位到 put() 操作。

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

可以看到 put 操作交給了 putVal 來(lái)進(jìn)行通用的實(shí)現(xiàn)。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);  //onlyIfAbsent  如果當(dāng)前位置已存在一個(gè)值，是否替換，false是替換，true是不替換  evict // 鉤子函數(shù)的參數(shù)，LinkedHashMap 中使用到，HashMap 中無(wú)意義。

2.3.1 putVal 的流程分析

其實(shí) putVal() 流程的函數(shù)非常的明了。這里挑了幾個(gè)關(guān)鍵步驟來(lái)引導(dǎo)。

是否第一次插入，true 調(diào)用 resizer() 進(jìn)行調(diào)整，其實(shí)此時(shí) resizer() 是進(jìn)行完整的初始化，之后直接賦值給對(duì)應(yīng)索引的位置。

if ((tab = table) == null || (n = tab.length) == 0) // 第一次 put 操作， tab 沒(méi)有分配內(nèi)存，通過(guò) redize() 方法分配內(nèi)存，開(kāi)始工作。             n = (tab = resize()).length;         if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null);

如果鏈表已經(jīng)轉(zhuǎn)化為樹(shù)，則使用樹(shù)的插入。

else if (p instanceof TreeNode)                  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

用遍歷的方式遍歷每個(gè) Node，如果遇到鍵相同，或者到達(dá)尾節(jié)點(diǎn)的next 指針將數(shù)據(jù)插入，記錄節(jié)點(diǎn)位置退出循環(huán)。若插入后鏈表長(zhǎng)度為 8 則調(diào)用 treeifyBin() 是否進(jìn)行樹(shù)的轉(zhuǎn)化 。

for (int binCount = 0; ; ++binCount) {                     if ((e = p.next) == null) {                         p.next = newNode(hash, key, value, null);                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                             treeifyBin(tab, hash);                         break;                     }                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         break;                     p = e;                 }

對(duì)鍵重復(fù)的操作：更新后返回舊值，同時(shí)還取決于onlyIfAbsent，普通操作中一般為 true，可以忽略。 

if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e); //鉤子函數(shù)，進(jìn)行后續(xù)其他操作，HashMap中為空，無(wú)任何操作。                return oldValue;            }

~

++modCount;     if (++size > threshold)         resize();     afterNodeInsertion(evict);     return null;

后續(xù)的數(shù)據(jù)維護(hù)。

2.3.2 modCount 的含義

fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制。當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生fail-fast事件。例如：當(dāng)某一個(gè)線程A通過(guò)iterator去遍歷某集合的過(guò)程中，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問(wèn)集合時(shí)，就會(huì)拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。一種多線程錯(cuò)誤檢查的方式，減少異常的發(fā)生。

一般情況下，多線程環(huán)境 我們使用 ConcurrentHashMap 來(lái)代替 HashMap。

2.4 resize() 函數(shù)

HashMap 擴(kuò)容的特點(diǎn)：默認(rèn)的table 表的大小事 16，threshold 為 12。負(fù)載因子 loadFactor .75，這些都是可以構(gòu)造是更改。以后擴(kuò)容都是 2 倍的方式增加。

至于為何是0.75 代碼的注釋中也寫(xiě)了原因，對(duì) Hash函數(shù)構(gòu)建了泊松分布模型，進(jìn)行了分析。

2.4.1 HashMap 預(yù)定義的一些參數(shù)

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  HashMap 的默認(rèn)大小。 為什么使用 1 <<4  static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量  static final float DEFAULT_LOAD_FACTOR = 0.75f; // 加載因子，擴(kuò)容使用  static final int UNTREEIFY_THRESHOLD = 6;//  樹(shù)結(jié)構(gòu)轉(zhuǎn)化為鏈表的閾值  static final int TREEIFY_THRESHOLD = 8;  //  鏈表轉(zhuǎn)化為樹(shù)結(jié)構(gòu)的閾值  static final int MIN_TREEIFY_CAPACITY = 64; // 鏈表轉(zhuǎn)變成樹(shù)之前，還會(huì)有一次判斷，只有數(shù)組長(zhǎng)度大于 64 才會(huì)發(fā)生轉(zhuǎn)換。這是為了避免在哈希表建立初期，多個(gè)鍵值對(duì)恰好被放入了同一個(gè)鏈表中而導(dǎo)致不必要的轉(zhuǎn)化。 // 定義的有關(guān)變量  int threshold;   // threshold表示當(dāng)HashMap的size大于threshold時(shí)會(huì)執(zhí)行resize操作

這些變量都是和 HashMap 的擴(kuò)容機(jī)制有關(guān)，將會(huì)在下文中用到。

2.4.2 resize() 方法解析 

Node<K,V>[] oldTab = table;       int oldCap = (oldTab == null) ? 0 : oldTab.length;        int oldThr = threshold;       int newCap, newThr = 0; // 定義了 舊表長(zhǎng)度、舊表閾值、新表長(zhǎng)度、新表閾值

if (oldCap > 0) {  // 插入過(guò)數(shù)據(jù)，參數(shù)不是初始化的            if (oldCap >= MAXIMUM_CAPACITY) {  // 如果舊的表長(zhǎng)度大于 1 << 30;                threshold = Integer.MAX_VALUE; // threshold 設(shè)置 Integer 的最大值。也就是說(shuō)我們可以插入 Integer.MAX_VALUE 個(gè)數(shù)據(jù)                return oldTab; // 直接返回舊表的長(zhǎng)度，因?yàn)楸淼南聵?biāo)索引無(wú)法擴(kuò)大了。             }            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //                      oldCap >= DEFAULT_INITIAL_CAPACITY)  //新表的長(zhǎng)度為舊表的長(zhǎng)度的 2 倍。               newThr = oldThr << 1; // double threshold 新表的閾值為同時(shí)為舊表的兩倍        }        else if (oldThr > 0) //   public HashMap(int initialCapacity, float loadFactor)   中的  this.threshold = tableSizeFor(initialCapacity);  給正確的位置              newCap = oldThr;        else {               // zero initial threshold signifies using defaults ，如果調(diào)用了其他兩個(gè)構(gòu)造函數(shù)，則下面代碼初始化。因?yàn)樗麄兌紱](méi)有對(duì)其 threshold 設(shè)置，默認(rèn)為 0，           newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        if (newThr == 0) { // 修正 threshold，例如上面的   else if (oldThr > 0)  部分就沒(méi)有設(shè)置。            float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }        threshold = newThr;        @SuppressWarnings({"rawtypes","unchecked"})

當(dāng)一些參數(shù)設(shè)置正確后便開(kāi)始擴(kuò)容。 

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

當(dāng)擴(kuò)容完畢之后，自然就是將原表中的數(shù)據(jù)搬到新的表中。下面代碼完成了該任務(wù)。

if (oldTab != null) {     for (int j = 0; j < oldCap; ++j) {        ....      }  }

如何正確的，快速的擴(kuò)容調(diào)整每個(gè)鍵值節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)？第一種方法：遍歷節(jié)點(diǎn)再使用 put() 加入一遍，這種方法實(shí)現(xiàn)，但是效率低下。第二種，我們手動(dòng)組裝好鏈表，加入到相應(yīng)的位置。顯然第二種比第一種高效，因?yàn)榈谝环N put() 還存在其他不屬于這種情況的判斷，例如重復(fù)鍵的判斷等。

練手項(xiàng)目，學(xué)習(xí)強(qiáng)化，點(diǎn)擊這里

所以 JDK 1.8 也使用了第二種方法。我們可以繼續(xù)使用e.hash & (newCap - 1)找到對(duì)應(yīng)的下標(biāo)位置,對(duì)于舊的鏈表，執(zhí)行e.hash & (newCap - 1) 操作，只能產(chǎn)生兩個(gè)不同的索引。一個(gè)保持原來(lái)的索引不變，另一個(gè)變?yōu)?原來(lái)索引 + oldCap(因?yàn)?newCap 的加入產(chǎn)生導(dǎo)致索引的位數(shù)多了 1 位，即就是最左邊的一個(gè)，且該位此時(shí)結(jié)果為 1，所以相當(dāng)于 原來(lái)索引 + oldCap)。所以可以使用 if ((e.hash & oldCap) == 0) 來(lái)確定出索引是否來(lái)變化。

因此這樣我們就可以將原來(lái)的鏈表拆分為兩個(gè)新的鏈表，然后加入到對(duì)應(yīng)的位置。為了高效，我們手動(dòng)的組裝好鏈表再存儲(chǔ)到相應(yīng)的下標(biāo)位置上。

oldCap  = 16  newCap  = 32  hash       : 0001 1011  oldCap-1   : 0000 1111  結(jié)果為     :  0000 1011  對(duì)應(yīng)的索引的 11  -------------------------  e.hash & oldCap 則定于 1,則需要進(jìn)行調(diào)整索引  oldCap  = 16  hash       : 0001 1011   newCap-1   : 0001 1111  結(jié)果為     :  0001 1011  相當(dāng)于 1011 + 1 0000 原來(lái)索引 + newCap

for (int j = 0; j < oldCap; ++j)  // 處理每個(gè)鏈表

特殊條件處理

Node<K,V> e;                  if ((e = oldTab[j]) != null) {                      oldTab[j] = null;                      if (e.next == null)  // 該 鏈表只有一個(gè)節(jié)點(diǎn)，那么直接復(fù)制到對(duì)應(yīng)的位置，下標(biāo)由 e.hash & (newCap - 1) 確定                          newTab[e.hash & (newCap - 1)] = e;                      else if (e instanceof TreeNode) // 若是 樹(shù)，該給樹(shù)的處理程序                          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

普通情況處理：     

else { // preserve order                          Node<K,V> loHead = null, loTail = null;  // 構(gòu)建原來(lái)索引位置 的鏈表，需要的指針                          Node<K,V> hiHead = null, hiTail = null; // 構(gòu)建 原來(lái)索引 + oldCap 位置 的鏈表需要的指針                          Node<K,V> next;                          do {                              next = e.next;                              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); // 將原來(lái)的鏈表劃分兩個(gè)鏈表                          if (loTail != null) { // 將鏈表寫(xiě)入到相應(yīng)的位置                             loTail.next = null;                              newTab[j] = loHead;                          }                          if (hiTail != null) {                              hiTail.next = null;                              newTab[j + oldCap] = hiHead;                          }                      }

到此 resize() 方法的邏輯完成了。總的來(lái)說(shuō) resizer() 完成了 HashMap 完整的初始化，分配內(nèi)存和后續(xù)的擴(kuò)容維護(hù)工作。

2.5 remove 解析 

public V remove(Object key) {         Node<K,V> e;         return (e = removeNode(hash(key), key, null, false, true)) == null ?             null : e.value;     }

將 remove 刪除工作交給內(nèi)部函數(shù) removeNode() 來(lái)實(shí)現(xiàn)。

final Node<K,V> removeNode(int hash, Object key, Object value,                                 boolean matchValue, boolean movable) {          Node<K,V>[] tab; Node<K,V> p; int n, index;          if ((tab = table) != null && (n = tab.length) > 0 &&              (p = tab[index = (n - 1) & hash]) != null) {  // 獲取索引，             Node<K,V> node = null, e; K k; V v;              if (p.hash == hash &&                    ((k = p.key) == key || (key != null && key.equals(k)))) // 判斷索引處的值是不是想要的結(jié)果                  node = p;                else if ((e = p.next) != null) { // 交給樹(shù)的查找算法                  if (p instanceof TreeNode)                      node = ((TreeNode<K,V>)p).getTreeNode(hash, key);                  else {                      do { // 遍歷查找                          if (e.hash == hash &&                              ((k = e.key) == key ||                               (key != null && key.equals(k)))) {                              node = e;                              break;                          }                          p = e;                      } while ((ee = e.next) != null);                  }              }              if (node != null && (!matchValue || (v = node.value) == value ||                                   (value != null && value.equals(v)))) {                  if (node instanceof TreeNode)  //樹(shù)的刪除                      ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);                  else if (node == p) // 修復(fù)鏈表，鏈表的刪除操作                      tab[index] = node.next;                   else                      p.next = node.next;                    ++modCount;                  --size;                  afterNodeRemoval(node);                  return node;              }          }          return null;      }

三、 HashMap 從鏈表到紅黑樹(shù)的轉(zhuǎn)變

如果鏈表的長(zhǎng)度（沖突的節(jié)點(diǎn)數(shù)）已經(jīng)達(dá)到8個(gè)，此時(shí)會(huì)調(diào)用 treeifyBin() ，treeifyBin() 首先判斷當(dāng)前hashMap 的 table的長(zhǎng)度，如果不足64，只進(jìn)行resize，擴(kuò)容table，如果達(dá)到64，那么將沖突的存儲(chǔ)結(jié)構(gòu)為紅黑樹(shù)。在源碼還有這樣的一個(gè)字段。

static final int UNTREEIFY_THRESHOLD = 6;   // 這樣表明了從紅黑樹(shù)轉(zhuǎn)化為鏈表的閾值為 6，為何同樣不是 8 那？   //如果插入和刪除都在 8 附近，將多二者相互轉(zhuǎn)化將浪費(fèi)大量的時(shí)間，對(duì)其性能影響。   //如果是的二者轉(zhuǎn)化的操作不平衡，偏向一方，則可以避免此類影響。

3.1 紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {        TreeNode<K,V> parent;  // red-black tree links        TreeNode<K,V> left;        TreeNode<K,V> right;        TreeNode<K,V> prev;    // 刪除后需要取消鏈接，指向前一個(gè)節(jié)點(diǎn)（原鏈表中的前一個(gè)節(jié)點(diǎn)）        boolean red;    }

因?yàn)?繼承了 LinkedHashMap.Entry<K,V> ，所以存儲(chǔ)的數(shù)據(jù)還是在Entry 中：

static class Node<K,V> implements Map.Entry<K,V> {       final int hash;       final K key;       V value;       Node<K,V> next;       Node(int hash, K key, V value, Node<K,V> next) {           this.hash = hash;           this.key = key;           this.value = value;           this.next = next;       }  }

3.2 承上啟下的 treeifyBin()

treeifyBin() 決定了一個(gè)鏈表何時(shí)轉(zhuǎn)化為一個(gè)紅黑樹(shù)。treeifyBin() 有兩種格式：

final void treeifyBin(Node<K,V>[] tab, int hash);   final void treeify(Node<K,V>[] tab);

final void treeifyBin(Node<K,V>[] tab, int hash) { // 簡(jiǎn)單的 Node 修改為 TreeNode，同時(shí)維護(hù)了 prev 屬性。        int n, index; Node<K,V> e;         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)             resize();         else if ((e = tab[index = (n - 1) & hash]) != null) {             TreeNode<K,V> hd = null, tl = null;             do {                 TreeNode<K,V> p = replacementTreeNode(e, null);                if (tl == null)                     hd = p;                 else {                     p.prev = tl;                     tl.next = p;                 }                 tl = p;             } while ((ee = e.next) != null);             if ((tab[index] = hd) != null)                 hd.treeify(tab);  // 真正生成紅黑樹(shù)的         }     }

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {      return new TreeNode<>(p.hash, p.key, p.value, next);  } // 實(shí)現(xiàn) Node 鏈表節(jié)點(diǎn)到 TreeNode 節(jié)點(diǎn)的轉(zhuǎn)化。

下面函數(shù)真正實(shí)現(xiàn)了鏈表的紅黑樹(shù)的轉(zhuǎn)變。首先構(gòu)建一個(gè)標(biāo)準(zhǔn)查詢二叉樹(shù)，然后在標(biāo)準(zhǔn)查詢二叉樹(shù)然后調(diào)整為一個(gè)紅黑樹(shù)。而 balanceInsertion() 實(shí)現(xiàn)了調(diào)整。     

/**          * Forms tree of the nodes linked from this node.          */         final void treeify(Node<K,V>[] tab) {             TreeNode<K,V> root = null;             for (TreeNode<K,V> x = this, next; x != null; x = next) {                 next = (TreeNode<K,V>)x.next;                 xx.left = x.right = null;                 if (root == null) { // 第一次轉(zhuǎn)化過(guò)程，將鏈表的頭節(jié)點(diǎn)作為根節(jié)點(diǎn)。                     x.parent = null;                     x.red = false;  // 紅黑樹(shù)的定義 根節(jié)點(diǎn)必須為黑色                     root = x;                 }                 else {                     K k = x.key;                     int h = x.hash;                     Class<?> kc = null;                     for (TreeNode<K,V> p = root;;) {                         int dir, ph;                         K ppk = p.key;                         if ((pph = p.hash) > h)  //// 通過(guò) Hash 的大小來(lái)確定插入順序                             dir = -1; // dir 大小順序的標(biāo)識(shí)                         else if (ph < h)                             dir = 1;                          else if ((kc == null && //當(dāng) 兩個(gè) Hash 的值相同，進(jìn)行特殊的方法，確定大小。                                   (kc = comparableClassFor(k)) == null) || // Returns x's Class if it is of the form "class C implements Comparable ", else null. 如果 key類的 源碼書(shū)寫(xiě)格式為 C implement Comparable<C> 那么返回該類類型 C, 如果間接實(shí)現(xiàn)也不行。 如果是 String 類型，直接返回 String.class                                  (dir = compareComparables(kc, k, pk)) == 0)   //    ((Comparable)k).compareTo(pk)); 強(qiáng)制轉(zhuǎn)換后進(jìn)行對(duì)比，若 dir == 0,則 tieBreakOrder()，繼續(xù)仲裁                              dir = tieBreakOrder(k, pk);  // 首先通過(guò)二者的類類型進(jìn)行比較，如果相等的話，使用 (System.identityHashCode(a) <= System.identityHashCode(b) 使用原始的 hashcode，不是重寫(xiě)的在對(duì)比。                         TreeNode<K,V> xp = p; // 遍歷的，上一個(gè)節(jié)點(diǎn)                         if ((p = (dir <= 0) ? p.left : p.right) == null) { //通過(guò) dir，將 p 向下查找，直到 p 為 null，找到一個(gè)插入時(shí)機(jī)                             x.parent = xp;                             if (dir <= 0)                                 xxp.left = x;                             else                                 xxp.right = x;                             root = balanceInsertion(root, x); //進(jìn)行二叉樹(shù)的調(diào)整                             break;                         }                     }                 }             }             moveRootToFront(tab, root);         }

3.3 將一個(gè)二叉樹(shù)轉(zhuǎn)化為紅黑樹(shù)的操作-balanceInsertion()

當(dāng)紅黑樹(shù)中新增節(jié)點(diǎn)的時(shí)候需要調(diào)用balanceInsertion方法來(lái)保證紅黑樹(shù)的特性。

如果想要了解紅黑樹(shù)的插入過(guò)程那么必須對(duì)紅黑樹(shù)的性質(zhì)有一個(gè)較為清晰的了解。

紅黑樹(shù)的性質(zhì)：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2.  每個(gè)結(jié)點(diǎn)或是紅色的，或是黑色的

3.  根節(jié)點(diǎn)是黑色的

4.  每個(gè)葉結(jié)點(diǎn)（NIL）是黑色的

5.  如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)兒子都是黑色的。

6.  對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其葉子結(jié)點(diǎn)構(gòu)成的所有路徑上的黑結(jié)點(diǎn)個(gè)數(shù)相同。 

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,                                                      TreeNode<K,V> x) {              x.red = true;  // 插入的子節(jié)點(diǎn)必須為 red              for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //// x 當(dāng)前處理節(jié)點(diǎn) xp父節(jié)點(diǎn) xpp祖父節(jié)點(diǎn) xppl祖父左節(jié)點(diǎn) xppr 祖父右節(jié)點(diǎn)                  if ((xxp = x.parent) == null) { // 如果 當(dāng)前處理節(jié)點(diǎn)為根節(jié)點(diǎn)，滿足紅黑樹(shù)的性質(zhì)，結(jié)束循環(huán)                      x.red = false;                      return x;                  }                  else if (!xp.red || (xpxpp = xp.parent) == null)                       return root;                  if (xp == (xppxppl = xpp.left)) {                      if ((xppxppr = xpp.right) != null && xppr.red) {                          xppr.red = false;                          xp.red = false;                          xpp.red = true;                          x = xpp;                      }                      else {                          if (x == xp.right) {                              root = rotateLeft(root, x = xp);                              xpp = (xxp = x.parent) == null ? null : xp.parent;                          }                          if (xp != null) {                              xp.red = false;                              if (xpp != null) {                                  xpp.red = true;                                  root = rotateRight(root, xpp);                              }                          }                      }                  }                  else {                      if (xppl != null && xppl.red) {                          xppl.red = false;                          xp.red = false;                          xpp.red = true;                          x = xpp;                      }                      else {                          if (x == xp.left) {                              root = rotateRight(root, x = xp);                              xpp = (xxp = x.parent) == null ? null : xp.parent;                          }                          if (xp != null) {                              xp.red = false;                              if (xpp != null) {                                  xpp.red = true;                                  root = rotateLeft(root, xpp);                              }                          }                      }                  }              }          }

TreeNode 紅黑樹(shù)總結(jié)

TreeNode 完整的實(shí)現(xiàn)了一套紅黑樹(shù)的增刪改查的規(guī)則。實(shí)現(xiàn)參考了《算法導(dǎo)論》

/* ------------------------------------------------------------ */  // Red-black tree methods, all adapted from CLR

這里推薦一個(gè)紅黑樹(shù)動(dòng)畫(huà)演示網(wǎng)站 https://rbtree.phpisfuture.com/

紅黑樹(shù)是一個(gè)不嚴(yán)格的平衡二叉查找樹(shù)，高度近似 log(N)。

四、HashMap 的擴(kuò)展

Map中 key 有一個(gè)性質(zhì)，就是 key 不能重復(fù)，而 Java Set 的含義：集合中不能有重復(fù)的元素。HashMap 的實(shí)現(xiàn)已經(jīng)足夠的優(yōu)秀。那么我們是否可以用 key 的性質(zhì)來(lái)實(shí)現(xiàn) Set ？的確 JDK 中的 HashSet 就是這樣做的。

public class HashSet<E>      extends AbstractSet<E>      implements Set<E>, Cloneable, java.io.Serializable  {      private transient HashMap<E,Object> map;        // Dummy value to associate with an Object in the backing Map      private static final Object PRESENT = new Object();  }

PRESENT 就是存進(jìn) Map 中的 value，而 key 正是 Set 語(yǔ)義的實(shí)現(xiàn)。而且可以判斷出 HashSet 中是允許存入 Null 值的。

到此，相信大家對(duì)“Java之怎么實(shí)現(xiàn)從Map到HashMap”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！