网站首页 > 技术文章 正文
今天聊聊「哈希表」,「哈希表」主要作用在于高效查找。
在编程实现中,常常面临着两个问题:存储和查找,存储和查找的效率往往决定了整个程序的效率。
脑补下,你在家里忘记了指甲刀放在哪里,通常要在你家所有抽屉中顺序寻找,直到找到,最差情况下,有N个抽屉,你就要打开N个抽屉。这种存储方式叫数组,查找方法称为「遍历」。
脑补下,你是一个整理控,所有物品必须分门别类放入整理箱,再将整理箱编号,比如1号放入针线,2号放入证件,3号放入细软。这种存储和查找方式称为「哈希」,如果这个时候要查找护照,你不许要再翻所有抽屉,直接可在2号整理箱中获取,通常只用一次查找即可,如何编号整理箱,称为哈希算法。
同样是查找,差距怎么那么大涅~,假设我们有100亿条数据记录,那差距就变得明显,遍历需要查找最多100亿次,最少1次,哈希只需1次。
让我们正式介绍哈希和哈希算法,哈希也称散列,哈希表是一种与数组、链表等不同的数据结构,与他们需要不断的遍历比较来查找的办法,哈希表设计了一个映射关系f(key)= address,根据key来计算存储地址address,这样可以1次查找,f既是存储数据过程中用来指引数据存储到什么位置的函数,也是将来查找这个位置的算法,叫做哈希算法。
让我们举个例子,比如下面这几个人物,按数组存储:
这样我要找到大胸姐的电话号码,需要顺序查找对比整个数组,第一个余罪,不是,第二个不是,第三个不是,直到第四个找到大胸姐。
如果以hash存储呢?首先让我们来看看如何设计哈希算法,哈希算法可以随意设计,教科书上一般会说以下几种方法:直接定址发,平方取中法,除数取余法,哈希算法的本质上是计算一个数字,如果用这几种方法讲解会稍显晦涩,我们假设我们的哈希算法是取姓名的首字母。所以f(余罪) = y, f(傅老大) = f,f(沈嘉文) = s,f(大胸姐) = d。
构建的hash表如下:
我们看到他们分别以姓名首字母的位置插入到这一张表格中,这样我们构建了这样一个Key-Value表格,此表就是哈希表,也称为Hash Table。未来,当我们要查找余罪的时候,通过计算,余罪在y位置,可以通过1次查找,找到这条记录,也即手机号。
这个时候有客官问了,那以首字母为哈希函数的话,应该有很多比如以y的姓名啊,这个时候就不是一次查找了吧,其实有很多条记录都映射到一个位置上,称为哈希冲突。
哈希冲突是跟哈希函数的设计正相关的,你的随机性越大,那么产生哈希冲突的可能性越小,在小概率下,如果还有冲突怎么办,这个时候要做些有损的设计,比如如果有两个首字母为y的姓名,那么可以接到余罪的后面,当查找的时候,需要先查找到y,然后再顺序查找,如图所示:
还有一些解决哈希冲突的办法叫「哈希再哈希」,也就是针对第一次哈希的结果再进行一次hash来减小冲突的概率。
这就是Hash表,首先Ta是一种数据结构,是一种效率极高的查找方式,哈希表的核心在于哈希函数的设计,哈希冲突了不要紧,我们要增加随机性以及对冲突进行适当的有损化的处理。
#专栏作家#
给产品经理讲技术,微信公众号(pm_teacher),人人都是产品经理专栏作家。资深程序猿,专注客户端开发若干年,对前端、后台技术略懂,热衷于对新的科技领域的探索。
本文原创发布于人人都是产品经理。未经许可,禁止转载。
题图来自PEXELS,基于CC0协议
猜你喜欢
- 2024-10-12 百度 面试题——Redis的对象类型与内部编码
- 2024-10-12 五分钟带你了解哈希算法究竟是什么!
- 2024-10-12 Redis哈希类型的使用场景 redis哈希槽的概念
- 2024-10-12 Redis哈希类型使用命令 redis 哈希操作
- 2024-10-12 对象存储服务器Minio(超详细) 对象存储服务适于哪些场景
- 2024-10-12 基于Vision Transformer的视频哈希检索识别虚假视频
- 2024-10-12 Java高级面试之哈希表 哈希表java实现
- 2024-10-12 Redis 选择hash还是string 存储数据?
- 2024-10-12 特征工程:基于梯度提升模型的特征编码效果测试
- 2024-10-12 Redis 讲解系列之 Redis的五大数据类型和配置文件解读
你 发表评论:
欢迎- 最近发表
-
- 在 Spring Boot 项目中使用 activiti
- 开箱即用-activiti流程引擎(active 流程引擎)
- 在springBoot项目中整合使用activiti
- activiti中的网关是干什么的?(activiti包含网关)
- SpringBoot集成工作流Activiti(完整源码和配套文档)
- Activiti工作流介绍及使用(activiti工作流会签)
- SpringBoot集成工作流Activiti(实际项目演示)
- activiti工作流引擎(activiti工作流引擎怎么用)
- 工作流Activiti初体验及在数据库中生成的表
- Activiti工作流浅析(activiti6.0工作流引擎深度解析)
- 标签列表
-
- oraclesql优化 (66)
- 类的加载机制 (75)
- feignclient (62)
- 一致性hash算法 (71)
- dockfile (66)
- 锁机制 (57)
- javaresponse (60)
- 查看hive版本 (59)
- phpworkerman (57)
- spark算子 (58)
- vue双向绑定的原理 (68)
- springbootget请求 (58)
- docker网络三种模式 (67)
- spring控制反转 (71)
- data:image/jpeg (69)
- base64 (69)
- java分页 (64)
- kibanadocker (60)
- qabstracttablemodel (62)
- java生成pdf文件 (69)
- deletelater (62)
- com.aspose.words (58)
- android.mk (62)
- qopengl (73)
- epoch_millis (61)
本文暂时没有评论,来添加一个吧(●'◡'●)