数据结构--Map和Set
目录
- 一.二叉搜索树
- 1.1 概念
- 1.2 二叉搜索树的简单实现
- 二.Map
- 2.1 概念
- 2.2 Map常用方法
- 2.3 Map使用注意点
- 2.4 TreeMap和HashMap的区别
- 2.5 HashMap底层知识点
- 三.Set
- 3.1 概念
- 3.2 Set常用方法
- 3.3 Set使用注意点
- 3.4 TreeSet与HashSet的区别
- 四.哈希表
- 4.1 概念
- 4.2 哈希冲突与避免
- 4.3 冲突解决
- 4.3.1 闭散列
- 4.3.2 开散列(哈希桶)
- 4.3.3 哈希桶的简单实现
一.二叉搜索树
1.1 概念
二叉搜索树,又称二叉排序树
,其是一棵空树或者具有以下性质的二叉树:
- 如果树的左子树不为空,则
左子树
上的所有结点的值都小于
根节点的值 - 如果树的右子树不为空,则
右子树
上的所有结点的值都大于
根节点的值 - 树的左右子树都分别为一棵二叉搜索树
1.2 二叉搜索树的简单实现
public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root;public boolean search(int val) { //查找值为val的结点TreeNode cur = root;while (cur != null) {if (cur.val < val) { //当前结点的值小于valcur = cur.right; //在其右子树查找} else if (cur.val > val) { //当前结点的值大于valcur = cur.left; //在其左子树寻找} else { //当前结点的值等于val,查找成功return true;}}return false;}public void insert(int val) { // 插入值为val的结点// 1.按照二叉搜索树的性质,查找到要插入的结点// 2.插入新结点if (root == null) {root = new TreeNode(val);return;}TreeNode parent = null;TreeNode cur = root;while (cur != null) {if (cur.val < val) {parent = cur;cur = cur.right;} else if (cur.val > val) {parent = cur;cur = cur.left;} else {return;}}TreeNode newNode = new TreeNode(val);if (parent.val > val) {parent.left = newNode;} else {parent.right = newNode;}}public void remove(int val) { //删除值为val的结点TreeNode parent = null;TreeNode cur = root;while (cur != null) {if (cur.val < val) {parent = cur;cur = cur.right;} else if (cur.val > val) {parent = cur;cur = cur.left;} else {// parent:待删除节点的父结点// cur:待删除结点removeNode(parent, cur);}}}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.left == null) { //cur.left为空的情况if (cur == root) { //cur是rootroot = cur.right;} else if (cur == parent.left) { //cur不是root,cur是parent的左子结点parent.left = cur.right;} else { //cur不是root,cur是parent的右子结点parent.right = cur.right;}} else if (cur.right == null) { //cur.right为空的情况(与cur.left为空的情况相同)if (cur == root) {root = cur.left;} else if (cur == parent.left) {parent.left = cur.left;} else {parent.right = cur.left;}} else { //cur.left与cur.right都不为空的情况//使用替换法删除,在cur结点的右子树中寻找值最小的结点来替换cur的值TreeNode t = cur.right; //值最小的结点TreeNode tp = cur; //值最小结点的父结点while (t.left != null) {tp = t;t = t.left;}cur.val = t.val;if (tp.left == t) { //删除结点ttp.left = t.right;} else {tp.right = t.right;}}}
}
二.Map
2.1 概念
Map和Set是一种专门用来进行搜索的数据结构,一般把搜索的数据称为关键字(Key),与关键字对应的称为值(Value)。Map是一个接口类,使用了Key-Value模型,类中存储的是<Key,Value>键值对
,并且Key是唯一的,不能重复。Map内部使用了Map.Entry<K,V>
的内部类来存放<Key,Value>键值对的映射关系
2.2 Map常用方法
方法 | 解释 |
---|---|
V get(Object key) | 返回key对应的value |
V getOrDefault(Object key,V defaultValue) | 返回key对应的value,key不存在,则返回defaultValue (默认值) |
V put(K key,V value) | 设置key对应的value |
V remove(Object key) | 删除key对应的映射关系 |
Set<K> keySet() | 返回所有key的不重复集合 |
Collection<V> values() | 返回所有value的可重复集合 |
Set<Map.Entry<K,V>> entrySet() | 返回所有的key-value映射关系 |
boolean containsKey(Object key) | 判断是否包含key |
boolean containsValue(Object value) | 判断是否包含value |
2.3 Map使用注意点
- Map是一个
接口
,不能直接实例化对象,如果要实例化对象,只能实例化其实现类TreeMap
或者HashMap
- Map中存放键值对的
key
是唯一
的,value
是可以重复
的 - 在TreeMap中插入键值对时,key不能为空,否则会抛出NullPointerException(空指针)异常,value可以为空;HashMap的key和value都可以为空
- Map中的key可以全部分离出来,存储到Set中进行访问
- Map中的value也可以全部分离出来,存储到Collection的任意一个子集合中
- Map中键值对的key不能直接修改,value可以修改,如果要修改key,只能将key删除掉再重新插入
2.4 TreeMap和HashMap的区别
Map | TreeMap | HashMap |
---|---|---|
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 | O(log2N) | O(1) |
是否有序 | 关于key有序 | 无序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
比较与覆写 | key必须能够比较,否则会抛异常 | 自定义类型需要覆写equals和hashCode方法 |
应用场景 | 需要key有序场景下 | 不关心key是否有序,有更高的时间性能需求 |
2.5 HashMap底层知识点
- HashMap的
最大容量
为230 - 当指定HashMap初始容量capacity时,生成的HashMap的容量为
最接近
capacity的二次幂
的值(例如指定容量为20,实际容量为32;指定容量为1000,实际容量为1024) - 未指定HashMap初始容量时,生成的HashMap
默认容量
为16
- HashMap扩容时为
2倍扩容
- HashMap的put方法使用的是
尾插法
- 如果HashMap中存储数组长度>=
64
,且各个桶中的单链表的长度>=8
,HashMap就会树化(单链表转变成红黑树
)
三.Set
3.1 概念
Set也是一个接口类,与Map不同,Set使用的是纯Key模型,类中只存储Key
3.2 Set常用方法
方法 | 解释 |
---|---|
boolean add(E e) | 添加元素,但是重复元素不会添加 |
void clear() | 清空集合 |
boolean contains(Object o) | 判断o是否在集合中 |
Iterator<E> iterator() | 返回迭代器 |
boolean remove(Object o) | 删除集合中的o |
int size() | 返回set中元素的个数 |
boolean isEmpty() | 检测set是否为空,空返回true,否则返回false |
Object toArray() | 将set中的元素转换为数组返回 |
boolean containsAll(Collection<?> c) | 集合c中的元素是否在set中全部存在 |
boolean addAll(Collection<? extends E> c) | 将集合c中的元素添加到set中,可达到去重的效果 |
3.3 Set使用注意点
- Set是继承自Collection的一个接口类
- Set中只存储了key,并且要求key
唯一
- 实现Set接口的常用类有
TreeSet
和HashSet
,还有LinkedHashSet(在HashSet的基础上维护了一个双向链表来记录元素的插入次序) - TreeSet
底层
使用Map
实现,使用key与Object默认对象作为键值对插入到Map中 - 与Map类似,Set中的key也不能直接修改,如果修改key,要删除并重新插入
- TreeSet不能插入null的key,HashSet可以
3.4 TreeSet与HashSet的区别
Set | TreeSet | HashSet |
---|---|---|
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 | O(log2N) | O(1) |
是否有序 | 关于key有序 | 不一定有序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 按照红黑树的特性来进行插入删除 | 计算key哈希地址再进行插入和删除 |
比较与覆写 | key必须能够比较,否则会抛出异常 | 自定义类型需要覆写equals和hashCode方法 |
应用场景 | 需要key有序场景下 | 不关心key是否有序,有更高的时间性能需求 |
四.哈希表
4.1 概念
哈希表,又称散列表
,是一种数据结构,其通过哈希函数
(散列函数)在元素的存储位置与关键码之间建立一一映射的关系,从而实现快速的插入、搜索和删除操作
例如数据集合{1,5,9},哈希函数设置为hash(key)=key%capacity;capacity为存储元素底层空间总大小
4.2 哈希冲突与避免
哈希冲突
:对于两个不同的关键字,如果通过哈希函数计算出了相同的哈希地址,这种现象称为哈希冲突
由于哈希表底层数组容量往往小于实际存储的关键字数量,这就导致冲突的发生是必然的,但是我们可以通过一些方法尽量降低冲突率。冲突避免
的方法有:
哈希函数设计
:引起哈希冲突的原理可能是哈希函数的设计不够合理,常用哈希函数有直接定制法,除留余数法,平方取中法,折叠法,随机数法,数学分析法等负载因子调节
:负载因子α=填入表中的元素个数/哈希表的长度
,α越大表明填入表中的元素越多,产生冲突的可能性就越大,反之则α越小,则填入表中元素越少,产生冲突的可能性越小。想要降低冲突率,就要降低负载因子
,由于哈希表中元素个数是不可变的,我们可以通过调整哈希表中数组的大小
来实现哈希冲突避免
4.3 冲突解决
解决哈希冲突的两种常见方法分别为闭散列
和开散列
4.3.1 闭散列
闭散列,也称开放定址法,当发生哈希冲突时,如果哈希表没有被装满,说明在哈希表中还有空位置,这时可以把key存放到冲突位置中的下一个空位置
去,下个空位置的具体寻找方法如下:
9. 线性探测:从发生冲突的位置开始,依次向后探测
,直到寻找到下一个空位置为止
10. 二次探测:线性探测会导致产生冲突的数据堆积在一起,二次探测为了避免这个问题,调整寻找下一个空位置的方法为(hash(key)+i^2^)%capacity
(其中i=1,2,3,…)
4.3.2 开散列(哈希桶)
开散列,又称链地址法,对关键码集合用哈希函数计算哈希地址,具有相同地址
的关键码归属于同一个子集合
,每一个子集合称为一个桶
,各个桶中的元素通过一条单链表(长度突破大于一定阈值后,转变为红黑树)连接起来,每条链表的头结点存储在哈希表中。在Java中,就使用了哈希桶这种方式来解决冲突
4.3.3 哈希桶的简单实现
public class HashBucket<K, V> {static class Node<K, V> {K key;V val;Node<K, V> next;public Node(K key, V val) {this.key = key;this.val = val;}}public Node<K, V>[] array = (Node<K, V>[]) new Node[10];public int usedSize;public static final double LOAD_FACTOR = 0.75; //负载因子public void put(K key, V val) {Node<K, V> node = new Node<>(key, val);int hash = key.hashCode();int index = hash % array.length;Node<K, V> cur = array[index];while (cur != null) {if (cur.key.equals(key)) {cur.val = val;return;}cur = cur.next;}node.next = array[index];array[index] = node;usedSize++;if (doLoadFactor() > LOAD_FACTOR) {reSize();}}public void reSize() {Node<K, V>[] newArray = new Node[array.length * 2];for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur != null) {int hash = cur.key.hashCode();int index = hash % newArray.length;Node curNext = cur.next;cur.next = newArray[index];newArray[index] = cur;cur = curNext;}}array = newArray;}public double doLoadFactor() {return usedSize * 1.0 / array.length;}public V get(K key) {int hash = key.hashCode();int index = hash % array.length;Node<K, V> cur = array[index];while (cur != null) {if (cur.key.equals(key)) {return cur.val;}cur = cur.next;}return null;}
}
相关文章:

