Set集合及其子类HashSet，LinkedHashSet, TreeSet详细讲解（包含笔记和练习题）

Set集合继承体系6、Set集合1Set集合的特点和常用的方法1、Set系列集合特点添加的元素是无序即存和取的顺序可能不一样、不重复、无索引。2、Set集合的实现类HashSet无序、不重复、无索引LinkedHashSet有序、不重复、无索引TreeSet可排序、不重复、无索引3、Set接口继承与Collection接口所以Set中的方法基本上与Collection的API一致。下面看看Collection常用方法1、public boolean add(E e); 添加元素返回值表示是否添加成功2、public void clear(); 清空集合中所有的元素3、public boolean remove(E e); 删除指定元素返回值表示是否删除成功4、public boolean contains(Object obj); 判断当前集合中是否包含给定的对象5、public int size(); 获取集合的长度6、public boolean isEmpty() 判断集合是否为空2Set集合的遍历和Collection遍历方法一样无索引所以有三种遍历方式迭代器遍历增强forLambda表达式import java.util.HashSet; import java.util.Iterator; import java.util.Set; import java.util.function.Consumer; public class SetText1 { public static void main(String[] args) { SetString s new HashSet(); s.add(张三); s.add(李四); s.add(王五); IteratorString it s.iterator(); while (it.hasNext()) { String str it.next(); System.out.print(str ); } System.out.println(); for(String str : s){ System.out.print(str ); } System.out.println(); 下面代码的匿名内部类new的是大括号中没有名字的类的对象实现了ConsumerString()这个接口。 // s.forEach(new ConsumerString() { // Override // public void accept(String str) { // System.out.print(str ); // } // }); s.forEach(str-System.out.print(str )); } }7、Set集合的实现类1HashSet——1、HashSet底层原理HashSet无序、不重复、无索引HashSet底层原理HashSet集合底层采取哈希表存储数据哈希表是一种对于增删改查数据性能都较好的结构哈希表组成JDK8之前数组链表JDK8开始数组链表红黑树哈希值哈希值对象的整数表现形式根据hashCode方法算出来的int类型的整数该方法定义在Object类中所有对象都可以调用默认使用地址值进行计算一般情况下会重写hashCode方法利用对象内部的属性值计算哈希值根据 int index 数组长度-1 哈希值存入底层的数组中对象的哈希值特点如果没有重写hashCode方法不同对象计算出来的哈希值是不同的地址值不同如果已经重写hashCode方法不同的对象只要属性值相同计算出的哈希值就是一样的在小部分情况下不同的属性值或者不同的地址值计算出来的哈希值也有可能一样哈希碰撞HashSet底层原理创建一个默认长度16默认加载因子为0.75的数组数组名table这里的加载因子就是HashSet的扩容时机情况一即当数组里面存了16*0.7512个元素后数组扩容为原来的2倍32。情况二JDK8以后当链表长度大于8而且数组长度大于等于64当前的链表自动转为红黑树提高查找效率根据元素的哈希值跟数组的长度计算出应存入的位置公式int index(数组长度-1哈希值判断当前位置是否为null如果是null直接存入如果位置不为null表示有元素则调用equals方法比较对象属性值注意这里如果集合中存储的是自定义对象必须重写equals方法。属性值一样不存 不一样存入数组形成链表因此HashSet保证了元素的唯一JDK8以前新元素存入数组老元素挂在新元素下面形成链表JDK8及以后新元素直接挂在老元素下面形成链表注意如果集合中存储的是自定义对象必须要重写hashCode和equals方法。HashSet的三个问题问题1HashSet为什么存和取的顺序不一样由于它存的方法和一个元素下挂的链表或者树。问题2HashSet为什么没有索引因为底层是数组链表红黑树一个索引下可能挂着树或链表因此去掉了索引问题3HashSet是利用什么机制保证数据去重的利用hashCode方法和equals方法利用hashCode方法计算出哈希值然后通过哈希值计算出元素存储的位置如果该位置有元素则通过equals方法比较对象内部的属性值相同则不添加不同则根据JDK不同版本处理。注如果HashSet存储的是自定义对象则需重写hashCode和equals方法练习import java.util.Objects; import java.util.Set; import java.util.HashSet; public class HashSetText1 { public static void main(String[] args) { Studentt s1 new Studentt(zhangsan,23); Studentt s2 new Studentt(lisi,24); Studentt s3 new Studentt(wangwu,25); Studentt s4 new Studentt(zhangsan,23); HashSetStudentt s new HashSet(); System.out.println(s.add(s1)); System.out.println(s.add(s2)); System.out.println(s.add(s3)); System.out.println(s.add(s4)); System.out.println(s); } } class Studentt{ String name; int age; public Studentt(){} public Studentt(String name,int age){ this.namename; this.ageage; } public void setName(String name) { this.name name; } public void setAge(int age) { this.age age; } Override public boolean equals(Object obj) { if(this obj){ return true; } if(obj null || getClass() ! obj.getClass()){ return false; } Studentt s (Studentt) obj; return ages.age Objects.equals(name, s.name); } Override public int hashCode() { return Objects.hash(name, age); } Override public String toString() { return name name , age age; } }——2、HashSet的子类LinkedHashSet直接使用Collection接口里面的常用方法就可以LinkedHashSet底层原理有序、不重复、无索引。这里的有序指的是保证存储和取出的元素顺序一致原理底层数据结构依然是哈希表只是每个元素又额外的多了一个双链表的机制记录存储的顺序即相连的元素直接互相记录一次地址地址值二第一个添加进去的元素为头结点import java.util.Objects; import java.util.LinkedHashSet; import java.util.HashSet; public class HashSetText1 { public static void main(String[] args) { Studentt s1 new Studentt(zhangsan,23); Studentt s2 new Studentt(lisi,24); Studentt s3 new Studentt(wangwu,25); Studentt s4 new Studentt(zhangsan,23); LinkedHashSetStudentt lhs new LinkedHashSet(); System.out.println(lhs.add(s1)); System.out.println(lhs.add(s2)); System.out.println(lhs.add(s3)); System.out.println(lhs.add(s4)); System.out.println(lhs); } } class Studentt{ String name; int age; public Studentt(){} public Studentt(String name,int age){ this.namename; this.ageage; } public void setName(String name) { this.name name; } public void setAge(int age) { this.age age; } Override public boolean equals(Object obj) { if(this obj){ return true; } if(obj null || getClass() ! obj.getClass()){ return false; } Studentt s (Studentt) obj; return ages.age Objects.equals(name, s.name); } Override public int hashCode() { return Objects.hash(name, age); } Override public String toString() { return name name , age age; } } 输出为 true true true false [namezhangsan, age23, namelisi, age24, namewangwu, age25] 添加顺序与取出的顺序有序2TreeSet——1、TreeSet特点和底层原理直接使用Collection接口中的常用方法即可。TreeSet的特点不重复、无索引、可排序可排序按照元素的默认规则由小到大排序。TreeSet集合底层是基于红黑树的数据结构实现排序的增删改查性能都较好。所以不需要重写hashCode和equals方法TreeSet集合默认的规则对于数值类型Integer、Double 等默认按数值大小升序排列对于字符、字符串类型Character、String 类型依据ASCII编码值升序排序自定义实体类未实现比较接口时无法直接存入 TreeSet需手动定义排序规则否则会异常错误如何选择两种排序规则默认使用第一种但是如果第一种不能满足需求则需要采用第二种排序方式。这里的满足需求是指比如我要比较Integer默认源码是升序我现在要降序第一种也能用但是不推荐修改源码所以可以使用第二种。还有比如说比较字符串源码默认使用ASCII字典序升序排序我现在要降序不可能去修改源码所以用第二种。总结非自定义类型源码中默认比较规则如果要修改该比较规则就用第二种否则用第一种默认即可。import java.util.TreeSet; import java.util.Iterator; import java.util.function.Consumer; public class TreeSetText1 { public static void main(String[] args) { TreeSetInteger ts new TreeSet(); ts.add(4); ts.add(5); ts.add(1); ts.add(3); ts.add(2); System.out.println(ts); //输出[1, 2, 3, 4, 5]默认从小到大。 IteratorInteger it ts.iterator(); while (it.hasNext()){ int i it.next(); System.out.print(i ); //输出结果1 2 3 4 5 默认从小到大、 } System.out.println(); ts.forEach( t- System.out.print(t )); } }——2、TreeSet第一种比较方式第一种比较方式默认排序/自然排序javabean类实现Comparable接口指定比较规则实现接口里面的compareTo方法例class Tiger implements ComparableTiger要比较排序的是Tiger该类的对象所以泛型接口数据类型为该类型Overridepublic int compareTo(Tiger o) {int num this.name.compareTo(o.name);//升序if(num 0){return this.age - o.age;//升序}return num;}this:表示当前要添加的元素o:表示已经在红黑树中存在的元素返回值负数认为要添加的元素是小的存左边正数认为要添加的元素是大的存右边0认为要添加的元素已经存在舍弃import java.util.Objects; import java.util.TreeSet; public class TreeSetText2 { public static void main(String[] args) { Tiger t1 new Tiger(zhangsan,23); Tiger t2 new Tiger(lisi,24); Tiger t3 new Tiger(wangwu,25); Tiger t4 new Tiger(zhang,23); TreeSetTiger tg new TreeSet(); tg.add(t1); tg.add(t2); tg.add(t3); tg.add(t4); System.out.println(tg); } } class Tiger implements ComparableTiger{ private String name; private int age; public Tiger(){} public Tiger(String name, int age) { this.name name; this.age age; } public String getName() { return name; } public int getAge() { return age; } Override public String toString() { return name name , age age; } Override public int compareTo(Tiger o) { return this.getAge() - o.getAge(); //return this.name.compareTo(o.name); } }——3、TreeSet第二种比较方式比较器排序创建TreeSet对象时候传递比较器Comparator指定规则。即使用TreeSet中的构造方法使用原则默认使用第一种方法如果第一种不能满足当前需求就使用第二种注意如果方式一和方式二同时存在那么会默认使用方式二比较器运行。TreeSetString ts new TreeSet(new ComparatorString() {Overridepublic int compare(String o1, String o2) {int i o1.length() - o2.length();if(i0) {return o1.compareTo(o2);}return i;}});o1:表示当前要添加的元素o2:表示已经在红黑树中存在的元素返回值规则和之前一样通过API帮助文档Comparator接口是函数式接口所以Lambda表达式简化TreeSetString ts new TreeSet((o1, o2) -{int i o1.length() - o2.length();if(i0) {return o1.compareTo(o2);}return i;});import java.util.TreeSet; import java.util.Comparator; public class TreeSetText3 { public static void main(String[] args){ TreeSetString ts new TreeSet(new ComparatorString() { Override public int compare(String o1, String o2) { int i o1.length() - o2.length(); if(i0) { return o1.compareTo(o2); } return i; } }); ts.add(c); ts.add(ab); ts.add(df); ts.add(qwer); System.out.println(ts); } }——4、TreeSet对象排序综合练习package TreeSetDemo; import java.util.TreeSet; import java.util.Comparator; public class TreeSetText { public static void main(String[] args) { Student s1 new Student(zhansan,23,90,99,50); Student s2 new Student(lisi,24,90,98,50); Student s3 new Student(wangwu,25,95,100,30); Student s4 new Student(zhaoliu,26,60,99,70); Student s5 new Student(qianqi,26,70,80,70); TreeSetStudent ts new TreeSet(); ts.add(s1); ts.add(s2); ts.add(s3); ts.add(s4); ts.add(s5); //System.out.println(ts); for (Student student : ts) { System.out.println(student); } } } class Student implements ComparableStudent{ String name; int age; int chinese; int math; int English; public Student() {} public Student(String name,int age,int chinese,int math,int English) { this.name name; this.age age; this.chinese chinese; this.math math; this.English English; } 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; } public int getChinese() { return chinese; } public void setChinese(int chinese) { this.chinese chinese; } public int getMath() { return math; } public void setMath(int math) { this.math math; } public int getEnglish() { return English; } public void setEnglish(int english) { English english; } public int getAllScores() { return (chinese math English); } Override public int compareTo(Student o) { int i getAllScores() - o.getAllScores(); i i 0 ? getChinese() - o.getChinese() : i; i i 0 ? getMath() - o.getMath() : i; i i 0 ? getEnglish() - o.getEnglish() : i; i i 0 ? getAge() - o.getAge() : i; i i 0 ? getName().compareTo(o.getName()) : i; return i; } Override public String toString() { return Student{ name name \ , age age , chinese chinese , math math , English English }; } }