【数据结构】Map与Set

前言

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

58d60bbf89ce4be698240c1474f4da73.png

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

一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称之为Key-value的键值对,所以模型会有两种:
1. key 模型,比如:
有一个英文词典,快速查找一个单词是否在词典中快速查找某个名字在不在通讯录中
2. Key-Value 模型,比如:
统计文件中每个单词出现的次数,统计结果是每个单词都有与其对应的次数:<单词,单词出现的次数>梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号
Map 中存储的就是 key-value 的键值对, Set 中只存储了 Key

一、Map

3784d2b8c38f434db7f6ce60bc674457.png

Map 是一个接口类,该类没有继承自 Collection ,该类中存储的是 <K,V> 结构的键值对,并且 K 一定是唯一的,不 能重复
Map.Entry<K, V> 是 Map 内部实现的用来存放 <key, value> 键值对映射关系的内部类,该内部类中主要提供了<key, value>的获取,value的设置以及Key的比较方式。
方法解释
K getKey()
返回 entry 中的 key
V getValue()
返回 entry 中的 value
V setValue(V value)
将键值对中的value替换为指定value

 

注意:Map.Entry<K,V> 并没有提供设置 Key 的方法
Map 的常用方法说明
aad74e44e2cc4ccca5b53e182933d846.png
注意:
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删除掉,然后再来进行重新插入。
8446713306834a369d27a58cf936962a.png
HashMap的简单实现:
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

Set与Map主要的不同有两点:Set是继承自Collection的接口类,Set中只存储了Key。
常见方法说明
36806fd5bfea4a3682513e02124fbb43.png
注意:
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可以。
7c56d054196046e2b5c58f840606d75b.png
TreeSet使用示例:

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这两个接口由于出色的查找效率,为之后的一些算法题中在优化时间上发挥着重要的作用,不过由于创建需要开辟大量空间,是典型的空间换时间,在实际应用中应该根据需要选用。还是哪句话,没有最好的数据结构,只有最适合的数据结构。


那么本篇文章就到此为止了,如果觉得这篇文章对你有帮助的话,可以点一下关注和点赞来支持作者哦。作者还是一个萌新,如果有什么讲的不对的地方欢迎在评论区指出,希望能够和你们一起进步✊

08403404d82e4ca19e76b10b45ca5f28.png

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395301.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于Hadoop的国内手机销售大数据分析与可视化研究【百万数据集】

文章目录 有需要本项目的代码或文档以及全部资源&#xff0c;或者部署调试可以私信博主项目介绍 绪论研究背景研究目的研究意义 相关技术理论介绍Hadoop相关理论HIve数据仓库flume组件介绍sqoop组件介绍Pyecharts介绍 数据来源及处理数据介绍数据预处理 Hadoop集群搭建Hadoop全…

开源wiki知识库工具zyplayer-doc

zyplayer-doc是一款适合团队和个人私有化部署使用的在线知识库、笔记、WIKI文档管理工具。它不仅提供了知识库管理的基本功能&#xff0c;还包含了数据库管理、API接口管理等模块&#xff0c;能够满足用户多样化的需求。 体验地址&#xff1a;文档管理系统 仓库地址&#xff…

Together规则引擎 金融解决方案

目录 1.金融法规和期望正在发生变化,快速跟踪您的金融数字化变革&#xff01;2.抵押贷款功能集&#xff08;MFS&#xff09;3.MFS 示例模型4.MFS 知识特点5.MFS特定功能 1.金融法规和期望正在发生变化,快速跟踪您的金融数字化变革&#xff01; ogether规则引擎使金融机构能够简…

NAT、服务代理、内网穿透

文章目录 NAT技术NAT IP转换过程NATPNAT的优点NAT的缺点 代理服务器正向代理反向代理 内网穿透和内网打洞内网穿透内网穿透 NAT技术 NAT技术即网络地址转换技术。用于将私有IP地址转换为公共IP地址&#xff0c;以便在互联网或其他外部网络中通信。为了解决IPv4协议下IP地址不足…

[matlab] 鲸鱼优化算法优化KNN分类器的特征选择

目录 引言 智能优化算法概述 智能优化算法在KNN特征选择中的应用 应用步骤 UCI数据集 鲸鱼优化算法 一、算法背景与原理 二、算法组成与步骤 三、算法特点与优势 四、应用与挑战 代码实现 鲸鱼优化算法 主程序 打印结果 引言 智能优化算法在优化KNN&#xff08;…

最大耗散功率

注&#xff1a;本文内容来自ChatGPT 最大耗散功率&#xff08;Maximum Power Dissipation&#xff09;是指芯片或电子元件在指定的工作条件下&#xff0c;能够安全散发的最大热功率&#xff0c;通常以瓦特&#xff08;W&#xff09;为单位表示。这是一个关键的设计参数&#x…

什么是Stable Diffusion?如何安装Stable Diffusion?

前言 Stable Diffusion秋叶整合包&#xff0c;一键安装Stable Diffusion&#xff0c;门槛极低&#xff0c;完全免费&#xff0c;支持Nvidia全系列显卡。 来自B站up主秋葉aaaki近期推出的Stable Diffusion整合包v4.6版本&#xff0c;能够让零基础用户轻松在本地部署Stable Diff…

Scanner类、String类和StringBuffer类的相关使用