数据结构--Map和Set
目录 一.二叉搜索树1.1 概念1.2 二叉搜索树的简单实现 二.Map2.1 概念2.2 Map常用方法2.3 Map使用注意点2.4 TreeMap和HashMap的区别2.5 HashMap底层知识点 三.Set3.1 概念3.2 Set常用方法3.3 Set使用注意点3.4 TreeSet与HashSet的区别 四.哈希表4.1 概念4.2 哈希冲突与避免4.3…...

计算机操作系统——进程控制(Linux)
进程控制 进程创建fork()函数fork() 的基本功能fork() 的基本语法fork() 的工作原理fork() 的典型使用示例fork() 的常见问题fork() 和 exec() 结合使用总结 进程终止与$进程终止的本质进程终止的情况正常退出(Exit)由于信号终止非…...

【前端】ES6基础
1.开发工具 vscode地址 :https://code.visualstudio.com/download, 下载对应系统的版本windows一般都是64位的 安装可以自选目录,也可以使用默认目录 插件: 输入 Chinese,中文插件 安装: open in browser,直接右键文件…...
【排序算法 python实现】
排序算法 python实现 / 默写 # 汉诺塔 import copy import randomdef hanuo(n, a, b, c):if n 1:print(f{a} --> {c})returnhanuo(n - 1, a, c, b)print(f{a} --> {c})hanuo(n - 1, b, a, c)hanuo(3, A, B, C)# 冒泡排序 def bubble_sort(arr):n len(arr)for i in ran…...

