java 8 HashMap存儲桶中使用哪種樹型？

正如我所知在java8 HashMap存儲桶的實現有所變化。如果桶大小超過某個值，則列表轉換爲「平衡樹」。java 8 HashMap存儲桶中使用哪種樹型？

我不明白
1.什麼類型的平衡樹在Oracle JDK中使用？（AVL？紅黑？像在數據庫的索引？）
2.它是二叉樹？
3.據我所知，排序按哈希碼執行。例如在我的桶裏，我有102個元素。與哈希碼100個值同樣12（我的理解，它的價值，但我只需要了解這種行爲）和2散列碼22
如何搜索將會爲價值被執行？

來源

2016-12-26 gstackoverflow

請注意，你不應該依賴於這種行爲。在代碼已經破壞行爲的情況下，它是一個特定於實現的後備（聚簇hashcodes）。如果你的密鑰不能很好地散列，但是可以比較，你可以從一開始就使用樹形圖。 – the8472

望着實現，它看起來像一個二叉樹。更具體地講，在註釋下表明這是一個紅黑樹：

樹箱（即垃圾箱的元素是：
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; 
    ... 
} 
至於處理相同的散列碼，這是在Javadoc解決所有樹節點）是主要通過的hashCode排序，但在並列的情況，如果兩個元素是相同的「class C implements Comparable<C>」，類型，然後被用於排序其compareTo方法。

在HashMap使用的TreeNode s的說是結構類似於那些TreeMap。

你可以看到搜索的實現爲TreeNode包含所需的關鍵在這裏：

/** 
    * Finds the node starting at root p with the given hash and key. 
    * The kc argument caches comparableClassFor(key) upon first use 
    * comparing keys. 
    */ 
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
     TreeNode<K,V> p = this; 
     do { 
      int ph, dir; K pk; 
      TreeNode<K,V> pl = p.left, pr = p.right, q; 
      if ((ph = p.hash) > h) 
       p = pl; 
      else if (ph < h) 
       p = pr; 
      else if ((pk = p.key) == k || (k != null && k.equals(pk))) 
       return p; 
      else if (pl == null) 
       p = pr; 
      else if (pr == null) 
       p = pl; 
      else if ((kc != null || 
         (kc = comparableClassFor(k)) != null) && 
        (dir = compareComparables(kc, k, pk)) != 0) 
       p = (dir < 0) ? pl : pr; 
      else if ((q = pr.find(h, k, kc)) != null) 
       return q; 
      else 
       p = pl; 
     } while (p != null); 
     return null; 
    }

正如你所看到的，這是類似於標準的二叉搜索樹搜索。首先，他們搜索具有相同hashCode作爲搜索關鍵（因爲HashMap的單個桶可以包含具有不同hashCode S記錄）一個TreeNode。然後繼續，直到找到具有等於所需密鑰的密鑰的TreeNode。二級搜索使用compareTo如果類的關鍵工具的Comparable。否則，將執行更詳盡的搜索。

來源

2016-12-26 09:19:42 Eran

但是，如果** compareTo **未實現？ – gstackoverflow

如果JDK已經有了TreeMap，是什麼原因用另一個名字創建同一個類？ – gstackoverflow

@gstackoverflow它不是同一個班級。 HashMap中使用的'TreeNode'是一個實現細節。當單個bin中的條目數量超過某個閾值時，它應該比原始鏈表實現單個HashMap的性能更好。 – Eran

java 8 HashMap存儲桶中使用哪種樹型？

回答

相關問題