java中List对象列表去重或取出以及排序

秒速五厘米 2022-07-16 07:39 170阅读 0赞

面试碰到几次list的去重和排序。下面介绍一种做法：

## 1. list去重 ##

### 1.1 实体类Student ###

List<Student>容量10k以上，要求去重复。这里Student的重复标准是属性相同，因此需要重写equals和hashcode方法，不知道有几个可以手写出来。

**student的equals方法：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

public void equals(Object o){
      if(this == o) retun true;
      if(!(o instanceof Student)) return false;
      Student stu = (Studend)o;
      if(id!=stu.id) return false;
      if(age!=stu.age) return false;
      return name!=null ? name.equals(stu.name) : stu.name ==null;    
    }

这里只要记住宗旨是比较Student的属性即可，如果属性相同则相等。先考虑地址相等，然后类型匹配instanceof。接下来是各种属性，int属性直接双等号比较，String类型需要判断是否为null，如果是null则都是null返回true，如果不是null则比较equals。

**student的hashcode方法：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

public int hashCode(){
      int result = id;
      reuslt = 31*id +(name!=null?name.hashCode():0);
      reuslt = 31*age;
      return reuslt;
    }

hashCode是为了hash表计算做辅助，方便快速查找。因此hash算法的结果要尽量的散列。这里用到31，这个31在别的博客中看到的原因是这样的：**obj\*31==obj<<5-obj.左移5位相当乘以2的5次方，就是32**.null的hashCode为空。

通过equals和hashCode的实现可以发现，如果equals为true，则所有属性相同，而属性相同则计算出的hashCode必然相同。然而hashCode相同，属性未必一样，即equals不一定为真。

关于hashCode的价值体现并不在这里，而在于HashMap的实现。HashMap内部是通过链表数组的hash结构来实现的，这里就要用到hashcode。

下面是完整的Student代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

package com.test.arithmetic.listequals;
    
    /**
     * 这里id，name,age相同则Student相同，
     * 若有其他相同
     * Created by Administrator on 2016/3/29.
     */
    public class Student {
        int id;
        String name;
        int age;
    
        public Student(int id, String name, int age) {
            this.id = id;
            this.name = name;
            this.age = age;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Student)) return false;
    
            Student student = (Student) o;
    
            if (id != student.id) return false;
            if (age != student.age) return false;
            return name != null ? name.equals(student.name) : student.name == null;
    
        }
    
        @Override
        public int hashCode() {
            int result = id;
            result = 31 * result + (name != null ? name.hashCode() : 0);
            result = 31 * result + age;
            return result;
        }
    
    }

### 1.2通过HashSet去重 ###

如果你觉得自己可以hold住一个完善的hash算法就可以自己去实现它。这里采用jdk自带的HashSet来完成重复获取。

先放代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

package com.test.arithmetic.listequals;
    import org.junit.Assert;
    
    import java.util.*;
    
    /**
     * 取出list中重复的Student对象
     * Created by Administrator on 2016/3/29.
     */
    public class ObtainListEquals {
        public static void main(String[] args){
            //原始数据
            List<Student> list = new ArrayList<>();
            //重复数据
            List<Student> list2 = new ArrayList<>();
            //填充
            for (int i = 0; i < 10 ; i++) {
                list.add(new Student(i,"_"+i,18+i));
                Random random = new Random();
                if (random.nextBoolean()){
                    list.add(new Student(i,"_"+i,18+i));
                }
            }
            //使用hashset去重复，set为重复的集合，可以通过new ArrayList(set)转换成list
            HashSet<Student> set = new HashSet<>();
            for (Student student : list) {
                boolean add = set.add(student);
                if (!add){
                    list2.add(student);
                }
            }
            //比较
            Assert.assertEquals(list.size(),list2.size()+set.size());
            
        }
    
    }