Java图书管理系统(简易保姆级)
前面学习了这么多知识,为了巩固之前的知识,我们就要写一个图书管理系统来帮助大家复习,让大家的知识融会贯通~~~ 话不多说,直接开始今天的内容~ 首先呢,我们要有一个大体的思路: 实现效果思路有两种情况&a…...
嵌入式硬件设计:从概念到实现的全流程
嵌入式硬件设计是现代电子技术中一个至关重要的领域,涉及从硬件架构设计到硬件调试的各个方面。它为我们日常生活中的各类智能设备、家电、工业控制系统等提供了强大的支持。本文将介绍嵌入式硬件设计的基本流程、关键技术、常用工具以及常见的挑战和解决方案&#…...
第 4 章 Java 并发包中原子操作类原理剖析
原子变量操作类 AtomicLong 是原子性递增或者递减类,其内部使用 Unsafe 来实现,AtomicLong类也是在 rt.jar 包下面的,AtomicLong 类就是通过 BootStarp 类加载器进行加载的。这里的原子操作类都使用 CAS 非阻塞算法 private static final lon…...

从 0 到 1 掌握部署第一个 Web 应用到 Kubernetes 中
文章目录 前言构建一个 hello world web 应用项目结构项目核心文件启动项目 检查项目是否构建成功 容器化我们的应用编写 Dockerfile构建 docker 镜像推送 docker 镜像仓库 使用 labs.play-with-k8s.com 构建 Kubernetes 集群并部署应用构建 Kubernetes 集群环境编写部署文件 总…...

