溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“Java之怎么實現從Map到HashMap”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java之怎么實現從Map到HashMap”吧!
一、 Map
1.1 Map 接口
在 Java 中, Map 提供了鍵——值的映射關系。映射不能包含重復的鍵,并且每個鍵只能映射到一個值。
以 Map 鍵——值映射為基礎，java.util 提供了 HashMap（最常用）、 TreeMap、Hashtble、LinkedHashMap 等數據結構。
衍生的幾種 Map 的主要特點：
HashMap：最常用的數據結構。鍵和值之間通過 Hash函數 來實現映射關系。當進行遍歷的 key 是無序的
TreeMap：使用紅黑樹構建的數據結構，因為紅黑樹的原理，可以很自然的對 key 進行排序，所以 TreeMap 的 key 遍歷時是默認按照自然順序（升序）排列的。
LinkedHashMap: 保存了插入的順序。遍歷得到的記錄是按照插入順序的。
1.2 Hash 散列函數
Hash （散列函數）是把任意長度的輸入通過散列算法變換成固定長度的輸出。Hash 函數的返回值也稱為 哈希值 哈希碼 摘要或哈希。Hash作用如下圖所示:
Hash 函數可以通過選取適當的函數，可以在時間和空間上取得較好平衡。
解決 Hash 的兩種方式：拉鏈法和線性探測法
1.3 鍵值關系的實現
interface Entry<K,V>
在 HashMap 中基于鏈表的實現
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; }用樹的方式實現：
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 中約定的基礎 API
基礎的增刪改查：
int size(); // 返回大小 boolean isEmpty(); // 是否為空 boolean containsKey(Object key); // 是否包含某個鍵 boolean containsValue(Object value); // 是否包含某個值 V get(Object key); // 獲取某個鍵對應的值 V put(K key, V value); // 存入的數據 V remove(Object key); // 移除某個鍵 void putAll(Map<? extends K, ? extends V> m); //將將另一個集插入該集合中 void clear(); // 清除 Set<K> keySet(); //獲取 Map的所有的鍵返回為 Set集合 Collection<V> values(); //將所有的值返回為 Collection 集合 Set<Map.Entry<K, V>> entrySet(); // 將鍵值對映射為 Map.Entry，內部類 Entry 實現了映射關系的實現。并且返回所有鍵值映射為 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 約定的較為高級的 API
default V getOrDefault(Object key, V defaultValue); //當獲取失敗時，用 defaultValue 替代。 default void forEach(BiConsumer<? super K, ? super V> action) // 可用 lambda 表達式進行更快捷的遍歷 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 高級 API 的使用
getOrDefault() 當這個通過 key獲取值，對應的 key 或者值不存在時返回默認值，避免在使用過程中 null 出現，避免程序異常。
ForEach() 傳入 BiConsumer 函數式接口，表達的含義其實和 Consumer 一樣，都 accept 擁有方法，只是 BiConsumer 多了一個 andThen() 方法，接收一個BiConsumer接口，先執行本接口的，再執行傳入的參數的 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); }); }更多的函數用法：
https://www.cnblogs.com/king0/p/runoob.com/java/java-hashmap.html
1.5 從 Map 走向 HashMap
HashMap 是 Map的一個實現類，也是 Map 最常用的實現類。
1.5.1 HashMap 的繼承關系
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
在 HashMap 的實現過程中，解決 Hash沖突的方法是拉鏈法。因此從原理來說 HashMap 的實現就是 數組 + 鏈表（數組保存鏈表的入口）。當鏈表過長，為了優化查詢速率，HashMap 將鏈表轉化為紅黑樹（數組保存樹的根節點），使得查詢速率為 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 兩位大師的參與。同時 Java 的 Collections 集合體系，并發框架 Doug Lea 也做出了不少貢獻。
2.1 基本原理
對于一個插入操作，首先將鍵通過 Hash 函數轉化為數組的下標。若該數組為空，直接創建節點放入數組中。若該數組下標存在節點,即 Hash 沖突，使用拉鏈法，生成一個鏈表插入。
引用圖片來自 https://blog.csdn.net/woshimaxiao1/article/details/83661464
如果存在 Hash 沖突，使用拉鏈法插入，我們可以在這個鏈表的頭部插入，也可以在鏈表的尾部插入，所以在 JDK 1.7 中使用了頭部插入的方法，JDK 1.8 后續的版本中使用尾插法。
JDK 1.7 使用頭部插入的可能依據是最近插入的數據是最常用的，但是頭插法帶來的問題之一，在多線程會鏈表的復制會出現死循環。所以 JDK 1.8 之后采用的尾部插入的方法。關于這點，可以看：Java8之后，HashMap鏈表插入方式->為何要從頭插入改為尾插入
在 HashMap 中，前面說到的 數組+鏈表 的數組的定義
transient Node<K,V>[] table;
鏈表的定義：
static class Node<K,V> implements Map.Entry<K,V>
2.1.2 提供的構造函數
public HashMap() { // 空參 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(int initialCapacity) { //帶有初始大小的，一般情況下，我們需要規劃好 HashMap 使用的大小，因為對于一次擴容操作，代價是非常的大的 this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor); // 可以自定義負載因子 public HashMap(int initialCapacity, float loadFactor); // 可以自定義負載因子三個構造函數，都沒有完全的初始化 HashMap，當我們第一次插入數據時，才進行堆內存的分配，這樣提高了代碼的響應速度。
2.2 HashMap 中的 Hash函數定義
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 將 h 高 16 位和低 16 位 進行異或操作。 } // 采用 異或的原因：兩個進行位運算，在與或異或中只有異或到的 0 和 1 的概率是相同的，而&和|都會使得結果偏向0或者1。這里可以看到，Map 的鍵可以為 null，且 hash 是一個特定的值 0。
Hash 的目的是獲取數組 table 的下標。Hash 函數的目標就是將數據均勻的分布在 table 中。
讓我們先看看如何通過 hash 值得到對應的數組下標。第一種方法：hash%table.length()。但是除法操作在 CPU 中執行比加法、減法、乘法慢的多，效率低下。第二種方法 table[(table.length - 1) & hash] 一個與操作一個減法，仍然比除法快。這里的約束條件為 table.length = 2^N。
table.length =16 table.length -1 = 15 1111 1111 //任何一個數與之與操作，獲取到這個數的低 8 位，其他位為 0
上面的例子可以讓我們獲取到對應的下標,而 (h = key.hashCode()) ^ (h >>> 16) 讓高 16 也參與運算，讓數據充分利用，一般情況下 table 的索引不會超過 216，所以高位的信息我們就直接拋棄了，^ (h >>> 16) 讓我們在數據量較少的情況下，也可以使用高位的信息。如果 table 的索引超過 216， hashCode() 的高 16 為 和 16 個 0 做異或得到的 Hash 也是公平的。
2.3 HashMap 的插入操作
上面我們已經知道如果通過 Hash 獲取到 對應的 table 下標，因此我們將對應的節點加入到鏈表就完成了一個 Map 的映射，的確 JDK1.7 中的 HashMap 實現就是這樣。讓我們看一看 JDK 為實現現實的 put 操作。
定位到 put() 操作。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }可以看到 put 操作交給了 putVal 來進行通用的實現。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict); //onlyIfAbsent 如果當前位置已存在一個值，是否替換，false是替換，true是不替換 evict // 鉤子函數的參數，LinkedHashMap 中使用到，HashMap 中無意義。
2.3.1 putVal 的流程分析
其實 putVal() 流程的函數非常的明了。這里挑了幾個關鍵步驟來引導。
是否第一次插入，true 調用 resizer() 進行調整，其實此時 resizer() 是進行完整的初始化，之后直接賦值給對應索引的位置。
if ((tab = table) == null || (n = tab.length) == 0) // 第一次 put 操作， tab 沒有分配內存，通過 redize() 方法分配內存，開始工作。 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
如果鏈表已經轉化為樹，則使用樹的插入。
else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
用遍歷的方式遍歷每個 Node，如果遇到鍵相同，或者到達尾節點的next 指針將數據插入，記錄節點位置退出循環。若插入后鏈表長度為 8 則調用 treeifyBin() 是否進行樹的轉化 。
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; }對鍵重復的操作：更新后返回舊值，同時還取決于onlyIfAbsent，普通操作中一般為 true，可以忽略。
if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); //鉤子函數，進行后續其他操作，HashMap中為空，無任何操作。 return oldValue; }~
++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null;
后續的數據維護。
2.3.2 modCount 的含義
fail-fast 機制是java集合(Collection)中的一種錯誤機制。當多個線程對同一個集合的內容進行操作時，就可能會產生fail-fast事件。例如：當某一個線程A通過iterator去遍歷某集合的過程中，若該集合的內容被其他線程所改變了；那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產生fail-fast事件。一種多線程錯誤檢查的方式，減少異常的發生。
一般情況下，多線程環境 我們使用 ConcurrentHashMap 來代替 HashMap。
2.4 resize() 函數
HashMap 擴容的特點：默認的table 表的大小事 16，threshold 為 12。負載因子 loadFactor .75，這些都是可以構造是更改。以后擴容都是 2 倍的方式增加。
至于為何是0.75 代碼的注釋中也寫了原因，對 Hash函數構建了泊松分布模型，進行了分析。
2.4.1 HashMap 預定義的一些參數
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap 的默認大小。 為什么使用 1 <<4 static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 加載因子，擴容使用 static final int UNTREEIFY_THRESHOLD = 6;// 樹結構轉化為鏈表的閾值 static final int TREEIFY_THRESHOLD = 8; // 鏈表轉化為樹結構的閾值 static final int MIN_TREEIFY_CAPACITY = 64; // 鏈表轉變成樹之前，還會有一次判斷，只有數組長度大于 64 才會發生轉換。這是為了避免在哈希表建立初期，多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化。 // 定義的有關變量 int threshold; // threshold表示當HashMap的size大于threshold時會執行resize操作
這些變量都是和 HashMap 的擴容機制有關，將會在下文中用到。
2.4.2 resize() 方法解析
Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 定義了 舊表長度、舊表閾值、新表長度、新表閾值
if (oldCap > 0) { // 插入過數據，參數不是初始化的 if (oldCap >= MAXIMUM_CAPACITY) { // 如果舊的表長度大于 1 << 30; threshold = Integer.MAX_VALUE; // threshold 設置 Integer 的最大值。也就是說我們可以插入 Integer.MAX_VALUE 個數據 return oldTab; // 直接返回舊表的長度，因為表的下標索引無法擴大了。 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // oldCap >= DEFAULT_INITIAL_CAPACITY) //新表的長度為舊表的長度的 2 倍。 newThr = oldThr << 1; // double threshold 新表的閾值為同時為舊表的兩倍 } else if (oldThr > 0) // public HashMap(int initialCapacity, float loadFactor) 中的 this.threshold = tableSizeFor(initialCapacity); 給正確的位置 newCap = oldThr; else { // zero initial threshold signifies using defaults ，如果調用了其他兩個構造函數，則下面代碼初始化。因為他們都沒有對其 threshold 設置，默認為 0， newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { // 修正 threshold，例如上面的 else if (oldThr > 0) 部分就沒有設置。 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"})當一些參數設置正確后便開始擴容。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
當擴容完畢之后，自然就是將原表中的數據搬到新的表中。下面代碼完成了該任務。
if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { .... } }如何正確的，快速的擴容調整每個鍵值節點對應的下標？第一種方法：遍歷節點再使用 put() 加入一遍，這種方法實現，但是效率低下。第二種，我們手動組裝好鏈表，加入到相應的位置。顯然第二種比第一種高效，因為第一種 put() 還存在其他不屬于這種情況的判斷，例如重復鍵的判斷等。
練手項目，學習強化，點擊這里
所以 JDK 1.8 也使用了第二種方法。我們可以繼續使用e.hash & (newCap - 1)找到對應的下標位置,對于舊的鏈表，執行e.hash & (newCap - 1) 操作，只能產生兩個不同的索引。一個保持原來的索引不變，另一個變為 原來索引 + oldCap(因為 newCap 的加入產生導致索引的位數多了 1 位，即就是最左邊的一個，且該位此時結果為 1，所以相當于 原來索引 + oldCap)。所以可以使用 if ((e.hash & oldCap) == 0) 來確定出索引是否來變化。
因此這樣我們就可以將原來的鏈表拆分為兩個新的鏈表，然后加入到對應的位置。為了高效，我們手動的組裝好鏈表再存儲到相應的下標位置上。
oldCap = 16 newCap = 32 hash : 0001 1011 oldCap-1 : 0000 1111 結果為 : 0000 1011 對應的索引的 11 ------------------------- e.hash & oldCap 則定于 1,則需要進行調整索引 oldCap = 16 hash : 0001 1011 newCap-1 : 0001 1111 結果為 : 0001 1011 相當于 1011 + 1 0000 原來索引 + newCap
for (int j = 0; j < oldCap; ++j) // 處理每個鏈表
特殊條件處理
Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) // 該 鏈表只有一個節點，那么直接復制到對應的位置，下標由 e.hash & (newCap - 1) 確定 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 若是 樹，該給樹的處理程序 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);普通情況處理：
else { // preserve order Node<K,V> loHead = null, loTail = null; // 構建原來索引位置 的鏈表，需要的指針 Node<K,V> hiHead = null, hiTail = null; // 構建 原來索引 + 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); // 將原來的鏈表劃分兩個鏈表 if (loTail != null) { // 將鏈表寫入到相應的位置 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } }到此 resize() 方法的邏輯完成了。總的來說 resizer() 完成了 HashMap 完整的初始化，分配內存和后續的擴容維護工作。
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 刪除工作交給內部函數 removeNode() 來實現。
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)))) // 判斷索引處的值是不是想要的結果 node = p; else if ((e = p.next) != null) { // 交給樹的查找算法 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) //樹的刪除 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) // 修復鏈表，鏈表的刪除操作 tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }三、 HashMap 從鏈表到紅黑樹的轉變
如果鏈表的長度（沖突的節點數）已經達到8個，此時會調用 treeifyBin() ，treeifyBin() 首先判斷當前hashMap 的 table的長度，如果不足64，只進行resize，擴容table，如果達到64，那么將沖突的存儲結構為紅黑樹。在源碼還有這樣的一個字段。
static final int UNTREEIFY_THRESHOLD = 6; // 這樣表明了從紅黑樹轉化為鏈表的閾值為 6，為何同樣不是 8 那？ //如果插入和刪除都在 8 附近，將多二者相互轉化將浪費大量的時間，對其性能影響。 //如果是的二者轉化的操作不平衡，偏向一方，則可以避免此類影響。
3.1 紅黑樹的數據結構
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; // 刪除后需要取消鏈接，指向前一個節點（原鏈表中的前一個節點） boolean red; }因為 繼承了 LinkedHashMap.Entry<K,V> ，所以存儲的數據還是在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() 決定了一個鏈表何時轉化為一個紅黑樹。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) { // 簡單的 Node 修改為 TreeNode，同時維護了 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); // 真正生成紅黑樹的 } }TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); } // 實現 Node 鏈表節點到 TreeNode 節點的轉化。下面函數真正實現了鏈表的紅黑樹的轉變。首先構建一個標準查詢二叉樹，然后在標準查詢二叉樹然后調整為一個紅黑樹。而 balanceInsertion() 實現了調整。
/** * 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) { // 第一次轉化過程，將鏈表的頭節點作為根節點。 x.parent = null; x.red = false; // 紅黑樹的定義 根節點必須為黑色 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) //// 通過 Hash 的大小來確定插入順序 dir = -1; // dir 大小順序的標識 else if (ph < h) dir = 1; else if ((kc == null && //當 兩個 Hash 的值相同，進行特殊的方法，確定大小。 (kc = comparableClassFor(k)) == null) || // Returns x's Class if it is of the form "class C implements Comparable ", else null. 如果 key類的 源碼書寫格式為 C implement Comparable<C> 那么返回該類類型 C, 如果間接實現也不行。 如果是 String 類型，直接返回 String.class (dir = compareComparables(kc, k, pk)) == 0) // ((Comparable)k).compareTo(pk)); 強制轉換后進行對比，若 dir == 0,則 tieBreakOrder()，繼續仲裁 dir = tieBreakOrder(k, pk); // 首先通過二者的類類型進行比較，如果相等的話，使用 (System.identityHashCode(a) <= System.identityHashCode(b) 使用原始的 hashcode，不是重寫的在對比。 TreeNode<K,V> xp = p; // 遍歷的，上一個節點 if ((p = (dir <= 0) ? p.left : p.right) == null) { //通過 dir，將 p 向下查找，直到 p 為 null，找到一個插入時機 x.parent = xp; if (dir <= 0) xxp.left = x; else xxp.right = x; root = balanceInsertion(root, x); //進行二叉樹的調整 break; } } } } moveRootToFront(tab, root); }3.3 將一個二叉樹轉化為紅黑樹的操作-balanceInsertion()
當紅黑樹中新增節點的時候需要調用balanceInsertion方法來保證紅黑樹的特性。
如果想要了解紅黑樹的插入過程那么必須對紅黑樹的性質有一個較為清晰的了解。
紅黑樹的性質：
鴻蒙官方戰略合作共建——HarmonyOS技術社區
每個結點或是紅色的，或是黑色的
根節點是黑色的
每個葉結點（NIL）是黑色的
如果一個節點是紅色的，則它的兩個兒子都是黑色的。
對于每個結點，從該結點到其葉子結點構成的所有路徑上的黑結點個數相同。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; // 插入的子節點必須為 red for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //// x 當前處理節點 xp父節點 xpp祖父節點 xppl祖父左節點 xppr 祖父右節點 if ((xxp = x.parent) == null) { // 如果 當前處理節點為根節點，滿足紅黑樹的性質，結束循環 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 紅黑樹總結
TreeNode 完整的實現了一套紅黑樹的增刪改查的規則。實現參考了《算法導論》
/* ------------------------------------------------------------ */ // Red-black tree methods, all adapted from CLR
這里推薦一個紅黑樹動畫演示網站 https://rbtree.phpisfuture.com/
紅黑樹是一個不嚴格的平衡二叉查找樹，高度近似 log(N)。
四、HashMap 的擴展
Map中 key 有一個性質，就是 key 不能重復，而 Java Set 的含義：集合中不能有重復的元素。HashMap 的實現已經足夠的優秀。那么我們是否可以用 key 的性質來實現 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 就是存進 Map 中的 value，而 key 正是 Set 語義的實現。而且可以判斷出 HashSet 中是允許存入 Null 值的。
到此，相信大家對“Java之怎么實現從Map到HashMap”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
