容器学习九：Comparable & Comparator

一.前言

     本系列文章以研究源码为主，源码原理和设计次之，应用最弱。因为现在能读懂源码，要搞清楚设计和原理尚需火候，至于应用网上大把大把的有，读懂了源码应用也就是小事了。

 

二. Comparable & Comparator

package java.lang;

public interface Comparable<T> {
    public int compareTo(T o);
}

 

package java.util;

//一般情况，x.equals(y)<======>compare(x, y)==0，但不是必须的
//x,y对象在物理是毫无关系的（除非x,y是同一对象）
//为了逻辑上的相等，我们才重写euqals方法；为了排序，我们才重写compare方法
//所以x.equals(y)和compare(x, y)的充分必要条件完全是逻辑上的概念，由使用者自己决定
//你可以让这种充分必要条件不成立，只要你能保证你代码是正常的。
public interface Comparator<T> {
    int compare(T o1, T o2);
    //重写object.equals方法
    boolean equals(Object obj);
}

 

三.什么时候使用Comparable & Comparator

1. 当两个对象需要比较的时候，使用Comparable & Comparator。
2. 比较的两个对象可以是基本类型包装对象，也可以是除此之外的其它对象。
3. 需要进行对象比较的场合，排序：
   1. Collections.sort(List<T>)，Arrays.sort(Object[]);
   2. TreeMap，插入数据时根据二叉树的规则，确定插入数据的位置。当然检索数据就一样了。
      

 

四.TreeMap插入数据源码

public V put(K key, V value) {
        ......
        //comparator是初始化TreeMap指定的比较器
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                //如果指定了比较器，就用此比较器比较两个对象。此时会有一个专门的比较器来比较两个对象。
                cmp = cpr.compare(key, t.key);
                //根据比较的结果-1,0,1，来确定插入位置
                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();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                //如果未指定比较器，就使用对象本身作为比较器。此时对象本身需实现Comparable接口。
                cmp = k.compareTo(t.key);
                //根据比较的结果-1,0,1，来确定插入位置
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        ......
    }

 

五.Collections.sort方法源码

Collctions.java
//不指定比较器，list存放的对象必须实现Comparable接口
public static <T extends Comparable<? super T>> void sort(List<T> list) {
	Object[] a = list.toArray();
        //对list对应的数组排序
	Arrays.sort(a);
        //同排序后的数组，重新给list赋值
	ListIterator<T> i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set((T)a[j]);
	}
}

//指定比较器
public static <T> void sort(List<T> list, Comparator<? super T> c) {
	Object[] a = list.toArray();
	Arrays.sort(a, (Comparator)c);
	ListIterator i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set(a[j]);
	}
}

//后面Arrays.sort的代码比较逻辑，就同TreeMap了，要么用对象本身比较，要么用比较器比较两个对象