[数据结构与算法]Java学习第20天学习日志

Day20 比较器、set、map、散列

1. ?Set和排序
   1. ?

Set特点:无序不可重复,添加和取出顺序不一定一致

Set->SortedSet->TreeSet:底层是红黑树,要添加的元素必须按照某个规则进行排序

1. 1. TreeSet
      1. ?概述

数字默认公开,字符串,默认比较每一位的ASCII码值,时间,默认自然日期

1. 1. 1. ?使用

TreeSet?treeSet=new?TreeSet();

//数字按照升序排序

treeSet.add(2);

treeSet.add(3);

treeSet.add(4);

treeSet.add(1);

System.out.println(treeSet);

treeSet=new?TreeSet();

//字符串按照ASCII升序排序

//每位比较,相同的则比较后面一位

treeSet.add("1");

treeSet.add("12");

treeSet.add("10");

treeSet.add("5");

System.out.println(treeSet);

1. 1. 1. ?为什么会排序?其他类型行不行?

因为他们三个都是实现了Comparable接口并实现了compareto()方法

??而 往treeSet中添加数据的时候,会自动调用该对象的compareTo()方法,因此 他们可以排序

??但是如果我们想添加其他元素,尤其是自定义类型的时候,就不行了,需要实现Comparable接口并实现了CompareTo接口

1. 1. 1. 树
         1. ?二叉查找树

类似于二分法查找,查询效率比较高

左叶子 用于小于根节点的值

右叶子 永远大于根节点的值

这种方式是二分查找的思想,查询所需要的最大次数,等同于二叉树的高度

在添加数据的时候,也是类似的方式,一层层找,一直找到适合新节点的位置

但是二叉查找树也有问题

比如 一直添加比根节点小的或者大的数据

这样的话,虽然符合二叉查找树特性,但是性能大打折扣,几乎变成了线性的

1. 1. 1. 1. 红黑树

为了解决二叉查找树多次插入新节点而导致的不平衡,红黑树就诞生了

完全符合二叉查找的特性

1 节点是红色或者黑色

2 根节点一定是黑色

3 每个子节点都是黑色的空节点

4 每个红节点的两个子节点都是黑色(从每个叶子到根节点的路径上不能有连续两个的红色节点)

5 从任何节点到其每一个子节点都有相同数量的黑色节点

左旋转 : 逆时针旋转,父节点被右节点取代,而自己成为左节点

右旋转 : 顺时针旋转,父节点被左节点取代,而自己成为右节点

右边黑色数量多,就左旋转

左边黑色数量多,就右旋转

1. 1. ?排序
      1. Comparator
         1. ?概述

应用场景

?* 比如我们现在要保存数字,并且是降序排序

?* 而Integer中 默认是升序,我们没有办法更改他的源码,所以可以使用Comparator解决该问题

?* 通过treeMap源码发现,Comparator的优先级大于Comparble

?* 所以我们可以利用Comparator的优先级来自定义排序规则

?* 我们自定义类型,需要排序优先使用Comparable来实现这样如果不能满足别人的需求,还可以通过comparator对排序进行扩展

?* 我们操作的是别人定义的类型的话,都需要使用comparator进行扩展,因为你改变不了对方的源码

?* 1本来有排序,比如Integer,默认升序,但是不能满足我们的排序需求,此时需要使用comparator进行扩展

?* 2.不支持排序,也就是说改类型没有实现comparable接口,不能排序,但是此时我们需要排序,也可以通过comparator进行扩展

?* 3.总之其他类型,无法满足我们的排序规则的时候,都可以使用comparator进行扩展序列

1. 1. 1. 1. ?使用
      2. ?Collections

list想要排序,元素必须实现comparable

?* 如果元素自身没有实现comparable接口,是不能调用sort方法的,会报错

?* 但是想要比较也可以,不管他是否实现comparable接口,或者是排序规则不是我们想要的

?* 都可以使用comparator进行比较,那么sort方法有一个重载,接受comparator

1. 1. 1. 散列表
      2. HashSet

散列表;数组中保存的链表

?* HashSet底层就是Hashmap的key部分,屏蔽了HashMap的value

?* 而HashSet底层是散列表

?* 添加过程:1.根据key生成的hash值(hashCode方法)

?* 2.根据生成的hash值,通过hash算法得到数组下标

?* 3.调用key的equals方法,和数组中对应的没一个节点进行比较

?* 4.如果不存在,就添加进去,如果存在就不添加

?* 5.java8开始,引入了红黑树,如果链表个数大于等于九就把链表转型为红黑树 从而加快查询效率

?* hashCode因为需要使用hashcode和equals共同表示对象的唯一性