Java中的Comparable接口和Comparator接口

Java中的Comparable接口和Comparator接口

  1. 介绍
    Comparable<T>接口和Comparator<T>接口都是JDK中提供的和比较相关的接口。使用它们可以对对象进行比较大小,排序等操作。这算是之后排序的先导知识吧。
    Comparable, 字面意思是“可以比较的”,所以实现它的类的多个实例应该可以相互比较“大小”或者“高低”等等。
    Comparator, 字面意思是“比较仪,比较器”, 它应该是专门用来比较用的“工具”。
  2. Comparable

    Comparable<T>接口

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

    首先看看JDK中怎么说的:

    This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's <i>natural ordering</i>, and the class's <tt>compareTo</tt> method is referred to as its <i>natural comparison method</i>.<p>
    

大意是: 任何实现这个接口的类,其多个实例能以固定的次序进行排列。次序具体由接口中的方法compareTo方法决定。

Lists (and arrays) of objects that implement this interface can be sorted automatically by {@link Collections#sort(List) Collections.sort} (and {@link Arrays#sort(Object[]) Arrays.sort}).

如果某个类实现了这个接口,则它的List或数组都能使用Collections.sort()或Arrays.sort()进行排序。

常见的类如Integer, Double, String都实现了此类。一会儿会结合源码进行分析。

我们先来看Integer中的实现:

public final class Integer extends Number implements Comparable<Integer> {

    private final int value;

    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);
    }
    public static int compareUnsigned(int x, int y) {
        return compare(x + MIN_VALUE, y + MIN_VALUE);
    }

我们只贴出了和比较相关的方法。

可以看到,compareTo方法其中调用了compare方法,这是JDK1.7增加的方法。在Integer中新增这个方法是为了减少不必要的自动装箱拆箱。传入compare方法的是两个Integer的值x和y。

如果x < y, 返回-1;如果x = y, 返回0;如果x > y, 返回1。

顺便一说,JDK中的实现非常简洁,只有一行代码, 当判断情况有三种时,使用这种嵌套的判断 x ? a : b 可以简洁不少,这是该学习的。

后面的compareUnsigned是JDK1.8新加入的方法, 用来比较无符号数。这里的无符号数意思是默认二进制最高位不再作为符号位,而是计入数的大小。

其实现是

public static int compareUnsigned(int x, int y) {
        return compare(x + MIN_VALUE, y + MIN_VALUE);
    }

直接为每个值加了Integer的最小值 -231。我们知道Java中int类型为4个字节,共32位。符号位占用一位的话,则其范围为-231 到231 – 1。

使用此方法时,所有正数都比负数小。最大值为 -1,因为 -1的二进制所有位均为 1。

也就是1111 1111 1111 1111 1111 1111 1111 1111 > 其它任何32位数。

具体是什么情况呢?

2.1 计算机编码

首先我们知道,在计算机中,所有数都是以二进制存在,也就是0和1的组合。

为了使数字在计算机中运算不出错,出现了原码,反码和补码。原码就是一个数的二进制表示,其中最高位为符号位,表示其正负。

正数的原码反码补码都一样,负数的反码是除符号位以外全部取反,补码为反码加1,如图所示为32位bits(也就是4比特bytes)数的原码反码和补码。

Java中的Comparable接口和Comparator接口

为什么要使用反码和补码呢?用四位二进制数举例:

1的二进制为0001,-1的二进制为1001,如果直接相加,则1 + (-1) = 0,二进制表示为0001 + 1001 = 1010 != 0,所以不能直接使用原码做运算。

后来出现了反码,除符号位之外其他位取反,1001(-1)取反后为1110, 现在做加法 0001 (1) + 1110 (-1) = 1111 。由于1111是负数,所以取反之后才是其真实值,取反后为1000,也就是-0。这能满足条件了,但是美中不足的是,0带了负号。唯一的问题其实就出现在0这个特殊的数值上。 虽然人们理解上+0和-0是一样的, 但是0带符号是没有任何意义的。 而且会有0000原和1000原两个编码表示0。怎么办呢?

人们又想出了补码,它是反码加1。-1的补码是 1111,以上的运算用补码表示就是0001 (1) + 1111 (-1) = 0000 = 0。神奇的发现,这个式子完美契合了十进制加法!

同时我们留出了1000,可以用它表示-8

(-1) + (-7) = (补码) 1111 + 1001 = 1000 = -8。注意,由于此处的-8使用了之前-0的补码来表示,所以-8没有没有原码和反码表示(针对的四位,如果是八位,则没有原码和反码的是-128,依次类推)。

使用补码, 不仅仅修复了0的符号以及存在两个编码的问题, 而且还能够多表示一个最低数. 这就是为什么4位二进制, 使用原码或反码表示的范围为[-7, +7], 而使用补码表示的范围为[-8, 7].

Java中的Comparable接口和Comparator接口

这就是简单的要用反码和补码的原因。

2.2 大数溢出问题

int类型在32位系统中占4个字节、32bit,补码表示的的数据范围为:

[10000000 00000000 00000000 00000000] ~ [01111111 11111111 11111111 11111111]

[−231,231−1]

[-2147483648, 2147483647]

java中表示为:

[Integer.MIN_VALUE, Integer.MAX_VALUE]

与byte类型的表示一样,由于负数比正数多表示了一个数字。对下限去相反数后的数值会超过上限值,溢出到下限,因此下限的相反数与下限相等;对上限去相反数的数值为负值,该负值比下限的负值大1,在可以表示的范围内,因此上限的相反数是上限直接取负值。

2.3 String类型的compareTo方法

