कार्यान्वयन को देखते हुए, यह एक द्विआधारी पेड़ की तरह दिखता है। विशेष रूप से, टिप्पणी नीचे चलता है कि यह एक लाल-काले पेड़ है:
ट्री डिब्बे (यानी, डिब्बे जिसका तत्व हैं:
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;
...
}
बराबर हैश कोड से निपटने के लिए के रूप में, इस जावाडोक में संबोधित किया जाता है सभी ट्री नोड्स) मुख्य रूप से हैशकोड द्वारा आदेश दिया गया है, लेकिन संबंधों के मामले में, यदि दो तत्व समान हैं "class C implements Comparable<C>", टाइप करें तो उनकी तुलना ऑर्डर करने के लिए विधि का उपयोग किया जाता है।
TreeNodeHashMap में इस्तेमाल रों TreeMap के उन लोगों की तरह ही बनाया जाता है कहा जाता है।
/**
* 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;
}
आप देख सकते हैं, इस मानक द्विआधारी खोज वृक्ष खोज के समान है:
आप यहाँ आवश्यक कुंजी वाला एक TreeNode के लिए खोज के कार्यान्वयन देख सकते हैं। सबसे पहले वे TreeNode खोजते हैं क्योंकि hashCode खोजी कुंजी के रूप में (HashMap की एक बाल्टी में अलग-अलग hashCode एस वाली प्रविष्टियां हो सकती हैं)। फिर यह TreeNode तक प्राप्त होता है जिसमें आवश्यक कुंजी के बराबर कुंजी होती है। द्वितीयक खोज compareTo का उपयोग करती है यदि कुंजी की कक्षा Comparable लागू करती है। अन्यथा, एक और संपूर्ण खोज की जाती है।
ध्यान दें कि आपको इस व्यवहार पर भरोसा नहीं करना चाहिए। यदि कोड पहले से ही टूटा व्यवहार (क्लस्टर हैशकोड) है तो यह कार्यान्वयन-विशिष्ट फ़ॉलबैक है। और यदि आपकी चाबियाँ अच्छी तरह से हैश नहीं है लेकिन तुलनीय हैं तो आप शुरुआत से एक ट्रेमैप का भी उपयोग कर सकते हैं। – the8472