set和排序
概述
set特点 无序，不可重复，添加顺序和取出顺序不一定一致
set->SortedSet->TreeSet;底层时红黑树，要添加的元素必须按照某个规则进行排序
TreeSet
概述
set特点 无序，不可重复，添加顺序和取出顺序不一定一致
set->SortedSet->TreeSet;底层时红黑树，要添加的元素必须按照某个规则进行排序
数字默认升序，字符串默认比较每一位的ASCII码值，时间默认自然日期(昨天，今天，明天)
使用
package day_7_16;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.TreeSet;
/**
*
*
* set特点 : 无序 不可重复,添加顺序和取出顺序不一定一致
*
* Set -> SortedSet -> TreeSet : 底层是红黑树,要添加的元素必须按照某个规则进行排序
*
* 数字 默认升序 , 字符串 默认比较每一位的ASCII码值 , 时间 默认自然日期(昨天,今天,明天,后天...)
*
* 为什么 String , Integer , Date 能排序? 其他类型行不行
* 因为他们三个类都实现了Comparable接口 并实现了compareTo()方法
* 而 往treeSet中添加数据的时候,会自动调用该对象的 compareTo方法,因此 他们可以排序
* 但是如果我们想添加其他元素,尤其是自定义类型的时候,就不行了,需要实现Comparable接口 并实现了compareTo()方法
*
*
* @author 啊超
* @Date 2021年7月16日
*/
public class Collection_01_SortedSet_1 {
public static void main(String[] args)throws ParseException {
//String,Integer,Date
TreeSet treeSet=new TreeSet ();
//数字按照升序排序
treeSet.add(2);
treeSet.add(8);
treeSet.add(7);
treeSet.add(3);
treeSet.add(6); [2, 3, 6, 7, 8]
System.out.println(treeSet);
//字符串按照 ASCII升序排序
//每位比较，相同则比较后面一位
treeSet=new TreeSet();
//[1，10，12，2]
treeSet.add("1");
treeSet.add("2");
treeSet.add("10");
treeSet.add("12");
System.out.println(treeSet); //[1, 10, 12, 2]
//时间 自然日期
treeSet = new TreeSet();
String strTime1="2021-07-15";
String strTime2="2021-07-13";
String strTime3 = "2020-08-15";
String strTime4 = "2022-02-11";
SimpleDateFormat a = new SimpleDateFormat("yyyy-MM-dd");
Date d1= a.parse(strTime1);
Date d2= a.parse(strTime2);
Date d3= a.parse(strTime3);
Date d4= a.parse(strTime4);
treeSet.add(strTime1);
treeSet.add(strTime2);
treeSet.add(strTime3);
treeSet.add(strTime4);
System.out.println(treeSet);
}
}
为什么会排序？其他类型行不行
为什么String,Integer,Date能排序？其他类型行不行
因为他们三个类都实现了Comparable接口，并实现了compareTo() 方法
而往streeSet中添加数据的时候，会自动调用对象的compareTo方法，因此他们可以排序
但是如果我们想添加其他元素，尤其是自定义类型的时候就不行了，需要实现Comparable接口，并实现了compareTo()方法
?树
二叉查找树
类似于二分法查找，查询效率比较高
左叶子 用于小于根节点的值
右叶子 永远大于根节点
?
这中方式是二分查找的思想，查询所需要的最大次数，等同于二叉树的高度
在添加数据的时候，也是类似的方式一层层找，直到找到适合的新节点的位置
但是二叉查找树也有问题
比如 一直添加比根节点小的或者大的数据
?
这样的话，虽然符合二叉查找树特性，但是性能大打折扣，几乎变成了线性的
红黑树
?为了解决二叉查找树多次插入新节点而导致的不平衡，红黑树就诞生了
完全符合二叉查找的特性
1节点是红色或者黑色
2根节点一定是黑色
3每个子节点一定是黑色
4每个红节点的两个子节点都是黑色（从每个叶子到根节点的路径上不能有连续两个的红色节点）
5 从任何节点到其每一个子节点都有相同数量的黑色节点
?
左旋转；逆时针旋转，父节点被右节点取代，而自己成为左节点
右旋转；顺时针转，父节点被左节点取代，而自己成为右节点
右边黑色数量多，就左旋转
左边黑色多，就右旋转
排序
概述
比较器类有两种
1 java.lang.Comparable接口并实现compareTo方法
2java.until.Comparator比较类
为什么String，Integer，Date能排序？其他类行不行
因为他们三个类都实现了Comparable接口，并实现了compareTo方法
而往treeSet添加数据的时候，会自动调用该对象的compareTo方法，他们可以排序
但是如果我们想添加其他元素，尤其是自定义类型的时候就不行了，需要实现Comparable接口。并实现了compareTo()方法
Comparable
?如果我们的自定义类型想要放到treSet中，必须实现Comparable接口，否则就无法使用treeSet进行数据保存
?
package day_7_16;
import java.util.TreeSet;
/**
*
* 比较器类 有两种
* 1 java.lang.Comparable 接口 并实现 compareTo方法
* 2 java.util.Comparator 比较器类
*
* 为什么 String , Integer , Date 能排序? 其他类型行不行
* 因为他们三个类都实现了Comparable接口 并实现了compareTo()方法
* 而 往treeSet中添加数据的时候,会自动调用该对象的 compareTo方法,因此 他们可以排序
* 但是如果我们想添加其他元素,尤其是自定义类型的时候,就不行了,需要实现Comparable接口 并实现了compareTo()方法
*
* @author 啊超
* @Date 2021年7月16日
*/
public class Collection_02_SortedSet_2 {
public static void main(String[] args){
//Exception in thread "main" java.lang.Error: Unresolved compilation problems:
TreeSet treeSet=new TreeSet();
treeSet.add(new user(12));
treeSet.add(new user(10));
treeSet.add(new user(14));
System.out.println(treeSet); //[user[age=14], user[age=10], user[age=12]]
}
}
class user implements Comparable{
int age;
public String toString(){
return "user[age="+age+"]";
}
public user(int age){
this.age=age;
}
@Override
public int compareTo(Object o) {
// this 是要要添加的元素 , o 是集合中的每一个元素
// 返回值为0 , 说明相等, 就不添加
// 返回小于0 的, 说明要添加的元素比集合中的元素小,就放到前面
// 返回大于0的,说明要添加的元素比集合中的元素大,就放到后面
if(o instanceof user){
user user=(user)o;
//升序
//return this.age-user.ang;
//降序
//return user.age-this.age;
}
return -1;
}
}Comparator
概述
比如我们现在要保存数字，并且是降序排序
而Integer中，默认是升序，我们没有办法更没有办法更改别人的源码，所以可以使用Comparator解决该问题，通过treeMap源码发现Comparator优先级大于Comparable
?使用
保存数字，并降序
package day_7_16;
import java.util.Comparator;
import java.util.TreeSet;
/**
* 应用场景
*
* 比如我们现在要保存 数字 , 并且是降序排序
*
* 而 Integer中 默认是升序,我们没有办法更改他的源码,所以可以使用Comparator解决该问题
*
* 通过treeMap源码发现,Comparator优先级 大于 Comparable
*
* 所以 我们可以利用Comparator的优先级,来自定义排序规则
*
* 我们自定义类型 需要排序,优先使用Comparable来实现,这样 如果不能满足别人的需求,还可以通过comparator对排序进行扩展
*
* 我们操作的是别人定义的类型的话,都需要使用comparator进行扩展,因为你改不了人家源码
* 1 本来有排序,比如Integer,默认升序,但是不能满足我们的排序需求,此时需要使用comparator进行扩展
* 2 不支持排序,也就是说该类型没有实现comparable接口,不能排序.但是此时我们需要排序,也可以通过comparator进行扩展
* 3 总之 其他类型.无法满足我们的排序规则的时候,都可以使用comparator进行扩展排序
*
* @author 啊超
* @Date 2021年7月16日
*/
public class Collection_03_Comparator {
public static void main(String[] args) {
//Integer
//TreeSet treeSet=new TreeSet(new Scor Test());
//匿名内部类
TreeSet treeSet=new TreeSet(new Comparator(){
@Override
public int compare(Object o1, Object o2) {
//o1是要添加的数， o2是集合中的元素
Integer i1=(Integer)o1;
Integer i2=(Integer)o2;
return i2-i1;
}
});
treeSet.add(22);
treeSet.add(15);
treeSet.add(45);
treeSet.add(24);
System.out.println(treeSet); //[45, 24, 22, 15]
}
}Collections
list想要排序，元素必须实现comparable接口
如果元素自身没有实现comparable接口，是不能调用sort方法的，会报错
但是想要比较也可以，不管他是否实现comparable接口，或者是排序规则不是我们想要的，都可以使用comparator进行比较，那么sort方法有一个重载，接收comparator
package day_7_16;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
/**
*
* list想要排序,元素必须实现comparable接口
*
* 如果元素自身没有实现comparable接口,是不能调用sort方法的,会报错
*
* 但是 想要比较也可以,不管他是否实现comparable接口,或者是排序规则不是我们想要的
*
* 都可以使用comparator进行比较,那么sort方法有一个重载,接收comparator
*
* @author 啊超
* @Date 2021年7月16日
*/
public class Collection_04_ListSort {
public static void main(String[] args){
ArrayList arrayList=new ArrayList();
arrayList.add(2);
arrayList.add(22);
arrayList.add(12);
arrayList.add(4);
// Collections.sort(arrayList);
Collections.sort(arrayList,new Comparator(){
@Override
public int compare(Object o1, Object o2) {
Integer i1=(Integer)o1;
Integer i2=(Integer)o2;
return i2-i1;
}
});
System.out.println(arrayList); //[22, 12, 4, 2]
}
}
总结
? ? ? ? 如果添加的元素是我们写的，那么我们应该使用comparable进行排序，因为对扩展开放，当满足不了别人需求的时候，别人还可以使用comparator精心扩展
? ? ? ?如果添加的元素 不是我们写的，是别人写的，那么我们不能修改别人的源代码，我们应该使用comparator进行重新排序，因为comparator和comparable同时存在的时候，comparator优先级要高
HashSet
散列表
?1调用key的hashCode方法生成hash值，所以一定要记住重写
?
?2散列存储方式
?3生成数组索引
?4 判断数组对应索引中是否有节点
5 没有节点 直接添加
?6 有节点 判断是否存在当前元素
?
?7 如果链表中节点个数大于等于8 就转为树
?
HashSet
?