Hash Table、HashMap、HashSet学习

文章目录

  • 前言
  • Hash Table(散列表)
    • 基本概念
    • 散列函数
    • 散列冲突(哈希碰撞)
    • 拉链法
      • 红黑树
      • 时间复杂度分析
  • HashMap
    • 基础
    • 方法使用
      • 基本的增删改查
      • 其他的方法
    • 实现原理
  • HashSet
    • 基础操作
    • 去重原理

前言

本文用于介绍关于Hash Table、HashMap、HashSet的学习。
本文中有的地方说的是哈希,有的地方说的是散列,只需记住,在本文中哈希就是散列,散列就是哈希。

Hash Table(散列表)

散列表也就是哈希表,在散列表中使用到了红黑树和链表(下面会介绍),无论是HashMap还是HashSet,它们都是基于散列表实现的,所以先简单介绍一下散列表。

基本概念

散列表是根据键key直接访问值value的数据结构,它是由数组演化而来,利用了数组支持按下标进行随机访问数据的特性。

在数组中,索引下标就可以作为key,数组中的元素就可以作为value,我们可以通过下标索引(key)直接获取到数组中的元素(value)。

散列函数

散列表的key可以是各种各样的数据结构,而数组下标是整数,所以将各种各样数据结构的key映射为数组下标的函数就叫散列函数(哈希函数)。可以表示为hashValue=hash(key)

散列函数的基本要求

  • 散列函数计算得到的散列值必须是大于等于0的正整数,因为hashValue需要作为数组的下标
  • 如果key1==key2,那么经过散列函数计算出的hashValue一定相等,即hash(key1)==hash(key2)
  • 如果key1!=key2,那么经过散列函数计算出的hashValue一定不相等,即hash(key1)!=hash(key2)(几乎不可能)

散列冲突(哈希碰撞)

实际上想找到一个散列函数能做到不同的key计算出的hashValue值不同是几乎不可能的,这就是散列冲突,也就是指多个key的hashValue相等,映射到了同一个数组下标

拉链法

拉链法是解决哈希冲突的方法。在散列表中,数组的每个下标位置我们可以称为或者,每个桶(槽)会对应一条链表,所有散列值(hashValue)相同的元素我们会放到相同槽位对应的链表中,如下。

在这里插入图片描述

红黑树

拉链法的使用的链表我们可以改造为效率更高的红黑树,这里简单介绍一下红黑树。

红黑树:是一种自平衡的二叉搜索树(二叉搜索树:对于树中的任意一个节点,左子树节点的值都小于该节点的值,右子树节点的值都大于该节点的值),红黑树与二叉搜索树不同的就是有一个平衡机制,可以避免二叉搜索树的最差情况(链表)。

在这里插入图片描述

红黑树的特性:

  • 节点要么是红色,要么是黑色
  • 根节点是黑色
  • 叶子节点都是黑色的空节点
  • 红黑树中的红色节点的子节点是黑色的
  • 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候,如果不符合这些性质会发生旋转,以达到所有性质,完成性质的目标就是为了保证平衡

红黑树的时间复杂度

  • 查找:红黑树也是二叉搜索树,所以查找的时间复杂度为O(logn)
  • 添加:从根节点开始找到元素添加的位置,时间复杂度为O(logn),添加完成后涉及到时间复杂度为O(1)的旋转操作,所以整体时间复杂度为O(logn)
  • 删除:从根节点开始找到元素删除的位置,时间复杂度为O(logn),删除完成后涉及到时间复杂度为O(1)的旋转操作,所以整体时间复杂度为O(logn)

时间复杂度分析

  • 插入元素:只需通过散列函数计算出相应的槽位,插入槽位对应的链表的末尾即可,时间复杂度为O(1)
  • 查找和删除元素:也是先通过哈希函数计算出相应的槽位,再遍历槽位对应的链表进行插入和删除
    • 在平均情况下(元素分布比较平均)基于链表法解决哈希散列冲突的时间复杂度是O(1)
    • 散列表可能退化为链表(所有元素通过散列函数计算出的槽位都是同一个槽位),查询时间复杂度就变为了O(n)
    • 可以将链表法中的链表改为其他更高效的数据结构,如红黑树(如下图),时间复杂度为O(logn)

