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

【算法】哈希表详解

【算法】哈希表详解

  • 1. 哈希表的基本概念
  • 2. 哈希表的优缺点
  • 3. 哈希表的实现方法
  • 4. 哈希表的应用场景
  • 5. 哈希表的性能优化
  • 6. 哈希表 vs 其他数据结构
  • 7. 总结

哈希表(Hash Table) 是一种高效的数据结构,用于存储键值对(Key-Value Pairs)。它通过哈希函数将键(Key)映射到表中的特定位置,从而实现快速的数据插入、删除和查找操作。哈希表的核心思想是通过空间换时间,将平均时间复杂度降低到接近 O(1)。

1. 哈希表的基本概念

  • 键值对(Key-Value Pair)哈希表存储的是键值对,其中:
    键(Key):唯一标识数据的值。
    值(Value):与键相关联的数据。

  • 哈希函数(Hash Function)
    哈希函数将键映射到一个固定范围的整数(通常称为哈希值或索引)。

  • 理想情况下,哈希函数应满足:
    一致性:相同的键总是映射到相同的索引。
    均匀性:不同的键应尽可能均匀地分布到不同的索引。

  • 哈希冲突(Hash Collision)
    当两个不同的键通过哈希函数映射到同一个索引时,称为哈希冲突。冲突会影响哈希表的效率,要尽可能减少冲突

  • 影响散列表性能的因素
    散列函数
    装填因子
    处理冲突的方式

  • 装填因子 = 表中的元素数/表长度
    装填因子越大,冲突的可能性越大
    装填因子越小,冲突的可能性越小,但空间利用率越低

  • 常见的解决冲突的方法包括:
    链地址法(Chaining):将冲突的键值对存储在同一个索引位置的链表中。
    开放地址法(Open Addressing):通过探测方法(如线性探测、二次探测)寻找下一个可用的索引。

2. 哈希表的优缺点

  • 优点
    高效的查找、插入和删除:
    平均时间复杂度为 O(1)。
    灵活性:可以存储任意类型的键值对。
    空间利用率高:通过合理的哈希函数设计,可以减少空间浪费。

  • 缺点
    哈希冲突:冲突可能导致性能下降,最坏情况下时间复杂度退化为 O(n)。
    哈希函数设计复杂:需要设计一个均匀分布的哈希函数。
    空间开销:为了减少冲突,哈希表通常需要预留额外的空间。

3. 哈希表的实现方法

详细讲解可见视频:【散列表(哈希表) - 散列函数, 冲突处理, 平均查找长度(ASL)-哔哩哔哩】 https://b23.tv/46ltfTx

  • 直接定址法: 适合关键字基本连续的情况
    H(key)= key 或 H(key)=a*key +b
  • 除留余数法:求余操作可以把不连续的关键字映射到连续的地址空间
    H(key) = key%p【p一般取小于等于表长的最大质数】

4. 哈希表的应用场景

  • 字典(Dictionary):哈希表是字典的底层实现,用于快速查找单词的定义。

  • 数据库索引:数据库使用哈希表加速数据的查找和检索。

  • 缓存(Cache):哈希表用于实现缓存系统(如 Redis),快速存取数据。

  • 唯一性检查:哈希表可用于检查数据是否重复(如检测重复文件)。

  • 编译器符号表:编译器使用哈希表存储变量和函数的信息。

5. 哈希表的性能优化

  • 设计良好的哈希函数:哈希函数应尽可能均匀分布键,减少冲突。
  • 动态扩容:当哈希表的负载因子(元素数量 / 表大小)超过阈值时,动态扩容以减少冲突。
  • 冲突解决策略:根据应用场景选择合适的冲突解决方法(如链地址法或开放地址法)。
  • 缓存友好:优化内存布局,提高缓存命中率。

6. 哈希表 vs 其他数据结构

数据结构查找时间复杂度插入/删除时间复杂度适用场景
哈希表O(1)O(1)快速查找、插入、删除
平衡二叉树O(log n)O(log n)有序数据、范围查询
数组O(1)O(n)随机访问、固定大小数据
链表O(n)O(1)频繁插入、删除,无需随机访问

7. 总结

哈希表是一种高效的数据结构,适用于需要快速查找、插入和删除的场景。

哈希函数和冲突解决方法是哈希表设计的核心。

在实际应用中,哈希表被广泛用于字典、数据库索引、缓存等场景。

相关文章:

【算法】哈希表详解