去重的原理和简单，无论你仅仅是想把重复的丢掉，或者将重复的取出来。这里去掉的是第二次遇到的对象，取出的也是第二次遇到的对象。HashSet中的add方法会返回一个Boolean值，如果插入的值已经存在，则直接返回false。关于hashset的源码放到以后研究。大概的说，是通过HashMap的key来实现的，而HashMap在1.8中改动很大，据说是用红黑树实现的，提高了get的时间复杂度。参考：[1.8HashMap][]

## 2. list对象排序 ##

同样list中存放的是Student对象，我需要一个规则来排序。这个排序的规则这里定义为id的比较大小。参考：[java中list排序][java_list]

### 2.1 Student对象实现Comparable接口 ###

Comparable接口提供一个比较的compareTo(Object o)方法，通过返回值>0,=0,<0比较大小。这里由于仅仅把id当做比较大小的方法，直接用id做减法，如果是要比较对象，建议套用this.property.compareTo(o.property).

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

package com.test.arithmetic.listequals;
    
    /**
     * 这里id，name,age相同则Student相同，
     * 若有其他相同
     * Created by Administrator on 2016/3/29.
     */
    public class Student implements Comparable<Student>{
        int id;
        String name;
        int age;
    
        public Student(int id, String name, int age) {
            this.id = id;
            this.name = name;
            this.age = age;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Student)) return false;
    
            Student student = (Student) o;
    
            if (id != student.id) return false;
            if (age != student.age) return false;
            return name != null ? name.equals(student.name) : student.name == null;
    
        }
    
        @Override
        public int hashCode() {
            int result = id;
            result = 31 * result + (name != null ? name.hashCode() : 0);
            result = 31 * result + age;
            return result;
        }
    
        @Override
        public int compareTo(Student o) {
            return this.id-o.id;
        }
    }

通过Collections.sort(list)排序：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

### 2.2 重载sort方法，传入一个比较器 ###

Student类还是未实现Comparable接口之前的：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

package com.test.arithmetic.list;
    
    /**
     * 这里id，name,age相同则Student相同，
     * 若有其他相同
     * Created by Administrator on 2016/3/29.
     */
    public class Student{
        int id;
        String name;
        int age;
    
        public Student(int id, String name, int age) {
            this.id = id;
            this.name = name;
            this.age = age;
        }
    
        public int getId() {
            return id;
        }
    
        public Student(int id) {
            this.id = id;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Student)) return false;
    
            Student student = (Student) o;
    
            if (id != student.id) return false;
            if (age != student.age) return false;
            return name != null ? name.equals(student.name) : student.name == null;
    
        }
    
        @Override
        public int hashCode() {
            int result = id;
            result = 31 * result + (name != null ? name.hashCode() : 0);
            result = 31 * result + age;
            return result;
        }
    
        @Override
        public String toString() {
            return "Student{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

在排序的代码出添加排序规则：

package com.test.arithmetic.list.sort;
    
    import com.test.arithmetic.list.Student;
    import org.junit.Before;
    import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    
    /**
     * 对list中对象排序
     * Created by Administrator on 2016/3/29.
     */
    public class SortList {
        List<Student> list;
        @Before
        public void setUp(){
            list = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                int v = (int)(Math.random() * 100);
                list.add(new Student(v,"_"+v,18+v));
            }
            System.out.println("原list："+list);
        }
        //方法一，对象实现Comparable接口
        @Test
        public void byImplements(){
    //        Collections.sort(list);
            System.out.println("排序后："+list);
        }
    
        /*方法二，添加比较器*/
        @Test
        public void byOverideCompare(){
    
            Collections.sort(list, new Comparator<Student>() {
                @Override
                public int compare(Student o1, Student o2) {
                    return o1.getId()-o2.getId();
                }
            });
            System.out.println(list);
        }
    }

[ContractedBlock.gif]: http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220716/9f5037f710b74e5b820c9d46872ca0ff.png
[1.8HashMap]: http://blog.jobbole.com/66078/
[java_list]: http://www.cnblogs.com/wentiertong/archive/2011/03/07/1973698.html