政安晨【零基础玩转各类开源AI项目】探索Cursor-AI Coder的应用实例
目录 Cusor的主要特点 Cusor实操 政安晨的个人主页:政安晨 欢迎 👍点赞✍评论⭐收藏 希望政安晨的博客能够对您有所裨益,如有不足之处,欢迎在评论区提出指正! Cursor 是 Visual Studio Code 的一个分支。这使我们能够…...

CentOS 7 安装部署 KVM
1.关闭虚拟机 打开相关选项 打开虚拟机centos7 连接xshell 测试网络,现在就是没问题的,因为我们要使用网络源 安装 GNOME 桌面环境 安装KVM 模块 安装KVM 调试工具 构建虚拟机的命令行工具 qemu 组件,创建磁盘、启动虚拟机等 输入这条命令,…...

ArcGIS 10.2软件安装包下载及安装教程!
今日资源:ArcGIS 适用系统:WINDOWS 软件介绍:ArcGIS是一款专业的电子地图信息编辑和开发软件,提供一种快速并且使用简单的方式浏览地理信息,无论是2D还是3D的信息。软件内置多种编辑工具,可以轻松的完成地…...

一个专为云原生环境设计的高性能分布式文件系统
大家好,今天给大家分享一款开源创新的分布式 POSIX 文件系统JuiceFS,旨在解决海量云存储与各类应用平台(如大数据、机器学习、人工智能等)之间高效对接的问题。 项目介绍 JuiceFS 是一款面向云原生设计的高性能分布式文件系统&am…...

