欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

TreeSet,TreeMap,Collections工具类排序方法

时间:2023-07-30

一,TreeSet排序方式

使用TreeSet类方式进行排序要用到Comparator构造器,当我们创建一个TreeSet对象时,在括号内需要完成一个匿名内部类的代码编写,而这个匿名内部类就会当作一个Comparator对象传递给给TreeSet的有参构造器

public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator));}

之后再把comparator对象赋给TreeMap自身的comparator,这个参数还是Comparator类型,然后在源码中调用Comparator比较的时候使用的Compare方法就是我们自己写的匿名内部类。

public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator;}

因此TreeSet的底层还是TreeMap。

public static void main(String[] args) { Set set=new TreeSet(new Comparator() { @Override public int compare(Object o1, Object o2) { int length=((String)o1).length()-((String)o2).length(); if(length==0){ return((String)o1).compareTo(((String) o2)); } return length; } }); set.add("Jack"); set.add("Lucy"); set.add("Tom"); System.out.println(set);

当需要比较的时候, 就会进入到TreeMap里面的put方法,如下代码所示。

private V put(K key, V value, boolean replaceOld) { Entry t = root; if (t == null) { addEntryToEmptyMap(key, value); return null; } int cmp; Entry 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 { V oldValue = t.value; if (replaceOld || oldValue == null) { t.value = value; } return oldValue; } } while (t != null); } else { Objects.requireNonNull(key); @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 { V oldValue = t.value; if (replaceOld || oldValue == null) { t.value = value; } return oldValue; } } while (t != null); } addEntry(key, value, parent, cmp < 0); return null;}

上面的源码所示的红色字体显示的就是调用我们创建的匿名内部类传递给TreeMap的comparator,所以当用到第二个红色字体显示的代码时,就会进入到我们写的匿名内部类,去比较传进去的两个参数,第一个参数是当前传进去的,也就是现在执行的key值,第二个传进去的是之前传进去的代码,两者比较,比较的方法就要看我们写的匿名内部类了。

Set set=new TreeSet(new Comparator() { @Override public int compare(Object o1, Object o2) { int length=((String)o1).length()-((String)o2).length(); if(length==0){ return((String)o1).compareTo(((String) o2)); } return length; }});

如上图代码,重写的comparator匿名内部类的compare方法,o1就是当前执行的代码的key值,o2就是之前执行过的代码的key值,让o1的长度减去o2的长度,结果值是一个int型,再根据这个结果值分开讨论,如果大于0,说明当前的key长度大于要比较的key长度,再看源码的紫色字体,大于0的条件,就要执行t=t.right;也就是让o2的右边的key值o3来和当前执行的key值比较长度,同时将左边的t.left置为null,这样,如果o1长度小于o3,就会执行小于0的if条件,将t=t.left,即为null赋给t,跳出循环,再执行

addEntry(key, value, parent, cmp < 0);

将当前的key值信息添加,每一次进行比较的时候,t一般都会取列表中的第二个key值进行比较,因为这时的key既有左边的值,也有右边的值,如果新来的key值大于这个第二个key值,那么第二个t就会将其右边的值赋给这个t,即执行else if的内容,t=t.right;同时将t.left置为null,这样做的目的就是后边的值如果大于新来的key值,那么相减后肯定为负数,也就会执行if语句的内容t=t.left,而这个时候的t.left经过第一轮的比较后被赋予null值,这样就可以跳出这个循环,执行我们上面说的addEntry语句,添加新的信息。而如果新来的key值小于第二个key值,就会执行if语句的内容,即t=t.left,这是t.right会被赋予null,t从第二个key值变成了第一个key的值,第一个key的值再和新来的key值进行比较,如果第一个key的值大于新来的key值,那么相差之和小于0,就会执行else if语句的内容,即t=t.right,这是的t.right经过第一轮的比较,已经被赋予了null值,因此在这个时候就会跳出循环执行addEntry语句。如果第一个key值小于新来的key值,因为第一个key值左边已经没有值了,所以还是会执行第一个if语句内容t=t.left,这个时候t.left为null也会跳出循环在执行addEntry语句,这样,整体来看一个新的key内容就会被添加到数组中去,并进行了排序。

