TreeMap分析(上)

 1     /**
 2      * 红黑树每个结点对象的数据结构
 3      * 4      *
 5      * @param <K>  key
 6      * @param <V>  value
 7      */
 8     static final class Entry<K,V> implements Map.Entry<K,V> {
 9         K key;   //键
10         V value; //值
11         Entry<K,V> left;  //左子结点引用
12         Entry<K,V> right;  //右子结点引用
13         Entry<K,V> parent;  //父结点引用
14         boolean color = BLACK;  //结点默认为黑色
15 
16         /**
17          * 构造一个叶子结点，默认无左右子结点，颜色为黑色
18          */
19         Entry(K key, V value, Entry<K,V> parent) {
20             this.key = key;
21             this.value = value;
22             this.parent = parent;
23         }
24 
25         /**
26          * 返回key
27          *
28          * @return the key
29          */
30         public K getKey() {
31             return key;
32         }
33 
34         /**
35          * 返回key对应的value
36          *
37          * @return the value associated with the key
38          */
39         public V getValue() {
40             return value;
41         }
42 
43         /**
44          * 替换对应的值
45          *
46          * @return 原先被替换的值
47          */
48         public V setValue(V value) {
49             V oldValue = this.value;
50             this.value = value;
51             return oldValue;
52         }
53 
54         /**
55          * 重写结点的equals()方法，比较结点的大小时使用
56          */
57         public boolean equals(Object o) {
58             if (!(o instanceof Map.Entry))
59                 return false;
60             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
61             //必须key和value都相同才算相等
62             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
63         }
64 
65         /**
66          * 重写结点的hashCode()方法
67          */
68         public int hashCode() {
69             int keyHash = (key==null ? 0 : key.hashCode());
70             int valueHash = (value==null ? 0 : value.hashCode());
71             return keyHash ^ valueHash;  //key的hashCode 异或  value的hashCode
72         }
73 
74         /**
75          * 重写toString()方法
76          */
77         public String toString() {
78             return key + "=" + value;
79         }
80     }
81     
82     /** 用户自定义的比较器 */
83     private final Comparator<? super K> comparator;
84 
85     /** 红黑树根结点  */
86     private transient Entry<K,V> root;
87 
88     /** 红黑树总结点个数  */
89     private transient int size = 0;

 1     /**
 2      * 无参数构造方法，使用key的自然比较顺序来维护树中结点的顺序
 3      */
 4     public TreeMap() {
 5         comparator = null;
 6     }
 7 
 8     /**
 9      * 带参数构造方法，使用用户传入的比较器来维护树中结点的顺序
10      * @param 用户自定义比较器，如果为空，则该Map会使用key的自然排序维护树的顺序
11      */
12     public TreeMap(Comparator<? super K> comparator) {
13         this.comparator = comparator;
14     }

 1     /**
 2      * 获取节点的操作
 3      * 如果在map中找到了这个键，则返回键对应的值；找不到对应的键或者键指向为null，否则返回null
 4      *
 5      * @throws ClassCastException 用户传入的key和当前map中的key无法比较（不是同一类型），则报该异常
 6      * @throws NullPointerException 使用了自然排序但传入的key为null，或者比较器不支持key为null的情况，则报此异常
 7      *         
 8      */
 9     public V get(Object key) {
10         Entry<K,V> p = getEntry(key);   //可以看到实际上是调用getEntry()这个方法来获取节点的
11         return (p==null ? null : p.value);
12     }
13     
14     
15     /**
16      * 返回通过传入的键在map中找到的相应entry，若未找到则返回null
17      *
18      * @throws ClassCastException 用户传入的key和当前map中的key无法比较（不是同一类型），则报该异常
19      * @throws NullPointerException 使用了自然排序但传入的key为null，或者比较器不支持key为null的情况，则报此异常
20      */
21     final Entry<K,V> getEntry(Object key) {
22         // 首先要区分是使用map键的自然排序查找还是使用用户自定义的比较器来进行查找
23         if (comparator != null)  //如果用户传入了自定义比较器
24             return getEntryUsingComparator(key); //调用getEntryUsingComparator()方法，通过用户自定义比较器的compare()方法查找entry
25         if (key == null)  //如果key为null，报空指针异常
26             throw new NullPointerException();
27         Comparable<? super K> k = (Comparable<? super K>) key;  //没有传入自定义比较器，使用key的自然排序比较传入的key和map中的key
28         Entry<K,V> p = root;  //从根节点开始比较
29         while (p != null) {  //如果节点不是空，则一直循环遍历比较
30             int cmp = k.compareTo(p.key); //获取传入的key和当前节点key的比较结果,使用自然排序Comparable实现的compareTo()方法进行比较
31             if (cmp < 0)  //结果<0,说明传入的key比当前节点的key小
32                 p = p.left; //将下次比较的节点变更为当前节点的左子节点
33             else if (cmp > 0)  //结果>0,说明传入的key比当前节点的key大
34                 p = p.right; //将下次比较的节点变更为当前节点的右子节点
35             else  //结果相等,则该节点就是要查找的节点
36                 return p;  //直接返回节点对应的Entry
37         }
38         return null;   //遍历完整个树也没找到，则返回null
39     }
40     
41     
42 
43     /**
44      * 使用用户自定义比较器的比较方法来查找节点
45      * 逻辑与通过自然排序查找类似，不再赘述
46      */
47     final Entry<K,V> getEntryUsingComparator(Object key) {
48         @SuppressWarnings("unchecked")
49             K k = (K) key;
50         Comparator<? super K> cpr = comparator;
51         if (cpr != null) {
52             Entry<K,V> p = root;
53             while (p != null) {
54                 int cmp = cpr.compare(k, p.key);  //仅仅这里和getEntry()方法不同，使用自定义比较器的compare()方法进行比较
55                 if (cmp < 0)
56                     p = p.left;
57                 else if (cmp > 0)
58                     p = p.right;
59                 else
60                     return p;
61             }
62         }
63         return null;
64     }