java中的TreeSet的add()方法解析

  1 public class HomeWork05 {
  2     public static void main(String[] args) {
  3         // TreeSet最好是同一类型。
  4 //        TreeSet treeSet = new TreeSet();
  5         // TreeSet可以定义排序【匿名内部类作为参数，实现Compare接口】
  6         TreeSet treeSet = new TreeSet(new Comparator() {
  7             @Override
  8             public int compare(Object o1, Object o2) {
  9                 return ((String) o1).compareTo((String) o2);
 10             }
 11         });
 12         treeSet.add("hello");
 13         treeSet.add("world");
 14         treeSet.add(new String("hello"));
 15 //        treeSet.add(new A(10));
 16 //        treeSet.add(new A(20));
 17 
 18         Iterator iterator = treeSet.iterator();
 19         while (iterator.hasNext()) {
 20             Object obj = iterator.next();
 21             System.out.println(obj);
 22         }
 23 
 24         /**
 25          * TreeSet无参构造器：
 26          *     public TreeSet() {
 27          *         this(new TreeMap<E,Object>());
 28          *     }
 29          *     public TreeMap() {
 30          *         comparator = null;
 31          *     }
 32          * 可见TreeSet的底层是TreeMap。
 33          *
 34          * 解析add():
 35          * 1) public boolean add(E e) {
 36          *         return m.put(e, PRESENT)==null;
 37          *     }
 38          *     $ PRESENT是value的固定值，主要是按照key的值存储。
 39          *
 40          * 2) public V put(K key, V value) {
 41          *         Entry<K,V> t = root;
 42          *         // 首次进入put()方法，root为空
 43          *         // 将第一次添加的key，作为root根节点
 44          *         if (t == null) {
 45          *             compare(key, key);
 46          *             root = new Entry<>(key, value, null);
 47          *             size = 1;
 48          *             modCount++;
 49          *             return null;
 50          *         }
 51          *         int cmp;
 52          *         Entry<K,V> parent;
 53          *         Comparator<? super K> cpr = comparator;
 54          *         // 遍历红黑树,compare()比较，两对象是否相同
 55          *         // 若在红黑树中没有相同的key,就添加key;
 56          *         // 若在红黑树中有相同的key,将红黑树中的key对应的value值,替换成添加的key对应的value值。
 57          *         if (cpr != null) {
 58          *             do {
 59          *                 parent = t;
 60          *                 cmp = cpr.compare(key, t.key);
 61          *                 if (cmp < 0)
 62          *                     t = t.left;
 63          *                 else if (cmp > 0)
 64          *                     t = t.right;
 65          *                 else
 66          *                     return t.setValue(value);
 67          *             } while (t != null);
 68          *         }
 69          *         else {
 70          *             if (key == null)
 71          *                 throw new NullPointerException();
 72          *                 Comparable<? super K> k = (Comparable<? super K>) key;
 73          *             // 遍历红黑树,根据自定义对象的compareTo()比较，两对象是否相同
 74          *             // 若在红黑树中没有相同的key,就添加key;
 75          *             // 若在红黑树中有相同的key,将红黑树中的key对应的value值,替换成添加的key对应的value值。
 76          *             do {
 77          *                 parent = t;
 78          *                 cmp = k.compareTo(t.key);
 79          *                 if (cmp < 0)
 80          *                     t = t.left;
 81          *                 else if (cmp > 0)
 82          *                     t = t.right;
 83          *                 else
 84          *                     return t.setValue(value);
 85          *             } while (t != null);
 86          *         }
 87          *         Entry<K,V> e = new Entry<>(key, value, parent);
 88          *         if (cmp < 0)
 89          *             parent.left = e;
 90          *         else
 91          *             parent.right = e;
 92          *         fixAfterInsertion(e);
 93          *         size++;
 94          *         modCount++;
 95          *         return null;
 96          *     }
 97          *
 98          * 3) final int compare(Object k1, Object k2) {
 99          *         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
100          *             : comparator.compare((K)k1, (K)k2);
101          *     }
102          *    $ 比较k1和k2，① 用TreeMap的comparator比较器比较，② 用传入对象的compareTo()方法进行比较。
103          */
104     }
105 }
106 
107 // 实现Compare接口的compareTo()方法
108 class A implements Comparable{
109     private int num;
110 
111     public A(int num) {
112         this.num = num;
113     }
114 
115     @Override
116     public int compareTo(Object o) {
117         return this.num - ((A) o).num;
118     }
119 }