java 8'de hangi ağaç türü kullanılır HashMap bucket?

Question

java8'da bildiğim gibi HashMap bucket uygulaması biraz değiştirildi. Kepçe boyutu bir değeri aşarsa, liste "dengeli ağaç" a dönüşür.

Oracle JDK
1. kullanılan dengeli ağacın ne tür anlamıyorum? (AVL? Red-black? Indexler için veri tabanlarında bir şey var mı?)
2. İkili ağaç mı?
3. Sıralama işleminin hashcode'a göre yapıldığını anladığım kadarıyla. Örneğin benim kovamda 102 elemanım var. Eşit kod ile 100 değer 12 (Ben bu değeri anladım ama sadece bu davranışı anlamak gerekir) ve 2 kodu 22 ile.
Arama değer için nasıl yürütülür?

Answer 1

uygulanması bakıldığında ikili ağaç gibi görünüyor. Daha spesifik olarak, yorum aşağıda bir kırmızı-siyah ağaç öneriyor: öğesi olan

Ağaç kutuları (yani, çöp kovaları: Eşit karma kodları ele gelince

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; 
    ... 
} 

, bu Javadoc ele alınmaktadır tüm TreeNode'lar), öncelikle hashCode tarafından sipariş edilen 'dur, ancak iki öğesinin aynı "class C implements Comparable<C>", türünde olması durumunda bağları durumunda compareTo yöntemi, sipariş vermek için kullanılır. HashMap kullanılan

TreeNode s TreeMap kişilerce benzer yapıda olduğu söylenmektedir.

/** 
    * 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; 
    } 

Gördüğünüz gibi, bu standart ikili arama ağacı arama benzer:

Burada gerekli anahtarını içeren bir TreeNode için arama uygulanmasını görebilirsiniz. Önce aradıkları anahtar ile aynı olan TreeNode'u ararlar (çünkü HashMap tek bir kova farklı hashCode s girişleri içerebilir). Ardından, gerekli anahtara eşit bir anahtar bulunan bir TreeNode sayılı tarihe kadar devam eder. Ikincil arama, anahtarın sınıfı Comparable uygularsa, compareTo kullanır. Aksi takdirde daha kapsamlı bir arama yapılır.