一、Scanner: 主要用于键盘录入的 构造方法&#xff1a; Scanner(InputStream source) 构造一个新的 Scanner &#xff0c;产生从指定输入流扫描的值。 1、next()和nextLine()区别&#xff1a; String line sc.next(); // 不会接收特殊字符&#xff0c;比如空格回…

Python中的 `continue` 语句:掌握循环控制的艺术

Python中的 continue 语句&#xff1a;掌握循环控制的艺术 下滑即可查看博客内容 &#x1f308; 欢迎莅临我的个人主页 &#x1f448;这里是我静心耕耘深度学习领域、真诚分享知识与智慧的小天地&#xff01;&#x1f387; &#x1f393; 博主简介&#xff1a;985高校的普通…

服务器数据恢复—Raid故障导致存储中数据库数据丢失的数据恢复案例

服务器存储数据恢复环境&故障情况&#xff1a; 一台光纤存储中有一组由16块硬盘组成的raid。 该存储出现故障导致数据丢失。RAID中2块盘掉线&#xff0c;还有1块盘smart状态为“警告”。 服务器存储数据恢复过程&#xff1a; 1、通过该存储自带的存储管理软件将当前存储的完…

企业常用的文件加密软件排行榜,10款顶级文件加密软件推荐

在数字化时代&#xff0c;企业数据的安全性和保密性显得尤为重要。为了确保敏感文件不被未授权访问或泄露&#xff0c;企业纷纷采用文件加密软件来加强数据保护。以下是2024年企业常用的10款顶级文件加密软件推荐&#xff0c;它们各具特色&#xff0c;能够满足不同企业的需求。…

【第十届泰迪杯数据挖掘挑战赛A题害虫识别】-农田害虫检测识别-高精度完整更新

农田害虫检测识别项目-高精度完整版 一、说明&#xff1a; 该版本为基于泰迪杯完整害虫数据重新制作数据集、优化增强数据集、重新进行模型训练&#xff0c;达到高精度、高召回率的最优模型代码。包含论文、最优模型文件以及相关文件、原始数据集、训练数据集XML版、增强扩充…

【数据结构】哈希应用-海量数据处理

目录 1、10亿个整数里面求最大的100个 2、求大文件交集 3、查找出现次数前210的ip地址 1、10亿个整数里面求最大的100个 经典的tok问题&#xff0c;可以使用堆来解决 2、求大文件交集 给两个文件&#xff0c;分别有100亿个query&#xff0c;我们只有1G内存&#xff0c;如…

如何用 CocosCreator 对接抖音小游戏的侧边栏复访

前言 最近小游戏的软著下来了&#xff0c;用 CocosCreator 做的游戏也完成了 1.0 版本。而当我打包成抖音小游戏进行提交时&#xff0c;还没到初审就给拒了&#xff0c;因为还有一个机审&#xff0c;机器检测到代码中没有接入 “侧边栏复访功能”。这个我还真不知道&#xff0…

不要问人工智能能为你做什么,而要问你能用人工智能实现什么?

​新前沿 欢迎来到雲闪世界。在过去的一年半里&#xff0c;我一直在向我认识的每个人讲述人工智能的潜力&#xff0c;尤其是大型语言模型 (LLM)。无论技术背景如何&#xff0c;现在是时候让每个人学习 LLM 的基础知识以及如何有效地使用它们了。 20 世纪 60 年代&#xff0c;我…

美国服务器稳定么?影响服务器稳定性的6个因素

美国服务器稳定么&#xff1f;美国服务器的稳定性是相当不错的&#xff0c;这主要得益于其先进的技术、成熟的基础设施以及严格的管理措施。美国拥有众多知名的服务器提供商&#xff0c;这些提供商通常会采用顶级的硬件设施&#xff0c;如英特尔、AMD等知名品牌的处理器&#x…

以树莓集团的视角:探索AI技术如何重塑数字媒体产业发展

在科技日新月异的今天&#xff0c;AI技术如同一股不可阻挡的潮流&#xff0c;正深刻改变着我们的世界&#xff0c;尤其是数字媒体产业发展。作为数字产业生态链的杰出建设者&#xff0c;树莓集团始终站在时代前沿&#xff0c;积极探索AI技术如何为数字媒体产业注入新活力。 在树…

NFTScan 正式上线 Gravity NFTScan 浏览器和 NFT API 数据服务

2024 年 8 月 9 号&#xff0c;NFTScan 团队正式对外发布了 Gravity NFTScan 浏览器&#xff0c;将为 Gravity 生态的 NFT 开发者和用户提供简洁高效的 NFT 数据搜索查询服务。NFTScan 作为全球领先的 NFT 数据基础设施服务商&#xff0c;Gravity 是继 Bitcoin、Ethereum、BNBC…

修改nacos实力权重或者对某实例下线报错

在Nacos控制台进行上述操作&#xff0c;错误信息 caused: errCode: 500, errMsg: do metadata operation failed ;caused: com.alibaba.nacos.consistency.exception.ConsistencyException: The Raft Group [naming_instance_metadata] did not find the Leader node;caused:…

IIS部署Linux环境下的cer证书步骤

1. 获取Linux环境的cer证书 Linux环境下的cer证书位于&#xff1a;root/.acme.sh 下&#xff0c;下载到Windows服务器。 2. 将cer证书转为pfx证书 IIS导入证书的时候只支持pfx格式证书&#xff0c;所以需要转换一下&#xff0c;确保Windows服务器上已安装openssl工具&#x…