前言
因为在面试的时候碰到几次list的去重和排序,觉着有必要给大家总结一下具体的方法,分享出来供大家学习参考,话不多说了,来一起看看下面介绍的一种做法:
一、list去重
1.1 实体类Student
List<Student>
容量10k以上,要求去重复。这里Student的重复标准是属性相同,因此需要重写equals和hashcode方法,不知道有几个可以手写出来。
student的equals方法:
1
2
3
4
5
6
7
8
|
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方法:
1
2
3
4
5
6
|
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代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
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来完成重复获取。
先放代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
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的时间复杂度。
二、list对象排序
同样list中存放的是Student对象,我需要一个规则来排序。这个排序的规则这里定义为id的比较大小。参考:java中list排序
2.1 Student对象实现Comparable接口
Comparable接口提供一个比较的compareTo(Object o)
方法,通过返回值>0,=0,<0比较大小。这里由于仅仅把id当做比较大小的方法,直接用id做减法,如果是要比较对象,建议套用this.property.compareTo(o.property)
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
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)排序:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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.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); } } |
2.2 重载sort方法,传入一个比较器
Student类还是未实现Comparable接口之前的:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
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 + '}' ; } } |
在排序的代码出添加排序规则:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
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); } } |
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对服务器之家的支持。