【数据结构】Map与Set
前言
前两篇文章我们研究了二叉搜索树与哈希表的结构与特点,他们二者是Map与Set这两个接口实现的底层结构,他们利用了搜索树与哈希表查找效率高这一特点,是一种专门用来进行搜索操作的容器或数据结构。本篇文章就让我们一起来梳理这两个接口的特性与用法吧

在介绍这两个接口前先说明一下Key-value模型吧:
一、Map

Map 是一个接口类,该类没有继承自 Collection ,该类中存储的是 <K,V> 结构的键值对,并且 K 一定是唯一的,不 能重复。
注意:1. Map 是一个接口,不能直接实例化对象,如果 要实例化对象只能实例化其实现类 TreeMap 或者 HashMap2. 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删除掉,然后再来进行重新插入。
public class HashBuck2<K,V> {static class Node<K,V> {public K key;public V val;public 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 Node<K,V>[] array = new Node<K,V>[10];public int usedSize;public double loadFactor = 0.75;public void put(K key,V val) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];//1. 遍历当前链表 是否存在当前值while (cur != null) {if(cur.key.equals(key)) {cur.val = val;return;}cur = cur.next;}//2. 说明 没有当前值,此时进行 头插Node<K,V> node = new Node<K,V>(key,val);node.next = array[index];array[index] = node;usedSize++;}public V get(K key) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];//1. 遍历当前链表 是否存在当前值while (cur != null) {if(cur.key.equals(key)) {return cur.val;}cur = cur.next;}return null;}
} TreeMap使用示例:
import java.util.TreeMap;
import java.util.Map;
public static void TestMap(){Map<String, String> m = new TreeMap<>();
// put(key, value):插入key-value的键值对
// 如果key不存在,会将key-value的键值对插入到map中,返回nullm.put("林冲", "豹子头");m.put("鲁智深", "花和尚");m.put("武松", "行者");m.put("宋江", "及时雨");String str = m.put("李逵", "黑旋风");System.out.println(m.size());System.out.println(m);
// put(key,value): 注意key不能为空,但是value可以为空
// key如果为空,会抛出空指针异常
//m.put(null, "花名");str = m.put("无名", null);System.out.println(m.size());
// put(key, value):
// 如果key存在,会使用value替换原来key所对应的value,返回旧valuestr = m.put("李逵", "铁牛");
// get(key): 返回key所对应的value
// 如果key存在,返回key所对应的value
// 如果key不存在,返回nullSystem.out.println(m.get("鲁智深"));System.out.println(m.get("史进"));
//GetOrDefault(): 如果key存在,返回与key所对应的value,如果key不存在,返回一个默认值System.out.println(m.getOrDefault("李逵", "铁牛"));System.out.println(m.getOrDefault("史进", "九纹龙"));System.out.println(m.size());
//containKey(key):检测key是否包含在Map中,时间复杂度:O(logN)
// 按照红黑树的性质来进行查找
// 找到返回true,否则返回falseSystem.out.println(m.containsKey("林冲"));System.out.println(m.containsKey("史进"));
// containValue(value): 检测value是否包含在Map中,时间复杂度: O(N)
// 找到返回true,否则返回falseSystem.out.println(m.containsValue("豹子头"));System.out.println(m.containsValue("九纹龙"));
// 打印所有的key
// keySet是将map中的key防止在Set中返回的for(String s : m.keySet()){System.out.print(s + " ");}System.out.println();
// 打印所有的value
// values()是将map中的value放在collect的一个集合中返回的for(String s : m.values()){System.out.print(s + " ");}System.out.println();
// 打印所有的键值对
// entrySet(): 将Map中的键值对放在Set中返回了for(Map.Entry<String, String> entry : m.entrySet()){System.out.println(entry.getKey() + "--->" + entry.getValue());}System.out.println();
}
二、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可以。
import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
public static void TestSet(){Set<String> s = new TreeSet<>();// add(key): 如果key不存在,则插入,返回ture// 如果key存在,返回falseboolean isIn = s.add("apple");s.add("orange");s.add("peach");s.add("banana");System.out.println(s.size());System.out.println(s);isIn = s.add("apple");// add(key): key如果是空,抛出空指针异常//s.add(null);// contains(key): 如果key存在,返回true,否则返回falseSystem.out.println(s.contains("apple"));System.out.println(s.contains("watermelen"));// remove(key): key存在,删除成功返回true// key不存在,删除失败返回false// key为空,抛出空指针异常s.remove("apple");System.out.println(s);s.remove("watermelen");System.out.println(s);Iterator<String> it = s.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();
} 总结
Map与Set这两个接口由于出色的查找效率,为之后的一些算法题中在优化时间上发挥着重要的作用,不过由于创建需要开辟大量空间,是典型的空间换时间,在实际应用中应该根据需要选用。还是哪句话,没有最好的数据结构,只有最适合的数据结构。
那么本篇文章就到此为止了,如果觉得这篇文章对你有帮助的话,可以点一下关注和点赞来支持作者哦。作者还是一个萌新,如果有什么讲的不对的地方欢迎在评论区指出,希望能够和你们一起进步✊
相关文章:
【数据结构】Map与Set
前言 前两篇文章我们研究了二叉搜索树与哈希表的结构与特点,他们二者是Map与Set这两个接口实现的底层结构,他们利用了搜索树与哈希表查找效率高这一特点,是一种专门用来进行搜索操作的容器或数据结构。本篇文章就让我们一起来梳理这两个接口的…...
Flamingo: a Visual Language Model for Few-Shot Learning
发表时间:NeurIPS 2022 论文链接:https://proceedings.neurips.cc/paper_files/paper/2022/file/960a172bc7fbf0177ccccbb411a7d800-Paper-Conference.pdf 作者单位:DeepMind Motivation:仅使用少量注释示例可以快速适应新任务…...
flume性能调优
作者:南墨 1.Source性能调优 1.1 Spooldir Source 使用Spooldir Source采集日志数据时,若每行日志数据<100bp,可以通过将多行合并传输来提升传输性能 建议合并时根据数据长度来确定多少行合并为一个单位进行传输,合并后的长…...
mysql 字符串转数组
在 MySQL 中,可以使用内置的字符串函数 SUBSTRING_INDEX() 和 REPLACE() 来实现将字符串转换为数组。 首先,使用 REPLACE() 函数将字符串中的分隔符替换为空格,然后使用 SUBSTRING_INDEX() 函数将字符串按空格分割成多个子字符串。最后&…...
UE基础 —— 术语
目录 Project Blueprint Class Object Actor Casting Component Pawn Character Player Controller AI Controller Player State Game Mode Game State Brush Volume Level World Project 项目(Project)包含游戏的所有内容,…...
kubernets学习笔记——使用kubeadm构建kubernets集群及排错
使用kubeadm构建kubernets集群 一、准备工作1、repo源配置:阿里巴巴开源镜像源2、更新软件包并安装必要的系统工具3、同步时间4、禁用selinux5、禁用交换分区swap6、关闭防火墙 二、安装docker-ce、docker、cri-docker1、安装docker-ce2、开启内核转发,转…...
简述MYSQL聚簇索引、二级索引、索引下推
一丶聚簇索引 InnoDB的索引分为两种: 聚簇索引:一般创建表时的主键就会被mysql作为聚簇索引,如果没有主键则选择非空唯一索引作为聚簇索引,都没有则隐式创建一个索引作为聚簇索引;辅助索引:也就是非聚簇索…...
电脑开机后出现bootmgr is missing原因及解决方法
最近有网友问我为什么我电脑开机后出现bootmgr is missing,这个提示意思是:意思是启动管理器丢失,说明bootmgr损坏或者丢失,系统无法读取到这个必要的启动信息导致无法启动。原因有很多,比如我们采用的是uefi引导,而第…...
2024 年 7 月公链行业研报:市场波动中 Solana 表现抢眼,Layer 2 竞争白热化
作者:Stella L (stellafootprint.network) 数据来源:Footprint Analytics 公链 Research 页面 7 月份,加密货币市场表现活跃,波动幅度较大,这一现象映射了全球金融市场的整体趋势。现货以太坊 ETP 在美国的上市&…...
Python查缺補漏
一、 json.load(s)与json.dump(s)区别 json.loads()将str类型的数据转换为dict类型 json.dumps()将dict类型的数据转成str json.load()从json文件中读取数据 json.dump()将数据以json的数据类型写入文件中 二、json内部要使用双引号 data """{ "fruit&qu…...
c++的类和对象(中):默认成员函数与运算符重载(重难点!!)
前言 Hello, 小伙伴们,我们今天继续c的学习,我们上期有介绍到c的部分特性,以及一些区别于c语言的地方,今天我们将继续深入了解c的类和对象,探索c的奥秘。 好,废话不多说,开始我们今天的学习。…...
Android .kl按键布局文件
1.介绍 一个硬件按键的处理流程大致为:当用户按下或释放一个键时,键盘硬件会生成一个扫描码scan code,然后操作系统读取这个scan code,并将scan code扫描码映射到虚拟键码key code,最后操作系统根据映射的keycode生成…...
Java每日一练_模拟面试题6(JVM的GC过程)
一、JVM虚拟机组成 JVM五大内存区域:程序计数器,Java虚拟机栈,本地方法栈,java堆,方法区。 堆被划分为两个区域:年轻代(Young)、老年代(Tenured)。年轻代又被划分为三个区域:Eden、From Surviv…...
数据防泄密软件推荐|(6大数据防泄密软件推荐!)
很多朋友在后台私信,什么是数据防泄密软件,有哪些数据防泄密软件推荐。 今天小编将从定义出发,深入浅出地介绍这一技术的工作原理、应用场景以及实现方式。 一、什么是文档透明加密? 文档透明加密是一种在用户无感知的情况下对文…...
Codeforces 874 div3 A-G
A. Musical Puzzle 分析 每两个相邻的字母都要录制一段,开个set记录一下,然后输出set的大小 C代码: #include<iostream> #include<set> using namespace std; void solve(){int n;string s;cin>>n>>s;set<strin…...
暑期数据结构 空间复杂度
3.空间复杂度 空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟…...
【Android Studio】图标一键生成 Image Asset Studio(一键各机型适配图标生成工具-告别一个一个替换)
文章目录 方法一:原始替换方法二:Image Asset Studio 方法一:原始替换 https://blog.csdn.net/xzzteach/article/details/140821856 方法二:Image Asset Studio 自动替换所有机型图标...
C++ | Leetcode C++题解之第332题重新安排行程
题目: 题解: class Solution { public:unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;vector<string> stk;void dfs(const string& curr) {while (vec.count(curr) &am…...
使用Python实现简单的网页爬虫:抓取网站标题
使用Python实现简单的网页爬虫:抓取网站标题 在当今数据驱动的时代,网络爬虫(Web Crawler)成为了获取和分析网络数据的重要工具。无论是数据科学、市场分析还是学术研究,爬虫都能帮助我们从互联网上提取有价值的信息。本文将介绍如何使用Python实现一个简单的爬虫,抓取某…...
视觉SLAM ch3—三维空间的刚体运动
如果对于某些线性代数的知识不太牢固,可以看一下我的另一篇博客,写了一些基础知识并推荐了一些视频。 旋转矩阵 单元所需的线代基础知识https://blog.csdn.net/Johaden/article/details/141023668 一、旋转矩阵 1.点、向量、坐标系 在数学中&…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
