当前位置： 首页 > news >正文

【MapSet】哈希表

news 2025/3/13 5:36:53

目录

1. 搜索树

1.1 概念

1.2 操作-查找

1.3 操作-插入

1.4 操作-删除（难点）

1.5 性能分析

1.6 和java类集的关系

2. 搜索

2.1 概念及场景

2.2 模型

3. Map的使用

3.1 关于Map的说明

3.2 关于Map.Entry的说明

3.3 Map的常用方法说明

3.4 TreeMap的使用案例

4. Set的说明

4.1 关于Set的说明

4.2 TreeSet的使用案例

5. 哈希表

5.1 概念

5.2 冲突-概念

5.3 冲突-避免

5.4 冲突-避免-哈希函数设计

5.5 冲突-避免-负载因子调节（重点）

5.6 冲突-解决

5.7 冲突-解决-闭散列

5.8 冲突-解决-开散列/哈希桶（重点）

5.9 冲突严重时的解决方法

5.10 性能分析

5.11 和java类集的关系

6. OJ练习

1. 搜索树

1.1 概念

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

  1. 若它的左子树不为空，则左子树上所有结点的值都小于根节点的值
  2. 若它的右子树不为空，则右子树上所有结点的值都大于根节点的值
  3. 它的左右子树也分别为二叉搜索树
1.2 操作-查找
    // 搜索（查找）数据public TreeNode search(int val) {TreeNode cur = root;if (cur == null) return null;if (val < cur.val) cur = cur.left;if (val > cur.val) cur = cur.right;return cur;}
1.3 操作-插入
    // 插入数据public void insert(int val) {if (root == null) {root = new TreeNode(val);return;}TreeNode parent = null;TreeNode cur = root;TreeNode node = new TreeNode(val);// 要插入的节点while (cur != null) {if (val < cur.val) {parent = cur;cur = cur.left;} else if (val > cur.val) {parent = cur;cur = cur.right;} else {return;// 插入结束}}if (parent.val > val) parent.left = node;else parent.right = node;}
1.4 操作-删除（难点）
  • cur.left==null
    1. cur是root,则root=root.right（如图1）
    2. cur不是root,cur是parent.left,则parent.left=cur.right（如图2）
    3. cur不是root,cur是parent.right,则parent.right=cur.right（如图3）

  • cur.right==null
    1. cur是root,则root=root.left（如图1）
    2. cur不是root,cur是parent.left,则parent.left=cur.left（如图2）
    3. cur不是root,cur是parent.right,则parent.right=cur.left（如图3）

 

    // 删除数据public void remove(int key) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (cur.val > key) {parent = cur;cur = cur.left;} else if (cur.val < key) {parent = cur;cur = cur.right;} else {removeNode(parent, cur);// 删除此节点}}}public void removeNode(TreeNode parent, TreeNode cur) {if (cur.left == null) {// 左子树为空if (cur == root) root = root.right;else if (parent.left == cur) parent.left = cur.right;else parent.right = cur.right;} else if (cur.right == null) {// 右子树为空if (cur == root) root = root.left;else if (parent.left == cur) parent.left = cur.left;else parent.right = cur.left;} else {// 左右都不为空TreeNode target = cur.right;TreeNode targetParent = cur;while (target.left != null) {targetParent = target;target = target.left;}cur.val = target.val;if (targetParent.left == target) {targetParent.left = target.right;} else {targetParent.right = target.right;}}}
1.5 性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对于n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，比较次数越多。

最优情况下：二叉搜索树为完全二叉树，其平均比较次数为：logN

最差情况下：二叉搜索树为单支树，其平均比较次数为：N/2

1.6 和java类集的关系

TreeMap和TreeSet即java中利用搜索树实现的Map和Set;实际上用的是红黑树，红黑树是一颗近似平衡的二叉搜索树，即在二叉搜索树的基础之上+颜色以及红黑树性质验证。

2. 搜索

2.1 概念及场景

Map和Set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。Map和Set是一种适合动态查找的集合容器。

