数据结构--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特色的可视…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...

群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...