基于深度学习CNN算法的花卉分类识别系统01--带数据集-pyqt5UI界面-全套源码
文章目录 基于深度学习算法的花卉分类识别系统一、项目摘要二、项目运行效果三、项目文件介绍四、项目环境配置1、项目环境库2、环境配置视频教程 五、项目系统架构六、项目构建流程1、数据集2、算法网络Mobilenet3、网络模型训练4、训练好的模型预测5、UI界面设计-pyqt56、项目…...
3174、清除数字
3174、[简单] 清除数字 1、题目描述 给你一个字符串 s 。你的任务是重复以下操作删除 所有 数字字符: 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。 请你返回删除所有数字字符以后剩下的字符串。 2、解题思路 遍历字符串: 我们需要逐个遍…...

C++ 优先算法 —— 无重复字符的最长子串(滑动窗口)
目录 题目: 无重复字符的最长子串 1. 题目解析 2. 算法原理 Ⅰ. 暴力枚举 Ⅱ. 滑动窗口(同向双指针) 3. 代码实现 Ⅰ. 暴力枚举 Ⅱ. 滑动窗口 题目: 无重复字符的最长子串 1. 题目解析 题目截图: 此题所说的…...

ADS学习笔记 6. 射频发射机设计
基于ADS2023 update2 更多ADS学习笔记:ADS学习笔记 1. 功率放大器设计ADS学习笔记 2. 低噪声放大器设计ADS学习笔记 3. 功分器设计ADS学习笔记 4. 微带分支定向耦合器设计ADS学习笔记 5. 微带天线设计 -1、射频发射机性能指标 在射频电路和系统中,发送…...

上海乐鑫科技一级代理商飞睿科技,ESP32-C61高性价比WiFi6芯片高性能、大容量
在当今快速发展的物联网市场中,无线连接技术的不断进步对智能设备的性能和能效提出了更高要求。为了满足这一需求,乐鑫科技推出了ESP32-C61——一款高性价比的Wi-Fi 6芯片,旨在为用户设备提供更出色的物联网性能,并满足智能设备连…...

QT QRadioButton控件 全面详解
本系列文章全面的介绍了QT中的57种控件的使用方法以及示例,包括 Button(PushButton、toolButton、radioButton、checkBox、commandLinkButton、buttonBox)、Layouts(verticalLayout、horizontalLayout、gridLayout、formLayout)、Spacers(verticalSpacer、horizontalSpacer)、…...

51单片机从入门到精通:理论与实践指南(一)
单片机在智能控制领域的应用已非常普遍,发展也很迅猛,学习和使用单片机的人员越来越多。虽然新型微控制器在不断推出,但51单片机价格低廉、易学易用、性能成熟,在家电和工业控制中有一定的应用,而且学好了51单片机&…...

零基础3分钟快速掌握 ——Linux【终端操作】及【常用指令】Ubuntu
1.为啥使用Linux做嵌入式开发 能广泛支持硬件 内核比较高效稳定 原码开放、软件丰富 能够完善网络通信与文件管理机制 优秀的开发工具 2.什么是Ubuntu 是一个以桌面应用为主的Linux的操作系统, 内核是Linux操作系统, 具有Ubuntu特色的可视…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...

【iOS】 Block再学习
iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

表单设计器拖拽对象时添加属性
背景:因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...