Loại cây nào được sử dụng trong java 8 HashMap bucket?

Question

Như tôi đã biết trong việc thực hiện gói javaMap HashMap đã được thay đổi một chút. Nếu kích thước thùng vượt quá một số giá trị thì danh sách sẽ biến đổi thành "cây cân bằng".

Tôi không hiểu
1. loại cây cân bằng nào được sử dụng trong Oracle JDK? (AVL? Đỏ-đen? Cái gì đó giống như trong cơ sở dữ liệu cho các chỉ mục?)
2. Có phải cây nhị phân không?
3. Khi tôi hiểu việc sắp xếp thực thi theo mã băm. Ví dụ trong thùng của tôi, tôi có 102 phần tử. 100 giá trị với hashcode bằng nhau 12 (Tôi hiểu rằng nó có giá trị nhưng tôi chỉ cần hiểu hành vi này) và 2 với hashcode 22.
Tìm kiếm sẽ được thực hiện như thế nào cho giá trị?

Answer 1

Nhìn vào triển khai, nó trông giống như cây nhị phân. Cụ thể hơn, bình luận dưới đây cho thấy nó là một cây đỏ-đen:

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

Đối với xử lý mã băm bình đẳng, điều này được giải quyết trong Javadoc:

thùng Tree (ví dụ, thùng mà yếu tố này là tất cả các TreeNode) là được sắp xếp chủ yếu bởi hashCode, nhưng trong trường hợp quan hệ, nếu hai phần tử giống nhau "class C implements Comparable<C>", thì phương thức compareTo của chúng được sử dụng để đặt hàng.

Các TreeNode s sử dụng trong HashMap được cho là có cấu trúc tương tự như những người TreeMap.

Bạn có thể thấy việc thực hiện việc tìm kiếm một TreeNode chứa khóa cần ở đây:

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

Như bạn có thể thấy, đây là giống với nhị phân tìm kiếm cây tìm kiếm chuẩn. Đầu tiên, họ tìm kiếm TreeNode có cùng số hashCode làm khóa được tìm kiếm (vì một nhóm duy nhất của HashMap có thể chứa các mục nhập có khác nhau hashCode s). Sau đó, nó tiếp tục cho đến khi một số TreeNode có khóa bằng phím được yêu cầu được tìm thấy. Tìm kiếm phụ sử dụng compareTo nếu lớp của khóa thực hiện Comparable. Nếu không, tìm kiếm đầy đủ hơn sẽ được thực hiện.