【轻松掌握数据结构】Map和Set

第六章 Map和Set

文章目录

• 第六章 Map和Set
• 前言
• 一、搜索树
• • 1.搜索树是什么？
  • 2.查找
  • 3.插入
  • 4.删除
  • 5.性能分析
• 二、搜索
• • 1.场景
  • 2.基本模型
• 三、Map
• • 1.概念
  • 2.常见用法
  • 3.注意事项
  • 4.使用案例
• 四、Set
• • 1.概念
  • 2.常见用法
  • 3.注意事项
  • 4.使用案例
• 五、哈希表
• • 1.概念
  • 2.哈希冲突
  • • 2.1概念
    • 2.2如何避免冲突
    • • （1）哈希函数
      • （2）负载因子调节
  • 3. 解决哈希冲突
  • • 3.1 闭散列
    • 3.2 开散列（重要）
  • 4. 性能分析
• 总结

前言

好久不见啊！今天让我为大家讲解数据结构中最受瞩目的一对搭档——Map和Set. 这乍一听有些抽象，别急，让我为你慢慢解答~

首先让我们了解一下搜索树这个概念~

一、搜索树

1.搜索树是什么？

二叉搜索树又称二叉排序树，它或者是⼀棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

举例：arr[]={5,3,8,1,0,9,4}

2.查找

private Node root =null;

//查找
public Node search(int a){
Node ter=root;
while(ter!=null ){
if (ter.key == a) {
return ter;
} else if (a > ter.key) {
ter = ter.rigth;
} else {
ter = ter.left;
}
}
return null;
}

3.插入

//插入
public boolean insert(int a){
if(root==null){
root=new Node(a);
return true;
}
int wa=0;//rigth
int we=0;//left

Node ter=root;
Node parent=root;
while(ter!=null){
if (ter.key == a) {
return false;
} else if (a > ter.key) {
parent=ter;
ter = ter.rigth;
wa=1;
we=0;
} else {
parent=ter;
ter = ter.left;
wa=0;
we=1;
}
}
Node der=new Node(a);
if(wa==1){
parent.rigth=der;
}else{
parent.left=der;
}
return true;
}

这里用wa,we来判断左右子树似乎有点麻烦了，动动脑筋，有没有更好的办法呢？结尾公布！

4.删除

//删除
public boolean remove(int a){
Node parent=null;
Node ter=root;
while(ter!=null ){
if (ter.key == a) {
break;
} else if (a > ter.key) {
parent=ter;
ter = ter.rigth;
} else {
parent=ter;
ter = ter.left;
}
}
if(ter == null){
return false;
}

Node cur=ter;

while(cur!=null) {
if (cur.rigth != null && cur.left != null) {
parent = cur;
cur = cur.rigth;
} else if (cur.left!=null) {
parent = cur;
cur=cur.left;
} else if (cur.rigth!=null) {
parent = cur;
cur=cur.rigth;
}else {
break;
}
}
ter.key= cur.key;
if(parent.left==cur){
parent.left=null;
}else {
parent.rigth=null;
}
return true;
}

5.性能分析

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： O(logN) 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N

读到这里你已经打败了50%的人！也许你还在疑惑，这搜索树和Map,Set有什么关系？现在让我来偷偷告诉你——搜索树是"引擎"，Map/Set 是"车型"：搜索树是底层数据结构，Map/Set 是基于它（或哈希表）实现的容器接口。 ok,现在让我们正式进入Map，Set的学习！

二、搜索

1.场景

试想一下，现在我们要做一个根据姓名查询考试成绩的系统，你会怎么实现查询功能？

而且我们可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是⼀种适合动态查找的集合容器。

2.基本模型

⼀般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

• 有⼀个英文词典，快速查找⼀个单词是否在词典中。

• 常见的英语字典里面，除了能查找到单词，还能在对应的词后面看见它四级考试中出现的次数。

提前预告一下，在下面的讲解中，出现Tree这一坨东西的地方需要让传入的key元素可比较，而Hash不用，接下来的举例我会大量使用Tree，结尾会单独讲到Hash

三、Map

1.概念

Map是⼀个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K⼀定是唯一的，不能重复。

2.常见用法

3.注意事项

4.使用案例

