jdk源码学习 内外部比较器（Comparator、Compar

在我对java的学习之初，经常遇到这两个接口，心里大概明白都是起个比较器的作用，但具体到使用场景的时候，尤其是阅读别人一些方法中精简的lambda表达式对这两个接口的应用的时候，感觉真是一脸懵逼。现在是时候做一份总结了~
我们先从简单的下手，就是俗称内比较器Comparable，它的源码不要太简单：

// 在官方注解里指出：1.如果指定的对象为空，则应抛出空指针异常
// 2.如果指定对象的类型禁止与本类的类型进行比较，则应抛出类型转换异常
public interface Comparable<T> {
   public int compareTo(T o);
}

首先我们发现内比较器是个泛型接口，任何一个类实现了此接口，就表明它的实例具有内在的排序关系。此时对一个对象数组 a ,排序就可以方便的使用 Arrays.sort(a); （Arrays类是功能强大的工具类，我们以后学习）来完成。同时对存储在集合中的元素类型如果实现了Comparable接口，那么对于这些元素进行搜索，计算极限值以及自动维护也变得非常简单。例如，以下程序依赖于实现了Comparable接口的String类，它的功能是将命令行参数去重，并按字母顺序打印出来：

// 在IDE里如何设置命令行参数，我常用的方式是在run含义的小绿色箭头左侧
// 有个下拉选项Edit configurations 点击然后在Program arguments里输入，以空格符隔开，run就可以啦
public static void main(String[] args) {
        Set<String> s=new TreeSet<>();
        Collections.addAll(s,args);
        System.out.println(s);

    }
// 这是书上的写法，我们做一下变形
public static void main(String[] args) {
        Set<String> s=new TreeSet<>();
        List<String> s1=new ArrayList<>();
        Collections.addAll(s,args);
        Collections.addAll(s1,args);
        System.out.println(s);
        System.out.println(s1);

    }

命令行参数如下：

image.png

结果：

[bbb, kkk, ttt, yyy]
[yyy, bbb, kkk, ttt, kkk]

有趣的是我们对两种数据结构调用了一种方法，结果表现显然不一样（Set不允许重复元素）。
为了满足好奇心，我们看一下集合工具类的源码：

// 其实Collections有好几个内部类它们也有各自的addAll方法，它们在线程安全等方面有更多的考虑，我们以后再说
// 两个参数，前者是一个集合，后者是一个T类型的可变长参数，集合元素要求是T的超类
// 因为本方法的意义在于将类型安全的元素添加到集合中去，注意collection的单个元素是key
// 是不存在value的概念的，而map的单个元素是键值对。所以无法用collections里的方法对map进行操作
// 但是可以用collections里定义的内部类里的方法来完成对map的操作
 @SafeVarargs
    public static <T> boolean addAll(Collection<? super T> c, T... elements) {
        boolean result = false;
        for (T element : elements)

// add方法在本类中是一个返回值为boolean类型的抽象方法，具体实现取决于具体的集合类
// 比较有趣的是迭代部分： result |= c.add(element);  其中 result的初值是false，
// 而迭代过程中一旦有一次添加成功(add返回true)，result最终的值就变为了true
// 对于list集合是不在意重复元素的，每次都能添加成功，返回值为true
// 对于set集合添加重复元素是不可能的，返回值也是false
// 这样对于list每次都成功自然没什么意义，但对于set有可能成功有可能失败就起到了一个告诉我们
// 最后集合元素是否增加了的作用
            result |= c.add(element);
        return result;
    }

不改变命令行参数，我们对代码做出以下改动：

public static void main(String[] args) {
        Set<String> s=new TreeSet<>();
        List<String> s1=new ArrayList<>();
        System.out.println(Collections.addAll(s,args));
        System.out.println(Collections.addAll(s1,args));
        System.out.println(s);
        System.out.println(s1);
        System.out.println(Collections.addAll(s,args));
        System.out.println(Collections.addAll(s1,args));
        System.out.println(s);
        System.out.println(s1);

    }

结果显而易见：
true
true
[bbb, kkk, ttt, yyy]
[yyy, bbb, kkk, ttt, kkk]
false
true
[bbb, kkk, ttt, yyy]
[yyy, bbb, kkk, ttt, kkk, yyy, bbb, kkk, ttt, kkk]

我们为了能够展现 Collections.addAll 的区别选择用一个 arraylist 集合和 treeset 做对比。但细心的朋友肯定发现了list集合不是能放重复元素么，那我们实现 compareTo 方法的意义是什么？没错，如果单纯是个 list集合其实它实现不实现 Comparable 接口仅仅通过调用 Collections.addAll 是体现不出来区别的（这部分留到arraylist源码解析中的add方法详细解释）。但对于 treeset 不实现 Comparable 是绝对不可以接受的事。
原文中之所以使用 treeset，是因为 treeset 虽然是一个 set 保证其中的每个元素唯一不重复，但它其实跟普通 set 有区别，在于能够按照 compareTo 方法的具体实现完成排序（这也是为什么这个例子中按字母顺序打印）。排序的过程其实是在每次调用add方法时递归调用TreeMap的put方法实现的（注意 treeset 自己可没有put方法哦，类似于 hashset 借助于 hashmap 实现其功能一样，treeset 也偷了一次懒）：

 public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
// m是什么呢，在字段定义部分我们找到了m
 private transient NavigableMap<E,Object> m;
// 原来m是被 treeset 组合进来的一个 NavigableMap 对象，而且m是在构造方法中初始化的
   public TreeSet() {
        this(new TreeMap<E,Object>());
    }
// 空参构造函数调用了一个有参构造来实现初始化
TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
// TreeMap是什么呢，我们看一下定义
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

public interface NavigableMap<K,V> extends SortedMap<K,V>
// NavigableMap扩展了 SortedMap，具有了针对给定搜索目标返回最接近匹配项的导航方法

// 也就是说 TreeSet 其实是通过构造函数里传入了一个 TreeMap 来实现的，而TreeMap 自然也是个有序的Map集合。那么我们看一下 TreeMap 的put方法
// 提前警告，内容比较多，有点耐心哦
public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

嗯细节问题咱们先略过，等分析treeset再认真逐行解释，在这里简单的给出 TreeMap 在每次put操作后究竟发生了什么的原理图：（图源来自网络）

image.png

从图中不难看出，只有元素类型实现了 Comparable 接口，对于每个新添加进来的元素，我们才能知道它应该放置的位置，不然也就无法实现 TreeMap 排序的功能了。当然具体细节还是挺繁琐的，我们以后再说。

那么言归正传，一旦一个类实现了Comparable接口，就可以跟许多泛型算法以及依赖于该接口的集合实现进行协作。Java 平台类库中几乎所有值类以及所有枚举类型都实现了 Comparable 接口。如果你正在编写具有明显内在排序关系（如字母顺序、数字顺序或时间顺序）的值类，则应该实现 Comparable 接口。

compareTo 方法的定义与 equals 有些类似：
将这个对象与指定的对象进行比较。当该对象小于，等于或大于时