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

哈希表的介绍

1.哈希表的介绍

在哈希表中插入、删除或查找一个元素都只需要O(1)的时间,因此经常被用来优化时间效率。

在Java中,哈希表有两个对应的类型,即HashSet和HashMap。

2.HashSet的应用

若每个元素都只有一个值,则用HashSet,如,HashSet在图搜索时经常用来存储已经搜索过的节点。
以下为HashSet的常用函数:

函数功能
add添加一个元素
contains判断是否包含一个元素
remove删除一个元素
size返回元素的数目

3.HashMap的应用

若每个元素都存在一个值到另外一个值的映射,那么就用HashMap。
以下为HashMap的常用函数:

函数功能
containsKey判断HashMap中是否包括某个键
get返回键对应的值,否则null
getOrDefault返回键对应的值,否则返回输入的默认值
put添加一组映射,否则修改键对应的值
putIfAbsent当键不存在时,添加一组映射
remove删除某个键
replace修改某个键对应的值
size返回映射数目

可以基于数组实现哈希表。

4.题目

面试30-插入、删除和随机访问都是O(1)的容器
在这里插入图片描述
解题思路:
需要结合哈希表和数组的特性来设计数据容器。
采用长度可变的数组:

ArrayList list = new ArrayList();

其中删除操作若考虑O(1)的时间复杂度,因为不能保证删除的元素总在末尾,所以,将末尾的元素与要删除的元素换位置(单方面交换–看代码),然后删除末尾的元素,注意,都是从0开始。
提交的代码:

class RandomizedSet {HashMap<Integer,Integer> map;//定义哈希表ArrayList<Integer> nums;//定义长度可变的数组//初始化public RandomizedSet(){map=new HashMap<>();nums=new ArrayList<>();}//插入public boolean insert(int val){if(map.containsKey(val)){return false;}map.put(val,nums.size());nums.add(val);return true;}//删除public boolean remove(int val){if(!map.containsKey(val)){return false;}int loc=map.get(val);map.put(nums.get(nums.size()-1),loc);//数组中最后一个元素放在要删除的位置map.remove(val);//map中删除val对应的键值对nums.set(loc,nums.get(nums.size()-1));//数组中最后一个元素放在要删除的位置nums.remove(nums.size()-1);return true;}//返回一个随机数public int getRandom(){Random random=new Random();int r=random.nextInt(nums.size());//随机生成0-nums.size()-1中的数字return nums.get(r);}
}

ArrayList的用法
在这里插入图片描述

相关文章:

哈希表的介绍

1.哈希表的介绍 在哈希表中插入、删除或查找一个元素都只需要O(1)的时间&#xff0c;因此经常被用来优化时间效率。 在Java中&#xff0c;哈希表有两个对应的类型&#xff0c;即HashSet和HashMap。 2.HashSet的应用 若每个元素都只有一个值&#xff0c;则用HashSet&#xf…...

spring cloud gateway 实现redis动态路由及自动项目路由上报

前言 spring cloud gateway默认为内存存储策略&#xff0c;通过配置文件加载的方式生成路由定义信息 可以看到&#xff0c;RouteDefinitionRepository继承了两个父接口&#xff0c;分别为RouteDefinitionLocator和RouteDefinitionWriter&#xff0c;RouteDefinitionLocator定…...

c++函数对象(仿函数)、谓词、内建函数对象

1、函数对象 1.1 概念 重载函数调用操作符的类&#xff0c;这个类的对象就是函数对象&#xff0c;在使用这个函数对象对应使用重载的&#xff08;&#xff09;符号时&#xff0c;行为类似于函数调用&#xff0c;因此这个函数也叫仿函数。 注意&#xff1a;函数对象&#xff0…...

物联网对供应链管理的影响

物联网对于许多行业来说都是一项革命性技术&#xff0c;其应用领域涉及零售、交通、金融、医疗保健和能源等行业。物联网在供应链等流程中已经展示了其深度的潜力。管理、预测和监督应用程序有助于车队运输经理提高配送的运营效率&#xff0c;并增加决策的准确性。如今&#xf…...

c++ 那些事 笔记

GitHub - Light-City/CPlusPlusThings: C那些事 1. ① extern extern关键字&#xff0c;C语言extern关键字用法详解 如果全局变量不在文件的开头定义&#xff0c;其有效的作用范围只限于其定义处到文件结束。如果在定义点之前的函数想引用该全局变量&#xff0c;则应该在…...

心跳机制Redis

 进入命令传播阶段候&#xff0c;master与slave间需要进行信息交换&#xff0c;使用心跳机制进行维护&#xff0c;实现双方连接保持在线 master心跳&#xff1a; 指令&#xff1a;PING 周期&#xff1a;由repl-ping-slave-period决定&#xff0c;默认10秒 作用&#…...

蓝桥杯算法训练合集十七 1.数字反转2.试题39713.矮人采金子4.筛法5.机器指令

目录 1.数字反转 2.试题3971 3.矮人采金子 4.筛法 5.机器指令 1.数字反转 问题描述 给定一个整数&#xff0c;请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式&#xff0c;即除非给定的原数为零&#xff0c;否则反转后得到的新数的最高位数字不应为零&…...

第一章 初识 Spring Security