这里要知道两个点,第一个是我们自己创建的匿名内部类是要比较什么,如果相比较长度,就向下转型成String,再调用length方法得到长度值并相差,如果想按字母大小进行排序,就直接向下转型,然后调用compareTo方法进行比较,按照返回值的正负再根据刚刚的分析进行排序。如果比较的两个key值返回的差值为0,则会进入到else语句,也就是上面的棕色代码内的内容,这个时候执行的目的就是key值保持不变,而value的值由新的key值对应的value值替换掉所比较的key值对应的value值,但是TreeSet类我们只用显示key值,而不用显示value值,所以这个地方主要是在TreeMap中体现出来。

二,TreeMap的排序

创建TreeMap对象时,因为TreeMap类里面也有含Comparator类型的有参构造器,所以也可以通过自己在创建TreeMap有参构造器的括号传入编写的匿名内部类作为一个comparator对象传递给TreeMap的有参构造器,这个有参构造器接收到我们传入的comparator对象后,就会自动把这个对象赋给它自身的comparator属性,当我们调用底层源码去比较排序的时候,再调用comparator的时候就是调用的我们自己编写的匿名内部类里面的内容了。

public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator;}

其实TreeMap的排序方式跟TreeSet的排序方式及其相像,只是TreeSet需要多一步,即把匿名内部类传递给TreeSet的有参构造器,再由这个有参构造器传递给TreeMap的Comparator类型的有参构造器,最后将comparator对象赋给TreeMap自身的comparator,最后调用排序仍然是调用TreeMap里面的put两个参数方法,再调用put三个参数的方法,基本步骤和上面分析的方法类似,使用key来进行比较,比较后的结果,value的顺序会随着key位置的变化而变化,如果key比较之后的差值返回的是0,那么进入源码中的棕色else语句,将当前执行的value替换掉所比较的之前的旧value值,此过程key的值保持不变,而value值发生替换。

TreeSet和TreeMap进行排序,去重的原理基本一致,调用的都是TreeMap类里面的方法,所以说TreeSet的底层是TreeMap维护,而我们重写的Comparator对象相应的compare方法在TreeSet中是要传递给TreeMap的Comparator类型的有参构造器的,中间还有一个传递给TreeSet有参构造器,再由TreeSet有参构造器传递给TreeMap有参构造器的步骤,而TreeMap方法直接把这个Comparator对象传递给自身的有参构造器即可。

三,Collections工具类排序方法

public class Collection03 { public static void main(String[] args) { List list=new ArrayList(); list.add("Jack"); list.add("ab"); list.add("Tom"); list.add("Mary"); list.add("Smith"); list.add("曾某某"); Collections.sort(list, new Comparator() { public int compare(Object o1,Object o2){ int sum= ((String) o1).length()-((String) o2).length(); if(((String) o1)=="曾某某") return -1; if(((String) o2)=="曾某某") return 1; else return sum; } }); System.out.println(list); }}

Collections工具类的排序方式,需要使用到Collections中的一个sort方法,即

Collections.sort(List 对象,new Comparator(){

    重写匿名内部类compare方法:

})

如上面我自己写的匿名内部类的排序方式,先向下转型成String类型,因为我想使用String类里面的length()方法,所以是要先向下转型的,然后我再做了两个if条件判断语句,o1是正在执行的代码对应的key值,如果它和要比较的key值返回的差值总是为负数的话,那么就会靠前走,o2是已经存在了的key值,即被比较值,它和正在执行的key值进行比较总是返回正数,则它会往前面走,这点可以参考前面讲TreeMap的底层代码时的说法。通过这种方法就可以特意的把某个重要的key值往前放。Collections的方法下一贴再做总结。 

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。