//这里用Tree来举例，结尾会单独讲到Hash
public class TreeMap {
public static void main(String[] args) {
Map<String,Integer> ter=new TreeMap<>();
ter.put("你好",4);
ter.put("我很好",9);
ter.put("它好吗",14);

//会得到对应的value
System.out.println(ter.get("你好"));
//不存在，返回null
System.out.println(ter.get("我不好"));

//看key存不存在，存在返回原本原本的value，不存在返回我输入的默认值，也就是第二个参数
System.out.println(ter.getOrDefault("它好吗",0));
System.out.println(ter.getOrDefault("我不好",7));

//如果有过相同的key，则对应的value会替换掉旧的value
//value可以等于null,但是key不可以
ter.put("我很好",56);
System.out.println(ter.get("我很好"));

//移除，对应的value会变成null
ter.remove("你好");
System.out.println(ter.get("你好"));

//打印所有的key,不会有重复的
for(String a: ter.keySet()){
System.out.println(a);
}

//打印所有value，可以有重复的，如果里面存在null,这里会报错
for(int a: ter.values()){
System.out.println(a);
}

//返回所有映射关系
for(Map.Entry<String,Integer> a:ter.entrySet()){
System.out.println(a.getKey()+"–>"+a.getValue());
}

//是否包含key
System.out.println(ter.containsKey("它好吗"));
System.out.println(ter.containsValue(23));

//打印当前ter里面的东西和组数
System.out.println(ter);
System.out.println(ter.size());

}

四、Set

1.概念

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。

2.常见用法

3.注意事项

4.使用案例

public static void main(String[] args) {
Set<String> ter=new TreeSet<>();
//添加元素
ter.add("你瞅啥");
ter.add("瞅你咋地");
ter.add("在干嘛");
//添加成功返回true，失败，也就是是重复元素的时候，返回false
System.out.println(ter.add("打电话"));
System.out.println(ter.add("你瞅啥"));

//判断原宿是否在集合中
System.out.println(ter.contains("你瞅啥"));
System.out.println("——");
//迭代器
for (Iterator<String> it = ter.iterator(); it.hasNext(); ) {
String a = it.next();
System.out.println(a);
}
//删除成功返回true
System.out.println(ter.remove("你瞅啥"));
//返回原宿个数
System.out.println(ter.size());

//看集合中的元素set里都存不存在，都存在返回true
LinkedList<String> arr=new LinkedList<>();
arr.add("打电话");
arr.add("在干嘛");
System.out.println(ter.containsAll(arr));//Arrays里面有个.asList数组变列表试试

//
LinkedList<String> crr=new LinkedList<>();
crr.add("打电话");
crr.add("在上学");
System.out.println(ter.addAll(crr));

//将元素转换为数组返回
Object[] err=ter.toArray();
System.out.println(Arrays.toString(err));

//清空
ter.clear();
//判断是否为空,为空返回true
System.out.println(ter.isEmpty());
}

五、哈希表

1.概念

在以往查找元素的过程中，必须要经过关键码的多次比较，需要耗费一定时间。那有没有一种理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素？ 有的！^ ^ 如果构造⼀种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一映射的关系，那么在查找时通过该函数可以很快找到该元素！

现在让我们模拟创建一下，向该结构中：

• 插入元素 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

举例arr={ 5，9 ，3，6，7} 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。 排序后 那么，会不会有数字对应在同一个位置的时候呢？

2.哈希冲突

2.1概念

结合上面这张图，假设数组arr={5，9，3，2，7}，那么当7遇到2的时候，该怎么做？ 这就是哈希冲突！ 即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。 我们把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2.2如何避免冲突

（1）哈希函数

引起哈希冲突的⼀个原因可能是：哈希函数设计不够合理。那么如何设计呢？ 哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间（就是函数计算完的地址数值必须在0~m-1之间）
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

常见哈希函数：

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

（2）负载因子调节

散列表的载荷因子定义为：α＝填入表中的元素个数/散列表的长度

从图中就可以看出，随着负载因子的增长，冲突率不断升高，所以当冲突率达到⼀个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。 Java中，当负载因子到达阈值0.75的时候，就会扩容散列表了

3. 解决哈希冲突

解决哈希冲突两种常见方法是：闭散列和开散列

3.1 闭散列

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下⼀个” 空位置中去。可如何寻找下⼀个空位置呢？

线性探测 结合图片，当该放入44时，通过函数得到的位置已经放了值为4的元素，即发生哈希冲突。 那么现在就需要线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下⼀个空位置为止。

• 插⼊ ◦ 通过哈希函数获取待插入元素在哈希表中的位置 ◦ 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

小问：那么当我们采用闭散列处理哈希冲突时，能不能直接删除元素呢？ 答：不能！这会直接影响其他元素的搜索。 比如删除元素4，如果直接删除掉，那么在查找44时，该位置显示为空，会直接判定没有44这个元素。因此线性探测采用标记的伪删除法来删除⼀个元素。

二次探测 线性探测的缺陷是产生冲突的数据堆积在一块(因为找空位置的方式就是挨着往后逐个去找) 而二次探测为了避免该问题，找下一个空位置的方法为：H1 = ( H0 + i^2 ) % m, 或者： ( key – i^2 ) % m，其中：i是产生冲突的次数， m是表的大小。举例：（依旧44）

3.2 开散列（重要）

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每⼀个子集合称为⼀个桶，各个桶中的元素通过⼀个单链表链接起来，各链表的头结点存储在哈希表中。

4. 性能分析

虽然哈希表总是和“冲突”这两字放在一起，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是⼀个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是O(1)

总结

以上就是今天要讲的内容啦~ 除了对Map和Set的讲解，还重点说了哈希表以及哈希冲突解决方法等等。 那就祝大家好梦啦，我们下期间~

彩蛋公布：直接将a与parent.key比较，大了放右边，小了方左边~