在这里插入图片描述

将链表法中的链表改为红黑树还有一个好处:可以防止DDos攻击(分布式拒绝服务攻击,指处于不同位置的多个攻击者对一个或多个目标进行攻击,或者一个攻击者控制位于不同位置的多个机器对目标同时实施攻击),DDos攻击可以伪装大量的key插入链表中,这样我们如果是使用的链表的话访问时效率就会非常低。

HashMap

基础

HashMap是Java中一个非常重要的数据结构,用于存储键值对(key-value)信息。它基于哈希表实现,提供了时间复杂度为O(1)的查找、插入和删除操作,所以从算法层面来说,我们常使用HashMap来判断一个元素是否在集合中。

HashMap具有以下特性:

  • 键值对存储:存储的是键值对,每个键(key)都有一个值(value)
  • 键的唯一性:在HashMap中,键是唯一的,如果先后插入两个键相同的值时,后插入的值会将前面一个值覆盖
  • 无序:不保证元素的顺序,元素的顺序可能会随着插入和删除操作而变化
  • 线程不安全:HashMap是线程不安全的,在多线程环境下,如果多个线程同时访问和修改HashMap,可能造成数据不一致的情况。

方法使用

要使用HashMap,我们需要先对其进行定义:

//键为整数类型,值为字符串类型
HashMap<Integer,String> hashMap=new HashMap<Integer,String>();

基本的增删改查

  • 增加数据
//添加键的同时添加值
hashMap.put(1,"aaa");
hashMap.put(2,"bbb");
hashMap.put(3,"ccc");
  • 删除数据
//根据键删除值
hashMap.remove(1);//清空所有数据
hashMap.clear();
  • 修改数据
//根据键修改数据
hashMap.replace(2,"bbbb");
  • 查询数据
//根据键查询数据
hashMap.get(2);

除此之外还存在一个getOrDefault()方法:

hashMap.getOrDefault(2,defaultValue);

这个方法用于查询是否存在这个key对应的value,如果没有,返回defaultValue。

String defaultValue=hashMap.getOrDefault(4,"ddd");
System.out.println(defaultValue);//由于并未添加键为4,值为ddd的数据,所以输出ddd

其他的方法

  • HashMap是否为空
hashMap.isEmpty();
  • 获取HashMap中键值对的数量
int size=hashMap.size();
  • 是否存在某个键值对
hashMap.containsKey(1);//是否存在键为1的键值对
hashMap.containsValue("aaa");//是否存在值为"aaa"的键值对
  • 分别返回所有键和值
Set<Integer> list1=hashMap.keySet();//所有键的集合
Collection<String> list2=hashMap.values();//所有值的集合

实现原理

HashMap的数据结构:底层使用散列表(哈希表)数据结构,即数组+链表或数组+红黑树

  • 当我们使用put方法向HashMap中添加元素时,会利用key的hashCode计算出hashValue(哈希值),对应两种结果

    • hashValue相同,key也相同:覆盖原始值
    • hashValue相同,key不相同:将当前的key-value存入链表或红黑树中
  • 使用get方法获取数据时,先找到hashValue对应的下标(桶或槽),再进一步通过key找到value

需要注意的是:

  • 在jdk1.8之前:拉链法只有将数组和链表结合,遇到哈希冲突就将冲突的值添加到链表中
  • 在jdk1.8之后:当链表长度大于阈值(默认为8)并且数组长度达到64时,就会将链表转为红黑树,这样做可以减少搜索时间还能防止DDos

HashSet

HashSet是一个不允许有重复元素的集合,但允许存在null值。

特性:

  • 不允许重复:不允许存储重复的元素,使用add方法存储重复的元素时会返回false
  • 无序:内部元素的存储是无序的,就算添加元素时是有序的,HashSet也不保证遍历时的顺序与添加时的一致
  • 高效:添加、删除、查找的时间复杂度都为O(1)

基础操作

  • 定义一个HashSet
Set<Integer> set=new HashSet<Integer>();
  • 添加值
set.add(100);
  • 删除元素
set.remove(100);
//移除所有元素
set.clear();
  • 判断元素是否存在