2.2 模型

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

  1. 纯key模型，比如：
    1. 有一个英文词典，快速查找一个单词是否在词典中
    2. 快速查找某个名字是否在通讯录中
  2. key-value模型，比如：
    1. 统计文件中每个单词出现的次数，统计结果是每个单词都有与之对应的次数：<单词，单词出现的次数>
    2. 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

Map中存储的是key-value的键值对，Set中只存储了key

3. Map的使用

3.1 关于Map的说明

Map是一个接口类，该类没有继承Collection，该类中存储的是<k,v>的键值对，并且k一定是唯一且不重复的。

3.2 关于Map.Entry的说明

Map.Entry<k,v>是Map内部实现的用来存放<key,value>键值对映射关系的内部类，该内部类中主要提供了<key,value>的获取，value的设置以及key的比较方式。

注意：Map.Entry<k,v>并没有提供设置key的方法

3.3 Map的常用方法说明

注意：

  1. Map是一个接口，不能直接实例化对象，如果实例化对象，只能实例化其实现类TreeMap或者HashMap
  2. Map中存放键值对的key唯一，value可以重复
  3. 在TreeMap中插入键值对时，key不能为空，否则就会抛出NullPointerException异常，value可以为空，但是HashMap的key和value都可以为空
  4. Map中的key可以全部分离出来，存储到set中进行访问（因为key不能重复）
  5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中（value可能重复）
  6. Map中键值对的key不能直接修改，value可以修改，如果要修改key，只能先将key删除掉，然后进行重新插入
3.4 TreeMap的使用案例
    public static void main(String[] args) {TreeMap<String, Integer> treeMap = new TreeMap<>();treeMap.put("abc", 3);treeMap.put("hello", 2);treeMap.put("world!", 1);Set<Map.Entry<String, Integer>> entrySet = treeMap.entrySet();for (Map.Entry<String, Integer> entry : entrySet) {System.out.println("key:" + entry.getKey() + " value:" + entry.getValue());}}

4. Set的说明

4.1 关于Set的说明

  1. Set是继承自Collection的一个接口类

  2. Set中只存储了key，并且要求key一定要唯一

  3. TreeSet的底层是Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中

  4. Set最大的功能就是对集合中的元素进行去重

  5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序

  6. Set中的key不能修改，如果要修改，先将原来的删除掉，然后重新插入

  7. TreeSet中不能插入null的key，HashSet可以