看完Integer后,我们再来看String中compareTo的实现方式:

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    /** The value is used for character storage. */
    private final char value[];     // String的值

    public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);     // limit, 表示两个String中长度较小的String长度
        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;     // 如果char不相同,则取其差值
            }
            k++;    // 如果char值相同,则继续往后比较
        }
        return len1 - len2;     // 如果所有0 ~ (lim - 1)的char均相同,则比较两个String的长短
    }
  // 字面意思是对大小写不敏感的比较器
    public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();
    private static class CaseInsensitiveComparator
            implements Comparator<String>, java.io.Serializable {
        private static final long serialVersionUID = 8575799808933029326L;

        public int compare(String s1, String s2) {  
            int n1 = s1.length();
            int n2 = s2.length();
            int min = Math.min(n1, n2);     // 和上面类似,均是取两个String间的最短长度
            for (int i = 0; i < min; i++) {
                char c1 = s1.charAt(i);
                char c2 = s2.charAt(i);
                if (c1 != c2) {
                    c1 = Character.toUpperCase(c1); // 统一换成大写
                    c2 = Character.toUpperCase(c2); // 统一换成大写
                    if (c1 != c2) {     // 大写如果不相等则再换为小写试试
                        c1 = Character.toLowerCase(c1);
                        c2 = Character.toLowerCase(c2);
                        if (c1 != c2) {     // 到此处则确定不相等
                            // No overflow because of numeric promotion
                            return c1 - c2;
                        }
                    }
                }
            }
            return n1 - n2;
        }

        /** Replaces the de-serialized object. */
        private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
    }
    // String的方法,可以直接使用这个方法和其它String进行比较,
    // 内部实现是调用内部比较器的compare方法
    public int compareToIgnoreCase(String str) {
        return CASE_INSENSITIVE_ORDER.compare(this, str);
    }   
}

String中的关于compare的方法相对复杂一点,但还是比较简单。我们先不看其他的代码,只重点关注compareTo方法。

public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);     // limit, 表示两个String中长度较小的String长度
        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;     // 如果char不相同,则取其差值
            }
            k++;    // 如果char值相同,则继续往后比较
        }
        return len1 - len2;     // 如果所有0 ~ (lim - 1)的char均相同,则比较两个String的长短
    }

内容很简洁,就是取两个String的长度中较小的,作为限定值(lim)。之后对数组下标为从0到lim – 1的char变量进行遍历比较,如果遇到不相同的值,返回其差值。一般我们只用其正负性,如果返回负数则说明第一个对象比第二个对象“小”。

例如比较 "abc"和"bcd",当对各自第一个字符’a’和 ‘b’进行比较时,发现 ‘a’ != ‘b’,则返回 ‘a’ – ‘b’ ,这个值是负数, char类型的-1,Java会自动将其类型强转为int型。最后得出结论"abc"比"bcd"小。

  1. Comparator

    Comparator<T>接口

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

    这是一个外部排序接口,它的功能是规定“比较大小”的方式。实现它的类可以作为参数传入Collections.sort()或Arrays.sort(),使用它的比较方式进行排序。

    它可以为没有实现Comparable接口的类提供排序方式。

    String类中以及Array类等都有实现此接口的内部类。

    在上面String的源码中就有一个内部的自定义Comparator类CaseInsensitiveComparator, 我们看看它的源码。

    public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();
    private static class CaseInsensitiveComparator
            implements Comparator<String>, java.io.Serializable {
        private static final long serialVersionUID = 8575799808933029326L;
    
        public int compare(String s1, String s2) {  
            int n1 = s1.length();
            int n2 = s2.length();
            int min = Math.min(n1, n2);     // 和上面类似,均是取两个String间的最短长度
            for (int i = 0; i < min; i++) {
                char c1 = s1.charAt(i);
                char c2 = s2.charAt(i);
                if (c1 != c2) {
                    c1 = Character.toUpperCase(c1); // 统一换成大写
                    c2 = Character.toUpperCase(c2); // 统一换成大写
                    if (c1 != c2) {     // 大写如果不相等则再换为小写试试
                        c1 = Character.toLowerCase(c1);
                        c2 = Character.toLowerCase(c2);
                        if (c1 != c2) {     // 到此处则确定不相等
                            // No overflow because of numeric promotion
                            return c1 - c2;
                        }
                    }
                }
            }
            return n1 - n2;
        }
    
        /** Replaces the de-serialized object. */
        private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
    }
    // String的方法,可以直接使用这个方法和其它String进行比较,
    // 内部实现是调用内部比较器的compare方法
    public int compareToIgnoreCase(String str) {
        return CASE_INSENSITIVE_ORDER.compare(this, str);
    }   
    }

CaseInsensitiveComparator, 字面意思是对大小写不敏感的比较器。

我们观察它的compare方法,可以发现,它和上面的compareTo方法实现类似,都是取两个String中长度较小的,作为限定值min,之后对数组下标为从0到min – 1的char变量进行遍历比较。和上面稍有不同的是,此处先将char字符统一换成大写(upper case), 如果仍然不相等,再将其换为小写(lower case)比较。一个字母只有大写或者小写两种情形,如果这两种情况都不想等则确定不相等,返回其差值。如果限定值内所有的char都相等的话,再去比较两个String类型的长度。

例如比较 "abC"和"ABc",compareTo会直接返回 ‘a’ – ‘A’,而compareToIgnoreCase方法由于使用了CaseInsensitiveComparator,比较结果最终会返回true。

原文 

http://blog.51cto.com/13981400/2325028

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java中的Comparable接口和Comparator接口

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址