【算法】哈希表详解 1. 哈希表的基本概念2. 哈希表的优缺点3. 哈希表的实现方法4. 哈希表的应用场景5. 哈希表的性能优化6. 哈希表 vs 其他数据结构7. 总结 哈希表(Hash Table) 是一种高效的数据结构,用于存储键值对(Key-Value Pa…...

【红队利器】单文件一键结束火绒6.0

关于我们 4SecNet 团队专注于网络安全攻防研究,目前团队成员分布在国内多家顶级安全厂商的核心部门,包括安全研究领域、攻防实验室等,汇聚了行业内的顶尖技术力量。团队在病毒木马逆向分析、APT 追踪、破解技术、漏洞分析、红队工具开发等多个…...

Docker小游戏 | 使用Docker部署star-battle太空飞船射击小游戏

Docker小游戏 | 使用Docker部署star-battle太空飞船射击小游戏 前言项目介绍项目简介项目预览二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署star-battle网页小游戏下载镜像创建容器检查容器状态检查服务端口安全设置四、访问star-battle网页小游戏五、总…...

【EB-06】SystemCreator dbc转arxml

SystemCreator dbc转arxml 1. SystemCreator 意义2. SystemCreator使用方法2.1 实现步骤2.2 参考官方文档方法1. SystemCreator 意义 EB Tresos 对dbc直接导入的支持不是很完善,dbc也不是AUTOSAR标准的数据库文件,EB建议所有通信矩阵通过ARXML交互比较合理(AUTOSAR定义的)…...

(0)阿里云大模型ACP-考试回忆

这两天通过了阿里云大模型ACP考试,由于之前在网上没有找到真题,导致第一次考试没有过,后面又重新学习了一遍文档才顺利通过考试,这两次考试内容感觉考试题目90%内容是覆盖的,后面准备分享一下每一章的考题,…...

按键精灵鹰眼中控:ios多设备管理工具

在当今数字化时代,高效管理多设备已成为许多企业和个人的迫切需求。无论是游戏多开、自动化测试,还是电商运营,如何同时操作多台设备并确保精准执行,一直是一个难题。现在,按键精灵的鹰眼群控功能为您提供了完美的解决…...

__对于初学者的CCS 汉化

IDE:Code Composer Studio 20.0.2 CCS安装后默认是英文,目前最新的20版其Help工具栏是没有安装软件包的选项。不过,想要汉化还有更简单的方法 安装插件 在左边找到扩展,然后在框内搜索Chinese,可以找到两个语言插件&am…...

JavaScript 系列之:Ajax、Promise、Axios

前言 同步:会阻塞。同步代码按照编写的顺序逐行依次执行,只有当前的任务完成后,才会执行下一个任务。 异步:异步代码不会阻塞后续代码的执行。当遇到异步操作时,JavaScript 会将该操作放入任务队列中,继续…...

Vidma Ver.2.14.0 高级版

Vidma Ver.2.14.0 高级版 Vidma 是一款易于使用的视频编辑器,提供多种音乐和流行视频效果选择,让您的视频在社交媒体上脱颖而出。您可以通过添加 swooshing 文本、流行效果、复古滤镜、精美贴纸、平滑过渡等等,轻松地从您的宝贵时刻创建有意…...

Redis Lua Script 溢出漏洞(CVE-2024-31449)

目录 漏洞描述 目前受影响的Redis版本: 安全版本 解决建议 升级Redis版本 查看旧redis版本信息 备份Redis数据 1.查看目前redis的key 2.备份数据 3.查看备份文件地址 4.将旧Redis安装目录备份 安装新版本Redis 1.下载redis安装包 2.安装redis 3.启动…...

【Mysql】我在广州学Mysql 系列—— 性能优化相关例题

ℹ️大家好,我是练小杰,时间过得真快,还有2天,2025年2月份就结束了!!😆 本文是针对Mysql数据库中有关性能优化的相关示例,通过本文的学习可以深入了解性能优化的各类命令&#xff01…...

java23种设计模式-中介者模式

中介者模式(Mediator Pattern)学习笔记 编程相关书籍分享:https://blog.csdn.net/weixin_47763579/article/details/145855793 DeepSeek使用技巧pdf资料分享:https://blog.csdn.net/weixin_47763579/article/details/145884039 1.…...

鸿蒙next 点击穿透实现

点击穿透可以参考华为开发的保留文章,该章节只能在developer preview版本下查看 点击穿透 主要的方法是hitTestBehavior // xxx.ets Entry Component struct HitTestBehaviorExample {build() {// outer stackStack() {Button(outer button).onTouch((event) > {console.i…...

OpenAPI Generator:API开发的瑞士军刀

一、工具介绍 OpenAPI Generator是基于OpenAPI规范(Swagger)的代码生成工具,支持50种编程语言的客户端/服务端代码生成。其核心价值在于: 自动化生成⇒减少重复劳动规范API开发流程 核心能力矩阵: 功能支持示例客户端SDK生成Java/Python/T…...

某住宅小区地下车库安科瑞的新能源汽车充电桩的配电设计与应用方案 安科瑞 耿笠

摘要:纯电动商用车的工作环境存在路况复杂、工况恶劣等情况,导致整车电气设备的磨损速率加快,造成电气设备绝缘电阻持续下降,如不及时处理,可能存在安全隐患或引发重大安全事故。文章从绝缘故障检测原理出发&#xff0…...

电子科技大学考研复习经验分享

电子科技大学考研复习经验分享 本人情况:本科就读于电科软院,24年2月开始了解考研,24年3月开始数学,9月决定考本院(开始全天候图书馆学习)并开始专业课学习,11月底开始政治学习,最后…...

2025面试Go真题第一场

前几天参加了一场面试,GoLang 后端工程师,他们直接给了我 10 道题,我留了一个截图。 在看答案之前,你可以先简单做一下,下面我会对每个题目做一个说明。 文章目录 1、golang map 是否并发安全?2、协程泄漏的原因可能是…...

【量化策略】趋势跟踪策略

【量化策略】趋势跟踪策略 🚀量化软件开通 🚀量化实战教程 技术背景与应用场景 在金融市场中,趋势跟踪策略是一种基于市场趋势进行交易的量化投资方法。该策略的核心思想是“顺势而为”,即当市场出现明显的上升或下降趋势时&a…...

leetcode 541. 反转字符串 II 简单

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。 如果剩余字符少于 k 个,则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符&…...

org.springframework.boot不存在的其中一个解决办法

最近做项目的时候发现问题,改了几次pom.xml文件之后突然发现项目中的注解全部爆红。 可以尝试点击左上角的循环小图标,同步所有maven项目。 建议顺便检查一下Project Structure中的SDK和Language Level是否对应,否则可能报类似:“…...

<6>-MySQL表的增删查改

目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表&#xf…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...

JVM垃圾回收机制全解析

Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、👨‍🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨‍&#x1f…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...