java.lang.Comparable, java.util.Compartor区别以及Hadoop中关于自定义类型中的compare方法
浏览数：33 /
时间：2015年06月08日
public interface Comparable<T> {
public int compareTo(T o);
}
规定了对象内部比较的方法
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}
定义外部比较器的基本方法，其中equals是用来确定两个比较器是否相等。
关于对象内部比较和外部比较这两个接口的区别和使用场景如下：
个人总结：
Comparable是对象内部固有的比较，一个类的不同对象肯定需要很自然的比较，无论使用在任何地方
Comparator是外部比较，在不改变对象内部固有的比较标准的前提下，增加新的比较行为，
尤其是对已有的类型，String，Integer等，如果我们想要不同的比较行为，例如绝对值比较，那么我们不能修改这写类固有的比较标准，而是加入自定义的外部比较器，
在外部比较器中定义新的比较规则，同时在需要比较的地方，插入我们自定义的外部比较器实例。
举个例子，Arrays工具类
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, c);
}
其中TimSort.sort
1 static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
2 if (c == null) {
3 Arrays.sort(a, lo, hi);
4 return;
5 }
6
7 rangeCheck(a.length, lo, hi);
8 int nRemaining = hi - lo;
9 if (nRemaining < 2)
10 return; // Arrays of size 0 and 1 are always sorted
11
12 // If array is small, do a "mini-TimSort" with no merges
13 if (nRemaining < MIN_MERGE) {
14 int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
15 binarySort(a, lo, hi, lo + initRunLen, c);
16 return;
17 }
18
19 /**
20 * March over the array once, left to right, finding natural runs,
21 * extending short natural runs to minRun elements, and merging runs
22 * to maintain stack invariant.
23 */
24 TimSort<T> ts = new TimSort<>(a, c);
25 int minRun = minRunLength(nRemaining);
26 do {
27 // Identify next run
28 int runLen = countRunAndMakeAscending(a, lo, hi, c);
29
30 // If run is short, extend to min(minRun, nRemaining)
31 if (runLen < minRun) {
32 int force = nRemaining <= minRun ? nRemaining : minRun;
33 binarySort(a, lo, lo + force, lo + runLen, c);
34 runLen = force;
35 }
36
37 // Push run onto pending-run stack, and maybe merge
38 ts.pushRun(lo, runLen);
39 ts.mergeCollapse();
40
41 // Advance to find next run
42 lo += runLen;
43 nRemaining -= runLen;
44 } while (nRemaining != 0);
45
46 // Merge all remaining runs to complete sort
47 assert lo == hi;
48 ts.mergeForceCollapse();
49 assert ts.stackSize == 1;
50 }
如果c==null，则使用对象内部已经定义好的比较标准
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
否则，使用外部比较器
1 while (left < right) {
2 int mid = (left + right) >>> 1;
3 if (c.compare(pivot, a[mid]) < 0)
4 right = mid;
5 else
6 left = mid + 1;
7 }
我们知道hadoop中有自定义类型，需要实现， WritableComparable接口，而WritableComparable接口继承之一便是Comparable接口。
因此，自定义的类型需要实现compareTo方法
如，LongWrite.class
@Override
public int compareTo(LongWritable o) {
long thisValue = this.value;
long thatValue = o.value;
return (thisValue<thatValue ? -1 : (thisValue==thatValue ? 0 : 1));
}
但是hadoop并没有直接使用这个基于对象内部比较机制，对需要排序比较的地方进行key的排序，而是借助外部比较器，统一介入的。
hadoop中的外部比较器，
WritableComparator。
1 public static WritableComparator get(
2 Class<? extends WritableComparable> c, Configuration conf) {
3 WritableComparator comparator = comparators.get(c);
4 if (comparator == null) {
5 // force the static initializers to run
6 forceInit(c);
7 // look to see if it is defined now
8 comparator = comparators.get(c);
9 // if not, use the generic one
10 if (comparator == null) {
11 comparator = new WritableComparator(c, conf, true);
12 }
13 }
14 // Newly passed Configuration objects should be used.
15 ReflectionUtils.setConf(comparator, conf);
16 return comparator;
17 }
该方法会被Job调用，获得当前类型对应的外部比较器实例。WritableComparator内部有缓存，其中会缓存类型和其对应的外部比较器。get方法会从缓存中取得类型对应的外部比较器，如果取得为空，则手动生成一个外部比较器，
外部比较器，默认的比较方法是按照对象的内部比较标准进行的。
1 @SuppressWarnings("unchecked")
2 public int compare(WritableComparable a, WritableComparable b) {
3 return a.compareTo(b);
4 }
5
6 @Override
7 public int compare(Object a, Object b) {
8 return compare((WritableComparable)a, (WritableComparable)b);
9 }
但是，hadoop在使用这个外部比较器的地方的，使用方式是：（例如，MapOutputBuffer，map端spill）
1 public int compare(final int mi, final int mj) {
2 final int kvi = offsetFor(mi % maxRec);
3 final int kvj = offsetFor(mj % maxRec);
4 final int kvip = kvmeta.get(kvi + PARTITION);
5 final int kvjp = kvmeta.get(kvj + PARTITION);
6 // sort by partition
7 if (kvip != kvjp) {
8 return kvip - kvjp;
9 }
10 // sort by key
11 return comparator.compare(kvbuffer,
12 kvmeta.get(kvi + KEYSTART),
13 kvmeta.get(kvi + VALSTART) - kvmeta.get(kvi + KEYSTART),
14 kvbuffer,
15 kvmeta.get(kvj + KEYSTART),
16 kvmeta.get(kvj + VALSTART) - kvmeta.get(kvj + KEYSTART));
17 }
使用的是外部比较器的这个方法，如下
1 @Override
2 public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
3 try {
4 buffer.reset(b1, s1, l1); // parse key1
5 key1.readFields(buffer);
6
7 buffer.reset(b2, s2, l2); // parse key2
8 key2.readFields(buffer);
9
10 } catch (IOException e) {
11 throw new RuntimeException(e);
12 }
13
14 return compare(key1, key2); // compare them
15 }
而这个方法默认也是使用对象内部比较的标准。
在考虑性能的时候，需要将这个方法的默认行为改成基于bytes字节的比较，那么就需要用户自己写一个外部比较类的子类，并手动放到WritableComparator类中的内部缓存。
这种手动放入到缓存的过程，在自定义类型中完成，（LongWritable为例）
（1）自定义外部比较器的子类。
1 public static class Comparator extends WritableComparator {
2 public Comparator() {
3 super(LongWritable.class);
4 }
5
6 @Override
7 public int compare(byte[] b1, int s1, int l1,
8 byte[] b2, int s2, int l2) {
9 long thisValue = readLong(b1, s1);
10 long thatValue = readLong(b2, s2);
11 return (thisValue<thatValue ? -1 : (thisValue==thatValue ? 0 : 1));
12 }
13 }
（2）手动注入到缓存中
1 static { // register default comparator
2 WritableComparator.define(LongWritable.class, new Comparator());
3 }
这样，就改变了外部比较器默认的比较标准，按照用户自定义的compare方法进行比较。
那么，什么时候要自定义外部比较器呢？
1）效率考虑，如上所述
2）排序的规则发生变化，所有需要排序的地方，可以指定外部比较器，让其发生比较规则的改变（默认的比较都是自定义类型中的外部比较器比较规则）
比如，二次排序等。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
