Set接口
Set接口中没有定义额外的新的方法，使用的都是Collection中声明的方法
存储数据特点
无序的，不可重复的数据
-
无序性
- 不等于随机性
- 以HashSet为例说明
- 存储的数据在底层数组中并非按照数组索引的顺序进行添加，而是根据数据的哈希值决定的
-
不可重复性
- 保证添加的元素按照equals()判断时，不能返回true，即相同的元素只能添加一个
要求
-
向Set中添加数据，其所在的类一定要重写hashCode()和equals()方法，两个方法可以自动生成
（如果没有重写hashCode()方法，相当于系统随机安排一个数字给该元素的hash值，即使两个元素相同，但是他们的hash值不同，还是会添加到数组中。重写hashCode()，两个元素的hash值根据同一个逻辑算出）
-
重写的hashCode()和equals()方法尽可能保持一致性
-
相等的对象必须具有相等的散列码（哈希值）
自动生成的hashCode()方法中会出现31这个系数的原因
- 选择系数的时候尽量选择大的系数，计算出的hash值越大，“冲突”就越少，查找起来效率也会提高
- 31占用5bits，相乘造成的数据溢出的概率较小
- 31是个素数，素数本身只能被本身和1整除，可以减少冲突
HashSet（主要实现类）
添加元素的过程
（hashSet底层是一个数组，长度为16）
图解
过程
底层：数组 + 链表
- 向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值
- 此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为索引位置）
- 判断数组此位置上是否已有元素
-
如果此位置没有其他元素，则元素a添加成功
-
如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较a与元素b的哈希值
（存放位置相同的两个元素哈希值不一定相同）
- 如果hash值不相同，则元素添加成功
- 如果hash值相同，进而调用元素a所在的equals()方法
- equals()返回true，元素a添加失败
- equals()返回false，元素a添加成功
-
说明
两个元素的hash值不同或者equals返回false时，元素a与已经存在指定索引位置上的数据以链表的方式存储
- jdk7：元素a放到数组中，指向原来的元素
- jdk8：原来的元素在数组中，指向元素a
- 总结：七是头插法，八是尾插法（七上八下）
LinkedHashSet
- HashSet的子类
- 遍历其内部数据是可以按照添加的顺序去遍历
注意：即使遍历出的数据顺序是按照添加顺序显示的，但是LinkedHashHashSet中的数据特点依旧是无序的，不可重复的
添加元素的过程
- 在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据的地址值
- 优点：对于频繁的遍历操作，使用LinkedHashSet效率高于HashSet
TreeSet
- 要求放入的数据属于同一个类的对象
- 可以按照添加对象的指定属性，进行排序
- 会使用到Comparable和Comparator两个排序接口
- 底层采用红黑树存储结构（小放左，大放右），其特点是有序，查询速度比List快
注意：向TreeSet中添加的数据，要求是相同类的对象
自定义类两种排序方式（Java比较器）
https://www.cnblogs.com/CrabDumplings/p/13339146.html
自然排序（实现Comparable接口）
比较两个函数是否相同的标准为compareTo()方法返回0，不再是equals()方法
代码实现
- 普通情况，按照名字进行排序
//Students类中的compareTo方法，按照名字进行排序
public int compareTo(Object o) {
if(o instanceof Students){
Students s = (Students)o;
return this.name.compareTo(s.name);
}else{
throw new RuntimeException("传入数据类型不一致");
}
}
//测试函数
public void test13(){
TreeSet set = new TreeSet();
set.add(new Students("Tom",18,90));
set.add(new Students("Ann",19,75));
set.add(new Students("Lisa",20,86));
set.add(new Students("Jack",21,50));
set.add(new Students("Jerry",19,60));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
运行结果
-
排序的信息有相同的情况（名字相同，其他信息不相同）
利用二次排序
按照名字进行比较，如果名字相同，在compareTo中比较返回值为0（TreeSet中判断是否相同的标准不再是equals，而是compareTo）
//姓名从小到大排列，姓名相同的年龄从小到大排列
@Override
public int compareTo(Object o) {
if(o instanceof Students){
Students s = (Students)o;
// return this.name.compareTo(s.name);
int compare = this.name.compareTo(s.name);
//姓名不一样
if(compare != 0){
return compare;
}else {
//姓名一样
return Integer.compare(this.age,s.age);
}
}else{
throw new RuntimeException("传入数据类型不一致");
}
@Test
public void test13(){
TreeSet set = new TreeSet();
set.add(new Students("Tom",18,90));
set.add(new Students("Ann",19,75));
set.add(new Students("Lisa",20,86));
set.add(new Students("Jack",21,50));
set.add(new Students("Jerry",19,60));
set.add(new Students("Jerry",22,70));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
运行结果
定制排序（实现Comparator接口）
在定制排序中，比较两个对象是否相同的标准为compare()，是否返回0，不再是equals()方法
TreeSet set = new TreeSet();
构造器没有参数的时候直接为自然排序
TreeSet set = new TreeSet(com);
构造器有蚕食的时候，按照com的定制排序进行排序
代码实现
- 普通情况，按照年龄进行排序
//年龄从小到大进行排序
public void test14(){
Comparator com = new Comparator() {
//按照年龄从小到大排列
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof Students || o2 instanceof Students){
Students s1 = (Students)o1;
Students s2 = (Students)o2;
return Integer.compare(s1.getAge(),s2.getAge());
}else{
throw new RuntimeException("传入数据类型不一致");
}
}
};
TreeSet set = new TreeSet(com);
set.add(new Students("Tom",18,90));
set.add(new Students("Ann",19,75));
set.add(new Students("Lisa",20,86));
set.add(new Students("Jack",21,50));
set.add(new Students("Jerry",19,60));
set.add(new Students("Jerry",22,70));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
运行结果
- 排序的信息有相同的情况（年龄相同，其他信息不相同）
public void test14(){
Comparator com = new Comparator() {
//按照年龄从小到大排列
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof Students || o2 instanceof Students){
Students s1 = (Students)o1;
Students s2 = (Students)o2;
// return Integer.compare(s1.getAge(),s2.getAge());
int compare = Integer.compare(s1.getAge(), s2.getAge());
if(compare != 0){
return Integer.compare(s1.getAge(),s2.getAge());
}else{
return s1.getName().compareTo(s2.getName());
}
}else{
throw new RuntimeException("传入数据类型不一致");
}
}
};
TreeSet set = new TreeSet(com);
set.add(new Students("Tom",18,90));
set.add(new Students("Ann",19,75));
set.add(new Students("Lisa",20,86));
set.add(new Students("Jack",21,50));
set.add(new Students("Jerry",19,60));
set.add(new Students("Jerry",22,70));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
运行截图
