数据结构编程实践20讲(Python版)—18哈希表
本文目录
- 18 哈希表(Hash Table)
- S1 说明
- 特征
- 解决问题
- S2 示例
- 示例 1
- 示例 2
- S3 应用
- 应用1: LRU 缓存机制
- 应用2:高级拼写检查器
- 应用3:DNA 序列的 K-mer 计数
往期链接
| 01 数组 | 02 链表 | 03 栈 | 04 队列 | 05 二叉树 | 06 二叉搜索树 | 07 AVL树 | 08 红黑树 | 09 B树 | 10 B+树 |
|---|
| 11 线段树 | 12 树状数组 | 13 图形数据结构 | 14 邻接矩阵 | 15 完全图 | 16 有向图 | 17 散列 |
|---|
18 哈希表(Hash Table)
S1 说明
哈希表(Hash Table)是一种用于存储键值对的数据结构,通过哈希函数将键映射到数组的索引位置,从而实现快速的查找、插入和删除操作。哈希表的基本思想是将数据存储在一个数组中,并使用哈希函数计算每个元素的存储位置。
特征
- 快速查找:
哈希表的查找、插入和删除操作的平均时间复杂度为 O ( 1 ) O(1) O(1),在最坏情况下为 O ( n ) O(n) O(n),但通过良好的哈希函数和冲突解决策略,可以保持接近 O ( 1 ) O(1) O(1)的性能。 - 键唯一性:
在哈希表中,每个键都是唯一的。若插入相同的键,则会更新其对应的值。 - 哈希函数:
哈希函数将键转换为数组索引。一个好的哈希函数应该能够均匀分布键,减少冲突的发生。 - 冲突解决:
当不同的键映射到相同的索引时,会发生冲突。常用的冲突解决方法有链式地址法(使用链表存储同一索引的多个元素)和开放地址法(寻找下一个空位)。 - 动态扩展:
当哈希表装载因子(存储的元素数量与数组大小的比率)超过某个阈值时,通常会进行扩展,以保持高性能。
解决问题
哈希表可以解决许多实际问题,包括但不限于:
- 缓存:使用哈希表存储计算结果或频繁访问的数据,实现快速访问。
- 数据去重:通过哈希表存储已访问的数据,快速判断新数据是否为重复。
- 频率统计:在字典或集合中存储数据频率,便于快速查找和更新。
- 索引建立:在数据库中使用哈希表建立索引,提高数据检索速度。
- 密码存储:在用户认证中,使用哈希表存储用户信息,提高查找效率。
S2 示例
示例 1
class Person:def __init__(self, name, age):self.name = nameself.age = agedef __hash__(self):"""自定义哈希函数,将名字和年龄结合起来生成哈希值"""return hash((self.name, self.age))def __eq__(self, other):"""比较两个对象是否相等"""if isinstance(other, Person):return self.name == other.name and self.age == other.agereturn False# 创建一些对象
person1 = Person("敖耳散", 30)
person2 = Person("包而嗣", 25)
person3 = Person("敖耳散", 30)# 使用哈希值
print(f"Hash of person1: {hash(person1)}")
print(f"Hash of person2: {hash(person2)}")
print(f"Hash of person3: {hash(person3)}")# 比较对象
print(f"person1 == person3: {person1 == person3}") # 输出: True
print(f"person1 == person2: {person1 == person2}") # 输出: False# 使用对象作为字典的键
person_dict = {person1相关文章:
数据结构编程实践20讲(Python版)—18哈希表
本文目录 18 哈希表(Hash Table)S1 说明特征解决问题S2 示例示例 1示例 2S3 应用应用1: LRU 缓存机制应用2:高级拼写检查器应用3:DNA 序列的 K-mer 计数往期链接 01 数组02 链表03 栈04 队列05 二叉树06 二叉搜索树07 AVL树08 红黑树09 B树10 B+树11 线段树12 树状数组13 …...
Html 标题加图标
每个网页选项卡都有一个图标: <meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>主页</title><link rel"icon" href"images/记事本.png&…...
机器学习探索性数据分析 (EDA)
机器学习探索性数据分析 (EDA) 探索性数据分析(Exploratory Data Analysis, EDA)是机器学习工作流中至关重要的一个步骤,通过深入分析和理解数据的结构、分布和相关性,EDA帮助揭示数据背后的故事,并为后续的建模提供有…...
【K8S系列】Kubernetes pod节点Pending或CrashLoopBackOff 问题及解决方案详解【已解决】
在 Kubernetes 中,Pod 是最小的可调度单元,负责运行容器。当 Pod 的状态显示为 Pending 或 CrashLoopBackOff 时,意味着它无法成功启动或持续崩溃。本文将详细分析这两种状态的原因、排查步骤、执行后的结果及相应的解决方案。 一、Pod 状态概…...
【Redis】Zset类型常用命令
文章目录 一. Zset有序集合简介.二. 添加元素相关命令.2.1 向有序集合中添加元素(zadd) 三. 查询元素相关操作.3.1 查询有序集合中的元素个数( zcard zcount)3.2 查询指定区间内的元素(zrange zrevrange zrangebyscore)3.3 查询有序集合中指定成员的排名(zrank zrevrank )3.4 查…...
js中map,filter,find,foreach的用法介绍
js中map,filter,find,foreach的用法介绍 在 JavaScript 中,数组提供了一些常用的迭代方法,如 map、filter、find 和 forEach,这些方法允许你对数组中的每个元素进行操作,下面是它们的用法和区别…...
Linux 重置 root 密码
如果您在Linux系统中忘记了root密码,可以按照以下步骤重置: 重启系统。在启动时,当GRUB菜单出现时,选择要启动的内核版本,然后按 e 键编辑启动选项。找到以linux或linux16开头的行,它包含了启动内核的命令…...
【含开题报告+文档+PPT+源码】基于SpringBoot+Vue的停车场管理系统
开题报告 随着城市化进程不断加快,汽车保有量持续增长,城市停车问题日益凸显,传统停车场管理手段面临着诸多挑战,诸如管理效率低、人工成本高、信息更新滞后、收费不透明等问题。鉴于此,基于 Web 的智能停车场管理系统…...
博睿数据首届“观测先锋 · 2024 可观测平台创新应用案例大赛”现已启动!
大赛报名火热进行中! 在当今这个数字化、智能化的时代,可观测性技术已经成为企业IT架构中不可或缺的一部分。它能够帮助企业实时监控系统的运行状态,及时发现并解决潜在问题,从而确保业务的稳定性和连续性。博睿数据一体化智能可观…...
笔记:SOME/IP-SD报文中的TTL
问:SOME/IP-SD报文中有几个参数名字都叫的TTL,请问它们有什么不同? 答:在SOME/IP Service Discovery (SOME/IP-SD)协议中,确实有多个与TTL(Time-To-Live)相关的参数,但它们的含义不…...
9.存储过程安全性博客大纲(9/10)
存储过程安全性博客大纲 引言 在数据库系统中,存储过程是一种预先编写好的SQL代码集合,它被保存在数据库服务器上,可以通过指定的名称来调用执行。存储过程可以包含一系列的控制流语句,如IF条件语句、WHILE循环等,使…...
android 打包成aar
1 先建立的空白新工程(不能有activity,直接建立No Activity的项目就行) 2 建立新library 3 填写自己的内容 4 5 如果代码有红色提示的错误,会提示打包失败,修改红色的错误提示就行...
服务器和中转机在网络安全方面
服务器和中转机(代理服务器)在网络安全方面扮演着不同的角色,各自承担着保护网络资源和控制网络访问的重要职责。 它们在网络安全方面的主要作用: 服务器在网络安全中的角色 1.服务保护: 服务器通常运行着各种网络…...
解决“无法从 System.String 强制转换或转换为 Class 对象”错误
解决“无法从 System.String 强制转换或转换为 Class 对象”错误 在进行 API 自动化时,我必须反序列化响应以解析 API 响应数据。我们使用 Newtonsoft.Json NuGet 来实现这一点。 我在反序列化过程中遇到以下错误 - Newtonsoft.Json.JsonSerializationExceptionH…...
Git:LF will be replaced by CRLF、pytest PermissionError以及Git应用中的一些问题解决及一些使用技巧
一、Git:LF will be replaced by CRLF和pytest: --cov NTERNALERROR PermissionError 1. git warning: LF will be replaced by CRLF in ***file 偶然git add在进行代码提交的时候碰到警告warning: LF will be replaced by CRLF in ***file,原因是编辑的代码内容中…...
云原生之运维监控实践-使用taosKeeper与TDinsight实现对TDengine服务的监测告警
背景 如果没有监控,那么最好的情况是没有问题发生,最糟糕的情况则是问题发生了但没有被发现。——《Prometheus监控实战》 在10月10日收到了 TDengine 官方微信公众号的一条推送,摘要如下: 今天(2024年10月10日)我们非常高兴地宣布…...
前端js,vue系统使用iframe嵌入第三方系统的父子系统的通信
前端js,vue系统使用iframe嵌入第三方系统的父子系统的通信 1,父子系统之间的通信问题 父系统给子系统传值可通过postMessage方式进行通信,postMessage(“传递的数据”,url) 1.1 父系统给子系统的传值 let iframe document.getElementById(childFrame); let o1 {…...
树莓派刷入OpenWrt后扩容overlay的方法
问题: 128G的SD卡刷入openwrt后发现可用空间不足100M(我用的squashfs固件,ext4也存在同样的问题,但能否用此方法需要自己尝试一下)。 rootOpenWrt:~# df -h Filesystem Size Used Available Use%…...
【JS】Node.js读取execle表格中的数据
在Node.js中读取.xlsx格式的Excel文件,可以使用xlsx库。这个库非常流行且易于使用。下面是一个基本示例,展示如何使用xlsx库读取.xlsx文件中的数据。 首先,你需要安装xlsx库。你可以使用npm来安装: npm install xlsx然后&#x…...
怎么为pdf文件设置密码?几种PDF文件设置密码的方法推荐
怎么为pdf文件设置密码?设置PDF文件密码,正是应对这一挑战的有效手段之一。通过为PDF文件设置密码,我们能够为文档加上一道安全锁,确保只有掌握密码的用户才能打开和查看文件内容。这一措施不仅保护了文档的隐私性,还防…...
Suricata在CentOS7上的性能优化:如何配置网卡混杂模式与端口聚合
Suricata在CentOS7上的性能优化:网卡混杂模式与端口聚合实战指南 当企业网络流量突破千兆级别时,传统单网卡监控方案往往力不从心。我曾为某金融客户部署Suricata时,单台服务器每天要处理超过2TB的流量数据,正是通过下文介绍的网卡…...
多模态数据挖掘前沿:生物医学与情感分析领域论文深度解析
多模态数据挖掘前沿:生物医学与情感分析领域论文深度解析 在人工智能与大数据技术飞速发展的当下,多模态数据因能更全面、立体地刻画研究对象,已成为科研领域的核心研究方向。本文将深度解析两篇聚焦多模态数据挖掘的重磅论文——《多模态生物…...
基于cartographer算法的自主导航系统仿真设计 移动机器人系统具备定位、建图及路径规划功能
基于cartographer算法的自主导航系统仿真设计 移动机器人系统具备定位、建图及路径规划功能,在迷宫式的环境中建模导航。 模型以及移动机器人模型,移动机器人模型包含2D激光雷达传感器、轮式里程计以及惯性导航原件 基于cartographer算法建图,…...
告别代码噩梦:用Awesome-Dify-Workflow零代码30分钟实现企业级登录系统
告别代码噩梦:用Awesome-Dify-Workflow零代码30分钟实现企业级登录系统 【免费下载链接】Awesome-Dify-Workflow 分享一些好用的 Dify DSL 工作流程,自用、学习两相宜。 Sharing some Dify workflows. 项目地址: https://gitcode.com/GitHub_Trending/…...
【大窗除强信号,小窗清残留】基于双尺度广义交叉验证阈值的地震信号自适应剥离和噪声提取方法(MATLAB)
背景知识在环境噪声层析成像等研究中,我们需要的是纯粹的“噪声”记录,而不是被地震信号“污染”的波形。传统方法是人工剔除含事件的时间段,或者用时间域归一化压制信号,但这些方法要么主观,要么难以彻底去除能量较强…...
gemeni 生成图片的提示词
[System / Prompt]You are an illustration assistant specialized in creating hand-drawn cartoon-style infographics. Follow all rules below strictly and without deviation.🎨 STYLE RULES(风格规则)Use a pure hand-drawn illustrat…...
提升开放平台开发效率,快马AI工具链自动化集成与测试
在企业级开放平台的开发过程中,效率往往是决定项目成败的关键因素之一。传统的开发流程中,开发者需要花费大量时间在重复性工作上,比如编写API客户端代码、配置测试环境、维护文档等。这些工作不仅耗时,还容易出错。今天我想分享一…...
FPGA Multiboot翻车实录:从XDC配置到ICAPE2,我的W25Q128分区血泪史与避坑指南
FPGA Multiboot实战:从配置陷阱到Flash分区优化的全流程解析 第一次在量产产品中实现FPGA远程更新功能时,我盯着实验室里突然变砖的开发板,后背渗出一层冷汗。原本以为按照官方文档配置就能万无一失,没想到Multiboot这个看似简单的…...
RTC成语音AI基础设施:AWS和ElevenLabs相继跟进,ZEGO已跑三年
2026 年 3 月,语音 AI 领域迎来一个值得关注的技术信号:AWS(亚马逊云科技)与 ElevenLabs 在同一个月内相继宣布支持 WebRTC 协议。这一时间上的高度吻合,折射出行业对实时语音交互底层架构的共同判断:传统 …...
MxRadioRF2xx库:ARM Mbed平台RF2xx射频驱动开发指南
1. MxRadioRF2xx 库概述 MxRadioRF2xx 是一个专为 ARM Mbed OS 平台设计的 Atmel(现 Microchip)RF2xx 系列射频收发器驱动库。该库并非对底层寄存器操作的简单封装,而是面向嵌入式无线应用开发者的工程化抽象层,其核心目标是&…...