第一章 初识 Spring Security 1、权限管理 权限管理 基本上涉及到用户参与的系统都要进行权限管理&#xff0c;权限管理属于系统安全的范畴&#xff0c;权限管理实现了对用户访问系统的控制&#xff0c;按照安全规则或者安全策略控制用户可以访问而且只能访问自己被授权的资…...

2023-02-20 关于回朔的思考

摘要: 考虑命运来回动荡交织&#xff0c;一些新的规划在不断的扩充, 而一些历史则开始陷入回朔。 有必要对历史和过往做一些规划和思考。 需要注意在这个阶段, 第一优先级是在反刍中将其最大化。 理论层: 一. 数据库的基础理论 ANSI SQL到词法解析和语法解析mysql的SQL层对…...

推荐系统[八]算法实践总结V1:淘宝逛逛and阿里飞猪个性化推荐:召回算法实践总结【冷启动召回、复购召回、用户行为召回等算法实战】

0.前言:召回排序流程策略算法简介 推荐可分为以下四个流程,分别是召回、粗排、精排以及重排: 召回是源头,在某种意义上决定着整个推荐的天花板;粗排是初筛,一般不会上复杂模型;精排是整个推荐环节的重中之重,在特征和模型上都会做的比较复杂;重排,一般是做打散或满足…...

适合初学者的超详细实用调试技巧(下)

我们日常写代码的时候&#xff0c;常常会遇到bug的情况&#xff0c;这个时候像我这样的初学者就会像无头苍蝇一样这里改改那里删删&#xff0c;调试的重要性也就显现出来&#xff0c;这篇文章接着上文来讲解。 上文地址&#xff1a;(8条消息) 适合初学者的超详细实用调试技巧&…...

C# String与StringBuilder 的区分

重点 1)它是比较的栈里面的值是否相等(值比较) 2)Equals它比较的是堆里面的值是否相等(引用地址值比较) 3)Object.ReferenceEquals(obj1,obj2)它是比较的是内存地址是否相等 问题描述&#xff1a; 今日提交代码时候&#xff0c;被检测工具发出修改建议。遂补充一下知识 1.什么…...

【麒麟】基于GPS北斗卫星技术的NTP网络时间服务器

【麒麟】基于GPS北斗卫星技术的NTP网络时间服务器 【麒麟】基于GPS北斗卫星技术的NTP网络时间服务器 麒麟系统NTP授时方案 设计思路&#xff1a; 在通用的麒麟服务器内部固定一块北斗卫星接收模块并引出卫星天线接口&#xff0c;卫星模块接收北斗卫星数据并解码输出时间数据&…...

“互联网+”下劳动关系认定的现状

1. 劳动关系的认定标准。依据目前我国法律的有关规定, 判定劳动关系存在两种情况:其一, 在有书面劳动合同的情况下, 这时应以书面合同作为认定标准;其二, 在没有书面合同的情况下, 则依据2005年劳社部的《关于确立劳动关系有关事项的通知》来认定, 其中第一条:“用人单位招用劳…...

LPWAN及高效弹性工业物联网核心技术方案

20多年前的一辆拖拉机就是一个纯机械的产品&#xff0c;里面可能并没有电子或者软件的构成&#xff1b;而随后随着软件的发展&#xff0c;拖拉机中嵌入了软件&#xff0c;它能控制发动机的功率及拖拉机防抱死系统&#xff1b;接下来&#xff0c;通过融入各种软件&#xff0c;拖…...

OPTIONS FMTSEARCH

FMTSEARCH 指定要检索的格式目录列表&#xff0c;语法如下&#xff1a;OPTIONS FMTSEARCH(catalog-specification-1<catalog-specification-2 … >);使用PROC FORMAT时可以定义格式目录&#xff0c;LIBRARYlibref或LIBRARYlibref.catalog。格式目录可以是libref或libref.…...

Python3 pip

Python3 pip pip 是 Python 包管理工具&#xff0c;该工具提供了对 Python 包的查找、下载、安装、卸载的功能。 软件包也可以在 https://pypi.org/ 中找到。 目前最新的 Python 版本已经预装了 pip。 注意&#xff1a;Python 2.7.9 或 Python 3.4 以上版本都自带 pip 工具…...

【2023-02-20】JS逆向之翼支付

提示&#xff1a;文章仅供参考&#xff0c;禁止用于非法途径 文章目录前言分析总结前言 真的好久没更了…… 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 分析 进到网页&#xff0c;加载两个接口 applyLoginFactor 接口返回一个RSA公钥&#xff0…...

假如面试官问你Babel的原理该怎么回答

1. 什么是 Babel 简单地说&#xff0c;Babel 能够转译 ECMAScript 2015 的代码&#xff0c;使它在旧的浏览器或者环境中也能够运行。 // es2015 的 const 和 arrow function const add (a, b) > a b;// Babel 转译后 var add function add(a, b) {return a b; };Babel…...

深入Spring底层透析Bean创建过程之拨云见日篇

目录前言一.BeanFactory快速入门1. BeanFactory创建Bean2. BeanFactory和ApplicationContext的关系3. 和ApplicationContext区别(高频问点)4. BeanFactory的继承体系5. ApplicationContext的继承体系二.Bean实例化的基本流程&#xff08;重点)前言 首先感谢您的阅览&#xff0…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...