Comparable和Comparator

xiaoxiao2021-02-28  63

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

一般是用于比较的对象本身直接来实现,如常见的基本数据类型。


public interface Comparator<T> { int compare(T o1, T o2); boolean equals(Object obj); }

作为比较器对象传入到某个集合中参与比较。在自定义对象中用的比较多,因为一开始我们并不会主动为了让某个类参与比较而实现Comparable,当需要的时候可以实现一个比较器传入,降低耦合性。


我们平时接触比较多的:Integer、String、TreeMap(TreeSet)、Collections.sort、Arrays.sort等。

Integer:

public final class Integer extends Number implements Comparable<Integer> { public int compareTo(Integer anotherInteger) { return compare(this.value, anotherInteger.value); } public static int compare(int x, int y) { return (x < y) ? -1 : ((x == y) ? 0 : 1); } //...... }

String:

public final class String implements java.io.Serializable, Comparable<String>, CharSequence { public int compareTo(String anotherString) { int len1 = value.length; int len2 = anotherString.value.length; int lim = Math.min(len1, len2); char v1[] = value; char v2[] = anotherString.value; int k = 0; while (k < lim) { char c1 = v1[k]; char c2 = v2[k]; if (c1 != c2) { return c1 - c2; } k++; } return len1 - len2; } //...... }

TreeMap的put方法:

private final Comparator<? super K> comparator; 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(); 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; }

该类持有一个Comparator类型的引用,在put的时候,首先会检查 Comparator类型的cpr 是否为null,如果不是则用它来参与比较;如果是,则有:

Comparable<? super K> k = (Comparable<? super K>) key;

利用key实现的Comparable中的compareTo来参与比较。这样就保证了自定义比较器优先,我们甚至可以间接改变基本数据类型的比较方式。

Collections(实际调用Arrays.sort()):

public class Collections { public static <T extends Comparable<? super T>> void sort(List<T> list) { Object[] a = list.toArray(); Arrays.sort(a); 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:

public class Arrays { public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex, c); else TimSort.sort(a, fromIndex, toIndex, c); } /** To be removed in a future release. */ private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { rangeCheck(a.length, fromIndex, toIndex); T[] aux = copyOfRange(a, fromIndex, toIndex); if (c==null) mergeSort(aux, a, fromIndex, toIndex, -fromIndex); else mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c); } private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off, c); mergeSort(dest, src, mid, high, -off, c); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (c.compare(src[mid-1], src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) dest[i] = src[p++]; else dest[i] = src[q++]; } } }

注意JDK1.6和1.7的区别,同时需要关注下TimSort。

转载请注明原文地址: https://www.6miu.com/read-61789.html

最新回复(0)