[数据结构与算法]比较器 set map 散列

比较器 set map 散列

set

特点:无序不可重复,添加和取出顺序可能不一致
Set ->SortedSet ->TreeSet:底层是红黑树,要添加元素必须按照人家的规则排序

TreeSet

• 使用

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.TreeSet;
public class Collection_05_HashSet {
public static void main (String[]args) throws ParseException{
	//String,Integer,Date
	TreeSet treeSet = new TreeSet();
	//数字按照升序排序
	treeSet.add(2);
	treeSet.add(3);
	treeSet.add(21);
	System.out.println(treeSet);
	//字符串按照ASCII升序排序
	//每位比较,相同就比较后一位
	treeSet = new TreeSet();
	treeSet.add("12");
	treeSet.add("22");
	treeSet.add("32");
	treeSet.add("1");
	//[1 12 22 32]
	System.out.println(treeSet);
	//时间日期
	String strTime1 = "2021.01.01";
	String strTime2 = "2021.02.01";
	String strTime3= "2022.01.10";
	String strTime4= "2021.11.01";
	String strTime5 = "2022.01.01";
	treeSet = new TreeSet();
	SimpleDateFormat sdf =new SimpleDateFormat("yyyy.MM.dd");
	Date d1   = sdf.parse(strTime1);
	Date d2  = sdf.parse(strTime2);
	Date d3  = sdf.parse(strTime3);
	Date d4 = sdf.parse(strTime4);
	Date d5 = sdf.parse(strTime5);
	treeSet.add(strTime1);
	treeSet.add(strTime2);
	treeSet.add(strTime3);
	treeSet.add(strTime4);
	treeSet.add(strTime5);
	System.out.println(treeSet);
}
}

底层因为String,Integer,Date都实现了Comparable接口的compareTo()方法,所以可以排序,但是想添加其他元素,尤其是自定义类型,必须实现Comparable接口的compareTo()方法.
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-64ym7MSY-1626440876528)(2021-07-16-20-28-46.png)]

排序(比较器)

概述
比较器类 有两种

•   1 java.lang.Comparable 接口 并实现 compareTo方法
  

•   2 java.util.Comparator 比较器类
  

• 为什么 String , Integer , Date 能排序? 其他类型行不行
  因为他们三个类都实现了Comparable接口 并实现了compareTo()方法而 往treeSet中添加数据的时候,会自动调用该对象的 compareTo方法,因此 他们可以排序
  但是如果我们想添加其他元素,尤其是自定义类型的时候,就不行了,需要实现Comparable接口 并实现了compareTo()方法.

Comparable

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4akDNcsS-1626440876529)(2021-07-16-20-34-03.png)]
如果我们的自定义类型想要放到treeSet中,必须实现Comparable接口,否则就无法使用treeSet进行数据保存
实例

import java.util.TreeSet;
public class Collection_02_SortedSet_02 {
public static void main (String[]args){
	TreeSet treeSet = new TreeSet();
	treeSet.add(new User(12));
	treeSet.add(new User(13));
	treeSet.add(new User(11));
	System.out.println(treeSet);
}
}
class User implements Comparable{
	int age;
	@Override
	public String toString() {
		return "User [age=" + age + "]";
	}	
	public User(int age) {
		super();
		this.age = age;
	}
	@Override
	public int compareTo(Object o) {
		//this是要添加的元素,o是集合中的每一个元素
		//返回值为0,相等不添加
		//返回-1说明添加的比集合中的小,就放在前面
		//返回1,说明添加的大放后边
		if(o instanceof User){//判断是同类型的
			User user = (User) o;
			//升序
			//return this.age-user.age;
			//降序
			return user.age-this.age;
		}
		return -1;
	}	
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vNs5PiGC-1626440876530)(2021-07-16-20-36-28.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ischr2KW-1626440876532)(2021-07-16-20-37-10.png)]

Comparator

使用场景
比如我们现在要保存 数字 , 并且是降序排序

而 Integer中 默认是升序,我们没有办法更改他的源码,所以可以使用Comparator解决该问题,通过treeMap源码发现,Comparator优先级 大于 Comparable,所以 我们可以利用Comparator的优先级,来自定义排序规则
我们自定义类型 需要排序,优先使用Comparable来实现,这样 如果不能满足别人的需求,还可以通过comparator对排序进行扩展
我们操作的是别人定义的类型的话,都需要使用comparator进行扩展,因为你改不了人家源码
1 本来有排序,比如Integer,默认升序,但是不能满足我们的排序需求,此时需要使用comparator进行扩展
2 不支持排序,也就是说该类型没有实现comparable接口,不能排序.但是此时我们需要排序,也可以通过comparator进行扩展
3 总之 其他类型.无法满足我们的排序规则的时候,都可以使用comparator进行扩展排序
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bmWgpkKK-1626440876533)(2021-07-16-20-42-31.png)]
使用

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Collection_04_ListSort {
public static void main (String[]args){
	ArrayList arrayList = new ArrayList();
	arrayList.add(2);
	arrayList.add(23);
	arrayList.add(42);
	arrayList.add(21);
	arrayList.add(12);
	//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);	
}
}