set.contains(100);

去重原理

HashSet通过hashCode()(用于计算出hashValue)和equals()(比较对象的地址值是否相同)方法实现去重。

在向HashSet添加元素时:会先调用hashCode()方法来计算出hashValue来判断对象加入的位置,如果该位置没有值,则直接插入;如果发现该位置存在值,则会调用equals()方法来判断两个对象是否相同(对象不同就是哈希冲突,上面有介绍),如果相同则添加失败返回false。

学习分享到此结束,希望能对你有所帮助!

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

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

相关文章

图像去噪技术:传统中值滤波与改进中值滤波算法的比较

在数字图像处理中&#xff0c;去噪是一个至关重要的步骤&#xff0c;尤其是在图像受到椒盐噪声影响时。本文将介绍一种改进的中值滤波算法&#xff0c;并与传统的中值滤波算法进行比较&#xff0c;以展示其在去除椒盐噪声方面的有效性。 实验环境 软件&#xff1a;MATLAB图像…

基于Java+SpringBoot+Vue+MySQL的西安旅游管理系统网站

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 基于SpringBootVue的西安旅游管理系统网站【附源码文档】、…

鸿蒙开发(API 12 Beta6版)【NFC标签读写】 网络篇

简介 近场通信(Near Field Communication&#xff0c;NFC)是一种短距高频的无线电技术&#xff0c;在13.56MHz频率运行&#xff0c;通信距离一般在10厘米距离内。电子设备可以通过NFC通信技术和NFC标签通信&#xff0c;从标签中读取数据&#xff0c;或写入数据到标签。 NFC标…

FreeRTOS学习笔记(四)Freertos的中断管理及临界保护

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Cortex-M 中断管理1.1 中断优先级分组1.2 相关寄存器1.3 相关宏定义1.4 FreeRTOS 开关中断 二、临界段及其保护2.1 taskENTER_CRITICAL( ) 和 taskEXIT_CRI…

虚幻引擎VR游戏开发02 | 性能优化设置

常识&#xff1a;VR需要保持至少90 FPS的刷新率&#xff0c;以避免用户体验到延迟或晕眩感。以下是优化性能的一系列设置&#xff08;make sure the frame rate does not drop below a certain threshold&#xff09; In project setting-> &#xff08;以下十个设置都在pr…

强烈推荐!分享5款ai论文生成软件

在当今学术研究和写作领域&#xff0c;AI论文生成工具的出现极大地提高了写作效率和质量。这些工具不仅能够帮助研究人员快速生成论文草稿&#xff0c;还能进行内容优化、查重和排版等操作。以下是五款值得推荐的AI论文生成软件&#xff0c;特别是千笔-AIPassPaper。 ### 千笔-…

C++ —— 关于string类

目录 1. auto和范围for 1.1 auto关键字 1.2 范围for 2. string的三种遍历方式 3. string类的常用接口说明 3.1 成员函数 3.2 Iterators:&#xff08;迭代器&#xff09; 3.2.1正向迭代器和反向迭代器 3.3 Capacity&#xff08;容量&#xff09; 3.4 Modifiers&#x…

智算时空 重塑视界│智汇云舟2024视频孪生产品发布会圆满举行,多个“全球首款”重磅亮相

​秋风送爽&#xff0c;丹桂飘香。9月6日&#xff0c;由北京智汇云舟科技有限公司主办&#xff08;简称&#xff1a;智汇云舟&#xff09;&#xff0c;北京北科软科技有限公司&#xff08;简称&#xff1a;北科软&#xff09;、北京恒升联合科技有限公司&#xff08;简称&#…

Leetcode 236-二叉树的最近公共祖先

同剑指offer 68-II 二叉树的最近公共祖先/lcr 194 题目描述 题目转载自LeetCode 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个结点 p、q&#xff0c;最近公共祖先表示为一个结点 x&#xff0…

【Rust】Mdbook插件开发和分享——多图浏览和多语言代码

mdbook-image-slider 受DevExpress文档多图浏览的启发&#xff0c;我开发这个插件&#xff0c;在查看多个图片和图片的描述的时候非常方便 项目地址&#xff1a;https://github.com/VinciYan/mdbook-image-slider.git 特点 鼠标置于图片查看区域时显示切换图片按钮鼠标点击图…

VS Code 文件定位功能

1、取消“当前打开文件”的自动定位功能。 设置 ->搜索 Explorer: Auto Reveal -> 将配置改为 false 2.在vs2017中定位文件 Tools->Option->Projects And Solutions->General, tick “track Active Item in Solution Explorer” 工具-> 选项->项目和…

iOS——GCD再学习

GCD 使用GCD好处&#xff0c;具体如下&#xff1a; GCD 可用于多核的并行运算&#xff1b;GCD 会自动利用更多的 CPU 内核&#xff08;比如双核、四核&#xff09;&#xff1b;GCD 会自动管理线程的生命周期&#xff08;创建线程、调度任务、销毁线程&#xff09;&#xff1b…

华为手机找不到wifi调试?不急,没有wifi调试一样可以进行局域网模式调试

最近小黄在使用uniapp启动无线调试的时候突然发现华为的手机突然找不到wifi调试了&#xff0c;那么我们怎么进行无线调试呢&#xff1f; 其实他只是找不到开关而已&#xff0c;正常使用就行。 1.使用数据线连接手机。 打开cmd命令行执行&#xff1a;adb tcpip 5555 2.再执行ad…

物联网之Arduino开发环境的下载与安装、ESP32开发环境的下载与安装、常见环境配置问题的解决办法、COM端口不可用的解决方法

MENU 前言下载和安装Arduino安装ESP32开发环境常见问题JSON下载失败和下载速度慢配置解释器没有发现端口检测到端口&#xff0c;但是有警告图标&#xff0c;端口无法使用 前言 想玩开发板必须得写代码&#xff0c;要不然Arduino不知道怎么运行&#xff0c;Arduino的开发语言是C…

❤《实战纪录片 1 》原生开发小程序中遇到的问题和解决方案

《实战纪录片 1 》原生开发小程序中遇到的问题和解决方案 文章目录 《实战纪录片 1 》原生开发小程序中遇到的问题和解决方案1、问题一&#xff1a;原生开发中 request请求中返回 的数据无法 使用this传递给 data{}中怎么办&#xff1f;2、刚登录后如何将token信息保存&#xf…

用于客户支持的 GenAI:探索 Elastic Support Assistant

作者&#xff1a;Chris Blaisure, Cory Mangini 我们很高兴地宣布推出 Elastic 的支持助手。本博客将带你了解我们最新的生成式 AI 工具以及它可以帮助你使用 Elastic 技术的一些常见场景。 Elastic 支持助手现已在 Support Hub 上可用 今天&#xff0c;我们宣布 Elastic 支持…

每日一题,力扣leetcode Hot100之206反转链表

原来的链表是1-2-3-4-5-null 反转后是5-4-3-2-1-null 只需要循环遍历&#xff0c;并且借一个temp便可以完成反转 class Solution:def reverseList(self, head: ListNode) -> ListNode:cur, pre head, Nonewhile cur:tmp cur.next # 暂存后继节点 cur.nextcur.next pre…

【软件测试】盒木进销存管理系统 需求说明书

目录 1 引言 2 项目概述 3 平台、角色和权限 3.1 Web端 4 Web端需求 4.1 登录/注册页面 4.1.1 业务描述 4.1.2 需求描述 4.1.3 行为人 4.1.4 UI页面 4.1.5 业务规则 4.2 首页 4.2.1 业务描述 4.2.2 需求描述 4.2.3 行为人 4.2.4 UI界面 4.2.5 业务规则 4.3报…

回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测+交叉验证

回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测交叉验证 目录 回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测交叉验证效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现基于贝叶…

第144天:内网安全-Linux权限维持OpenSSHPAM后门SSH软链接公私钥登录

目录 案例一&#xff1a; 权限维持-Linux-替换版本-OpenSSH 后门 案例二&#xff1a; 权限维持-Linux-更改验证-SSH-PAM 后门 案例三&#xff1a; 权限维持-Linux-登录方式-软链接&公私钥&新帐号 ssh软链接 公私钥 新帐号 案例一&#xff1a; 权限维持-Linux-替换…