4.2 TreeSet的使用案例
    public static void main(String[] args) {TreeSet<String> set = new TreeSet<>();set.add("abcd");set.add("abcd");set.add("hello");Iterator<String> it = set.iterator();while (it.hasNext()) {System.out.print(it.next() + " ");//abcd hello （自动去重）}System.out.println();}

5. 哈希表

5.1 概念

哈希（散列）方法：不经过比较，直接一次获取要搜到的元素。通过某种函数使元素的存储位置与它的关键码之间建立一一映射的关系。

哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（或称散列表）

哈希函数设置为：hash(key)=key%capacity;capacity为存储元素底层空间的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。

5.2 冲突-概念

不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。

把具有不同关键码具有相同哈希地址的数据元素称为“同义词”


5.3 冲突-避免

由于哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，因此冲突的发生是必然的，我们能做的就是降低冲突率。

5.4 冲突-避免-哈希函数设计

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

5.5 冲突-避免-负载因子调节（重点）

负载因子越大冲突率越高

散列表的负载因子=填入表的元素个数/散列表长度

当逼近负载因子或者等于负载因子，此时要赶快进行扩容

5.6 冲突-解决

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

5.7 冲突-解决-闭散列

也叫“开放定址法”，当发生哈希冲突时，如果哈希表未满，说明表中还有空位置，那么可以将key存放到冲突位置的下一个空位置（线性探测——冲突元素聚集到了一起、二次探测——避免了上个方法的问题）

最大的缺陷：空间利用率低，也是哈希的缺陷

5.8 冲突-解决-开散列/哈希桶（重点）

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

用空间换时间

5.9 冲突严重时的解决方法

哈希桶可以看作将大集合的搜索问题转化为小集合的搜索问题，如果冲突严重，就意味着小集合的搜索性能也不佳，此时可以将这个小集合搜索问题继续进行转化，例如：

  1. 每个桶背后是另一个哈希表
  2. 每个桶背后是一颗搜索树
5.10 性能分析

哈希表的冲突个数是可控的，即每个桶的链表长度是一个常数，所以，通常意义下，哈希表的插入/删除/查找时间复杂度是O(1)

5.11 和java类集的关系
  1. HashMap和HashSet即java中利用哈希表实现的Map和Set
  2. java中使用的是哈希桶方式解决冲突的
  3. java会在冲突链长度大于一定阈值后，将链表转变为搜索树（红黑树）
  4. java中计算哈希值实际上是调用的类的hashCode方法，进行key的相等性比较是调用key的equals方法。所以如果要用自定义类作为HashMap的key或者HashSet的值，必须复写hashCode和equals方法，而且要做到equals相等的对象，hashCode一定是一致的。

6. OJ练习

136. 只出现一次的数字 - 力扣（LeetCode）

// 强行使用集合
class Solution {public int singleNumber(int[] nums) {HashSet<Integer> set = new HashSet<>();// 创建一个哈希表for (int i = 0; i < nums.length; i++) {// 遍历numsif (set.contains(nums[i])) {set.remove(nums[i]);} else {set.add(nums[i]);}}for (int i = 0; i < nums.length; i++) {// 遍历numsif (set.contains(nums[i])) {// 剩下的那个元素即为所求return nums[i];}}return -1;}
}

138. 随机链表的复制 - 力扣（LeetCode）

注：百度考过-中等难度（使用HashMap）

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {HashMap<Node, Node> map = new HashMap<>();//Node cur = head;// 用来遍历链表while (cur != null) {Node node = new Node(cur.val);map.put(cur, node);// 将新节点，老节点构成一一对应关系cur = cur.next;}cur = head;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}
}

771. 宝石与石头 - 力扣（LeetCode）

class Solution {public int numJewelsInStones(String jewels, String stones) {HashSet<Character> count = new HashSet<>();for (int i = 0; i < jewels.length(); i++) {count.add(jewels.charAt(i));}int num = 0;for (int i = 0; i < stones.length(); i++) {if (count.contains(stones.charAt(i))) {num++;}}return num;}
}

1033 旧键盘打字 - PAT (Basic Level) Practice （中文）

692. 前K个高频单词 - 力扣（LeetCode）

（小根堆-50行代码）


http://www.mrgr.cn/news/94141.html

相关文章：

  • vue3，Element Plus中el-select默认显示0
  • 前端高阶面试题·每日一题
  • 大模型在甲状腺肿瘤预测及治疗方案制定中的应用研究
  • Java并发编程面试题：基础（11题）
  • XSS笔记
  • 大模型架构记录4-文档切分 (chunks构建)
  • Fedora41安装MySQL8.4.4
  • 笔记六：链表介绍与模拟实现
  • 【leetcode hot 100 24】两两交换链表中的节点
  • Visual C++ 6.0（完整绿色版）安装设置
  • pytorch retain_grad vs requires_grad
  • 项目实操分享：一个基于 Flask 的音乐生成系统，能够根据用户指定的参数自动生成 MIDI 音乐并转换为音频文件
  • git本地仓库链接远程仓库
  • go 标准库包学习笔记
  • Rust 之一 基本环境搭建、各组件工具的文档、源码、配置
  • Burpsuite使用笔记
  • 【大模型统一集成项目】让 AI 聊天更丝滑：SSE 实现流式对话！
  • 【大模型统一集成项目】让 AI 聊天更丝滑：WebSocket 实现流式对话！
  • Android实现Socket通信
  • 利用selenium调用豆包进行自动化问答以及信息提取