匿名内部类方法

import java.util.Comparator;
import java.util.TreeSet;
public class Collection_03_Comparator_02 {
public static void main(String[]args){
	TreeSet treeSet = new TreeSet (new Comparator(){
	public int compare(Object o1, Object o2) {
		//o1是要添加的元素,o2是集合中的元素
		Integer i1 = (Integer)o1;
		Integer i2 = (Integer)o2;
		// i1-i2是升序, i2-i1是降序
		return i1-i2;
	}	});
	treeSet.add(22);
	treeSet.add(222);
	treeSet.add(2);
	treeSet.add(12);
	System.out.println(treeSet);
}
}

Collections

• list想要排序,元素必须实现comparable接口如果元素自身没有实现comparable接口,是不能调用sort方法的,会报错但是 想要比较也可以,不管他是否实现comparable接口,或者是排序规则不是我们想要的都可以使用comparator进行比较,那么sort方法有一个重载,接收comparator

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Collection_04_ListSort {
public static void main (String[]args){
	ArrayList arrayList = new ArrayList();
	arrayList.add(2);
	arrayList.add(23);
	arrayList.add(42);
	arrayList.add(21);
	arrayList.add(12);
	//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);	
}
}

如果 添加的元素 是我们写的,那么我们应该使用comparable进行排序,因为对扩展开放,当满足不了别人需求的时候,人家还可以使用comparator进行扩展
如果 添加的元素 不是我们写的,是别人写的,那么我们肯定不能更改人家的源码
此时我们可以通过comparator进行重新排序
因为comparator和comparable同时存在的时候,comparator优先级要高

树

二叉查找树

类似于二分法查找,查询效率比较高
左叶子 用于小于根节点的值
右叶子 永远大于根节点的值
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KMHLoU80-1626440876534)(2021-07-16-20-51-35.png)]
这种方式是二分查找的思想,查询所需要的最大次数,等同于二叉树的高度
在添加数据的时候,也是类似的方式,一层层找,一直找到适合新节点的位置
但是二叉查找树也有问题
比如 一直添加比根节点小的或者大的数据
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r28NmiSk-1626440876534)(2021-07-16-20-52-10.png)]
这样的结构,虽然符合二叉查找树特性,但是性能大打折扣,几乎变成了线性的

红黑树

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

• 规则
  1 节点是红色或者黑色
  2 根节点一定是黑色
  3 每个子节点都是黑色的空节点
  4 每个红节点的两个子节点都是黑色(从每个叶子到根节点的路径上不能有连续两个的红色节点)
  5 从任何节点到其每一个子节点都有相同数量的黑色节点
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pCPeyCgB-1626440876535)(2021-07-16-20-53-42.png)]
• 出问题先变色不行就旋转
  左旋转 : 逆时针旋转,父节点被右节点取代,而自己成为左节点
  右旋转 : 顺时针旋转,父节点被左节点取代,而自己成为右节点
  右边黑色数量多,就左旋转
  左边黑色数量多,就右旋转

HashSet

散列表(哈希表)

散列表 : 数组中保存的链表
HashSet 底层就是HashMap 的key部分,屏蔽了HashMap的value,而HashMap底层是散列表

• 添加过程 :
  1 根据key生成hash值(hashCode方法)
  2 根据生成hash值,通过hash算法得到数组下标i = (n - 1) &hash
  3 调用key的equals方法,和数组中对应的链表的每一个节点进行比较
  4 如果不存在,就添加进去,如果存在,就不添加
  5 java8开始.,引入了红黑树,如果链表个数 大于等于9 就把链表转型为红黑树 从而加快查询效率
  覆写equals的时候 还需要考虑hashCode 因为需要使用hashCode和equals共同表示对象的唯一性

1.调用 key的hashCode方法生成hash值,所以记得重写
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q568AgDq-1626440876536)(2021-07-16-21-01-19.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XiWfidQv-1626440876536)(2021-07-16-21-01-28.png)]
2.散列存储方式
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ofR57Sms-1626440876537)(2021-07-16-21-01-49.png)]
3.生成数组索引
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ffwq3vpB-1626440876537)(2021-07-16-21-02-08.png)]
4.判断数组对应索引中是否有节点
5.没有节点 直接添加
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sPJY6q3N-1626440876538)(2021-07-16-21-02-42.png)]
6.有节点 判断是否存在当前元素
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x9WRkEHS-1626440876538)(2021-07-16-21-03-14.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6m4iW6t6-1626440876539)(2021-07-16-21-03-24.png)]
7.如果链表中节点个数大于等于8 就转为树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WKl4gXt2-1626440876540)(2021-07-16-21-03-46.png)]

添加方法应用

import java.util.HashSet;
public class Collection_01_SortedSet_01 {
public static void main(String[]args){
	HashSet set = new HashSet();
	set.add("a");
	set.add("b");
	set.add("c");
	set.add("d");
	set.add("e");
	System.out.println(set);
	for(Object obj : set){
		System.out.println(obj);
	}	
}
}