JavaSE学习总结(十三)Set集合/HashSet集合/LinkedHashSet集合/TreeSet集合/比较器的使用/利用Set集合实现去重
一、Set集合
Set集合是Collection集合的一个子接口,实际上Set就是Collection,只是行为略有不同:
- Set集合不保存重复的元素。(唯一性)
- Set集合是无序的:存储和取出的顺序无序。(无序性)
案例演示
import java.util.HashSet;
import java.util.Set;
public class MyTest {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("hello");
set.add("world");
set.add("hello");
set.add("world");
set.add("good");
set.add("morning");
for (String s : set) {
System.out.println(s);
}
}
}
二、HashSet集合
(一)概述
HashSet是Set接口的典型实现(集合中元素也是无序且唯一的),实现了Set接口中的所有方法,并没有添加额外的方法,大多数时候使用Set集合时就是使用这个实现类。HashSet 底层数据结构是哈希表,HashSet 不是线程安全的,集合元素可以是 null。
- 哈希表:是一个元素为链表的数组,综合了数组和链表的优点 (像新华字典一样) (JDK1.7之前)
(二)存储规则
当向 HashSet 集合中添加一个元素A时,HashSet 会调用该对象的 hashCode() 方法来得到该对象的整型hashCode 值,然后根据 hashCode 值决定该对象在 HashSet 中的存储位置,如果存储位置已经有元素B了,然后再根据equals()方法来判断元素A和元素B是否相同,相同则不再存入这个元素A,以确保元素唯一性;不同则将元素A链在已存在的元素B后面。
结论:HashSet 保证元素唯一性是靠元素重写hashCode()和equals()方法来保证的,如果不重写则无法保证。
(三)HashSet中如何判断集合元素相等
两个对象比较 具体分为如下四个情况:
- 1.如果有两个元素的hashCode()方法返回不相等的值,但它们通过equals()方法比较返回false,HashSet将会把它们存储在不同的位置。
- 2.如果有两个元素的hashCode()方法返回不相等的值,但它们通过equals()方法比较返回true,HashSet将会把它们存储在不同的位置。
- 3.如果有两个元素的hashCode()方法返回相等的值,但它们通过equals()方法比较不相等,HashSet将会把它们存储在相同的位置,在这个位置以链表式结构来保存多个对象
- 4.如果有两个元素的hashCode()方法返回相等的值,但它们通过equals()方法比较返回true,HashSet将不予添加。
结论:HashSet判断两个元素相等的标准———两个对象通过hashCode()方法比较相等,并且两个对象的equals()方法返回值也相等。
注意:HashSet是根据元素的hashCode值来快速定位的,如果HashSet中两个以上的元素具有相同的hashCode值,将会导致碰撞次数增加,性能下降。所以如果重写类的equals()方法和hashCode()方法时,应尽量保证两个对象通过hashCode()方法返回值相等时,通过equals()方法比较返回true。
案例演示
用HashSet集合存储学生对象,重写hashCode()和equals()保证集合中的元素不重复。
import java.util.Objects;
import java.util.HashSet;
class Student {
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
//重写equals()
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return age == student.age &&
Objects.equals(name, student.name);
}
//重写hashCode()
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
public class MyTest {
public static void main(String[] args) {
//HashSet集合能够保证元素的唯一性,是靠元素重写hashCode()方法和equals()方法来保证的,如果元素不重写则无法保证
//HashSet 底层用的是HashMap来存的
Student s1 = new Student("张三", 25);
Student s2 = new Student("张三", 25);
Student s3 = new Student("张三", 25);
Student s4 = new Student("王五", 26);
Student s5 = new Student("王五", 23);
Student s6 = new Student("小明", 25);
Student s7 = new Student("赵四", 26);
Student s8 = new Student("李四", 28);
Student s9 = new Student("李四", 28);
Student s10 = new Student("小红", 25);
HashSet<Student> hashSet = new HashSet<>();
hashSet.add(s1);
hashSet.add(s2);
hashSet.add(s3);
hashSet.add(s4);
hashSet.add(s5);
hashSet.add(s6);
hashSet.add(s7);
hashSet.add(s8);
hashSet.add(s9);
hashSet.add(s10);
for (Student student : hashSet) {
System.out.println(student);
}
}
}
三、LinkedHashSet集合
LinkedHashSet 底层数据结构是链表和哈希表,元素有序(存取顺序一致)且唯一 ,链表保证了元素有序,哈希表保证了元素唯一。
案例演示
import java.util.LinkedHashSet;
public class MyTest {
public static void main(String[] args) {
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("A");
linkedHashSet.add("B");
linkedHashSet.add("D");
linkedHashSet.add("E");
linkedHashSet.add("C");
linkedHashSet.add("E");
linkedHashSet.add("C");
linkedHashSet.add("E");
linkedHashSet.add("C");
for (String s : linkedHashSet) {
System.out.println(s);
}
}
}
四、TreeSet集合
(一)特点
元素唯一,并且可以对元素进行排序
底层数据结构是二叉树
案例演示
import java.util.TreeSet;
public class MyTest1 {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(20);
treeSet.add(18);
treeSet.add(23);
treeSet.add(22);
treeSet.add(17);
treeSet.add(24);
treeSet.add(19);
treeSet.add(18);
treeSet.add(24);
for (Integer integer : treeSet) {
System.out.println(integer);
}
}
}
结果是排好序的,并且唯一
那么它的底层的数据结构是如何实现排序的呢?
添加完以后,按左中右的顺序取出来就是有序的了:
(二)排序
Treeset集合的排序又分为自然排序和使用比较器排序
具体用哪种排序,根据你使用的构造方法,如果用空参构造,那么就使用的是自然排序,如果用有参构造,就是使用比较器来排序。
1.自然排序
如果我们使用的是自然排序:那么对元素所属的类是有要求的,要求该类必须实现一个Comparable
接口并且重写里面的compareTo()
方法(否则报错),根据此方法的返回值(正、负、0)来决定元素在二叉树的位置。
我们上面的例子中的Integer类就已经实现了Comparable
接口,并且重写了compareTo()
方法:
继续点开compare()
方法可以看到它的实现逻辑:
其实就是x小于y就返回负数,那么x就放置在y的左边;x等于y返回0,就不放进去;x大于y就返回正数,那么x就放置在y的右边。
案例演示1
需求:将集合中的学生按年龄来排序
import java.util.TreeSet;
class Student implements Comparable<Student>{//实现Comparable接口
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public int compareTo(Student s) {
int num1 = this.age-s.age;//比较逻辑是按照年龄大小来排序
//此时可能有人觉得return num1;这个方法就可以结束了
//但是会出现一个现象:名字不同,年龄相同的Student对象存不进去
//而这个和重写equals方法没关系,因为底层数据结构是二叉树不是哈希表
//年龄相同不能说明他是同一个对象,还得比较姓名
int num2=num1==0?this.name.compareTo(s.name):num1;
return num2;//如果需要降序,则return -num2;
}
}
public class MyTest {
public static void main(String[] args) {
Student s1 = new Student("王五", 21);
Student s2 = new Student("王五", 21);
Student s3 = new Student("王五五", 21);
Student s4 = new Student("王五", 22);
Student s5 = new Student("张三", 25);
Student s6 = new Student("李四", 29);
Student s7 = new Student("赵四", 24);
Student s8 = new Student("赵六", 26);
Student s9 = new Student("小明", 26);
Student s10 = new Student("小红", 28);
Student s11 = new Student("小张", 21);
Student s12 = new Student("小刚", 20);
TreeSet<Student> treeSet = new TreeSet<>();
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s4);
treeSet.add(s5);
treeSet.add(s6);
treeSet.add(s7);
treeSet.add(s8);
treeSet.add(s9);
treeSet.add(s10);
treeSet.add(s11);
treeSet.add(s12);
for (Student student : treeSet) {
System.out.println(student);
}
}
}
元素的唯一性是靠compareTo()方法的返回值来保证的,如果返回0,表示两个元素相等,则不重复存储
案例演示2
需求:按照姓名的长度进行排序
主要条件是姓名的长度
然后是姓名内容
然后是年龄
import java.util.TreeSet;
class Student implements Comparable<Student>{//实现Comparable接口
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public int compareTo(Student s) {
//先比较姓名长度
int num1=this.name.length()-s.name.length();
//姓名长度一样 再比较姓名内容
int num2=num1==0?this.name.compareTo(s.name):num1;
//如果姓名长度和内容一样再比较年龄
int num3=num2==0?this.age-s.age:num2;
return num3;
}
}
public class MyTest {
public static void main(String[] args) {
Student s1 = new Student("王五", 21);
Student s2 = new Student("王五", 21);
Student s3 = new Student("王五五", 21);
Student s4 = new Student("王五六七八", 22);
Student s5 = new Student("张三三", 25);
Student s6 = new Student("李四", 29);
Student s7 = new Student("赵六六", 27);
Student s8 = new Student("赵六六", 26);
Student s9 = new Student("明", 26);
Student s10 = new Student("小红", 28);
Student s11 = new Student("小红", 21);
Student s12 = new Student("小刚", 20);
TreeSet<Student> treeSet = new TreeSet<>();
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s4);
treeSet.add(s5);
treeSet.add(s6);
treeSet.add(s7);
treeSet.add(s8);
treeSet.add(s9);
treeSet.add(s10);
treeSet.add(s11);
treeSet.add(s12);
for (Student student : treeSet) {
System.out.println(student);
}
}
}
2.使用比较器排序
在创建TreeSet对象的时候使用有参构造TreeSet(Comparator<? super E> comparator)
构造一个新的空 TreeSet,它根据指定比较器进行排序。
案例演示
需求:将集合中的学生按年龄来排序
- 方式1
创建一个Comparator的子实现类,并使用
import java.util.TreeSet;
import java.util.Comparator;
class Student{
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
//自定义的Comparator子实现类
class MyComparator implements Comparator<Student> {
@Override
public int compare(Student s1, Student s2) {
int num1=s1.getAge()-s2.getAge();
int num2=num1==0?s1.getName().compareTo(s2.getName()):num1;
return num2;
}
}
public class MyTest {
public static void main(String[] args) {
Student s1 = new Student("王五", 21);
Student s2 = new Student("王五", 21);
Student s3 = new Student("王五五", 21);
Student s4 = new Student("王五", 22);
Student s5 = new Student("张三", 25);
Student s6 = new Student("李四", 29);
Student s7 = new Student("赵四", 24);
Student s8 = new Student("赵六", 26);
Student s9 = new Student("小明", 26);
Student s10 = new Student("小红", 28);
Student s11 = new Student("小张", 21);
Student s12 = new Student("小刚", 20);
//创建Comparator子实现类的对象
MyComparator myComparator = new MyComparator();
//有参构造,传入Comparator子实现类的对象
TreeSet<Student> treeSet = new TreeSet<>(myComparator);
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s4);
treeSet.add(s5);
treeSet.add(s6);
treeSet.add(s7);
treeSet.add(s8);
treeSet.add(s9);
treeSet.add(s10);
treeSet.add(s11);
treeSet.add(s12);
for (Student student : treeSet) {
System.out.println(student);
}
}
}
- 方式2
不创建多的类,使用匿名内部类
import java.util.Comparator;
import java.util.TreeSet;
public class MyTest {
public static void main(String[] args) {
Student s1 = new Student("王五", 21);
Student s2 = new Student("王五", 21);
Student s3 = new Student("王五五", 21);
Student s4 = new Student("王五", 22);
Student s5 = new Student("张三", 25);
Student s6 = new Student("李四", 29);
Student s7 = new Student("赵四", 24);
Student s8 = new Student("赵六", 26);
Student s9 = new Student("小明", 26);
Student s10 = new Student("小红", 28);
Student s11 = new Student("小张", 21);
Student s12 = new Student("小刚", 20);
//使用匿名内部类传入比较器对象
TreeSet<Student> treeSet = new TreeSet<>(new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
int num1=s1.getAge()-s2.getAge();
int num2=num1==0?s1.getName().compareTo(s2.getName()):num1;
return num2;
}
});
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s4);
treeSet.add(s5);
treeSet.add(s6);
treeSet.add(s7);
treeSet.add(s8);
treeSet.add(s9);
treeSet.add(s10);
treeSet.add(s11);
treeSet.add(s12);
for (Student student : treeSet) {
System.out.println(student);
}
}
}
聊到比较器,提一下Arrays的sort方法:
import java.util.Arrays;
public class MyTest {
public static void main(String[] args) {
Integer[] i={2,54,6,23,74,685,0};
Arrays.sort(i);
System.out.println(Arrays.toString(i));
}
}
我们平时使用的Arrays的sort()方法,默认是升序排序,那么如果我们想要降序呢?
其实可以用到比较器:
import java.util.Arrays;
import java.util.Comparator;
public class MyTest {
public static void main(String[] args) {
Integer[] i={2,54,6,23,74,685,0};
Arrays.sort(i, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i2-i1;
}
});
System.out.println(Arrays.toString(i));
}
}
五、应用
案例演示1
需求:编写一个程序,获取10个1至20的随机数,要求随机数不能重复。
思路:可以使用HashSet、LinkedHashSet、TreeSet作为容器接收这些随机数,它们可以帮忙去重。
import java.util.HashSet;
import java.util.Random;
public class MyTest {
public static void main(String[] args) {
Random random = new Random();
HashSet<Integer> set = new HashSet<>();
while(set.size()<10){
int num=random.nextInt(20)+1;
set.add(num);
}
System.out.println(set);
}
}
案例演示2
需求:将ArrayList中的元素去重
思路:将ArrayList传给HashSet(HashSet(Collection<? extends E> c)
构造一个包含指定 collection 中的元素的新 set。)
import java.util.ArrayList;
import java.util.HashSet;
public class MyTest {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2210);
list.add(2210);
list.add(2130);
list.add(2150);
list.add(2150);
list.add(2210);
list.add(2130);
list.add(2150);
list.add(21770);
list.add(21550);
HashSet<Integer> set = new HashSet<>(list);
System.out.println(set);
}
}