关于散列表(哈希表)我所知道的

简介: 关于散列表(哈希表)我所知道的

image.png


持续创作,加速成长!这是我参与「掘金日新计划 · 10 月更文挑战」的第1天,点击查看活动详情

关键词:散列表 哈希表 哈希算法

什么是散列/哈希表?


散列表其实是数组的一种扩展,由数组演化而来。利用了数组随机访问数据的特性,降低了数据读取的复杂度。使用哈希表可以解决数组由于线性查找效率低,耗时过长的问题。

散列表存储的是由键(key)和值(value)组成的数据。在 JS 中,也可以将对象理解成一种散列表。

其实有点像解码,变量名是 key , 变量值是 value , 输入是入参,输出是出参。函数在里面对应的角色就是将入参通过某种处理,处理成出参。

举个例子:

const A = '1'
const B = '2'
const C = '3'
const D = '4'
const fn = (...args) => {
  return args.join('') * 1
}
console.log(fn(A, B, C))
console.log(fn(A, B, C, D))


image.png



复杂度

平均复杂度 最坏复杂度 数组 链表
查找 O(1) O(n) O(1) O(n)
插入 O(1) O(n) O(n) O(1)
删除 O(1) O(n) O(n) O(1)


在平均情况下,散列表的查找(获取给定索引处的值)速度与数组一样快,而插入和删除速度与链表一样快,因此它兼具两者的优点。

但在最糟情况下,散列表的各种操作的速度都很慢。因此,在使用散列表时,避开最糟情况至关重要。

为此,需要避免冲突。(最好是个正方形)


什么是哈希函数


把给定的数据转换成固定长度的无规律数值。

哈希函数的特征

  • 输出的哈希值数据长度不变。
  • 如果输入的数据相同,那么输出的哈希值也必定相同。
  • 输入的数据相似,输出的哈希值也会有很大差异。
  • 输入的两个数据完全不同,输出的哈希值也有可能相同。这种情况就是 哈希冲突,造成这种情况的原因就是:数组的存储空间有限,数组越短,哈希冲突的概率越大。

典型的哈希算法有:MD5、SHA-1、SHA-2。不同算法有不同的计算方式,所以输入数据相同,算法不同的话,输出的哈希值也会不同。


如何解决哈希冲突


开放地址法


通过多次使用哈希函数或“线性探测法”计算候补地址。如果仍然有冲突,便继续计算下一个候补地址,直到有空地址为止。

优点

  • 不需要拉链表,哈希表中的数据都储存在数组中,查询速度更快。
  • 方便序列化。

缺点

  • 删除数据需要特殊处理。要删除的数据并没有被删除,只是添加了被删除了的标记。
  • 更浪费内存,因为数据都存在数组中

应用场景: 数据量小、需要序列化的时候


链地址法


发生冲突就利用链表在已有数据的后面插入新数据来解决冲突。

优点:

  • 内存利用率高

缺点:

  • 查找的时候比开放地址法复杂。


image.png

参考资料:

《算法图解》


目录
打赏
0
0
0
0
26
分享
相关文章
Alibaba Cloud Linux和CentOS有什么区别?
阿里云服务器Linux操作系统Alibaba Cloud Linux和CentOS有什么区别?
2510 0
Alibaba Cloud Linux和CentOS有什么区别?
微软开源WinJS 使用JavaScript技术打造跨平台应用
最近举办的Build2014大会上,微软的Treadwel介绍了WinJS的前景。微软WinJS已逐渐开源,正逐步实现跨平台开发,现在已经支持Windows和Windows Phone平台,以后将支持Android、iOS和网页版应用。
511 0
微软开源WinJS 使用JavaScript技术打造跨平台应用
格网DEM生成不规则三角网TIN
格网DEM生成不规则三角网TIN
140 0
蓝易云 - 解决git clone时出现Failed to connect to 127.0.0.1 port 1573问题
希望这些信息能帮助你解决问题。如果问题仍然存在,可能需要检查你的网络设置或者联系你的网络管理员。
200 3
网络安全与信息安全:保护数据的科学与艺术
【5月更文挑战第27天】在数字化的浪潮中,数据成为了新的货币。然而,随着信息技术的迅猛发展,网络攻击和信息泄露事件频发,对个人隐私和企业安全构成了严峻挑战。本文深入探讨网络安全的核心议题,包括网络安全漏洞的形成、加密技术的进展以及提升公众安全意识的重要性。通过分析最新的安全趋势和技术,旨在为读者提供一套全面的信息安全防护策略。
【Alibaba工具型技术系列】「EasyExcel技术专题」实战技术针对于项目中常用的Excel操作指南
【Alibaba工具型技术系列】「EasyExcel技术专题」实战技术针对于项目中常用的Excel操作指南
1409 0
【Alibaba工具型技术系列】「EasyExcel技术专题」实战技术针对于项目中常用的Excel操作指南
【使用深度学习的城市声音分类】使用从提取音频特征(频谱图)中提取的深度学习进行声音分类研究(Matlab代码实现)
【使用深度学习的城市声音分类】使用从提取音频特征(频谱图)中提取的深度学习进行声音分类研究(Matlab代码实现)
425 0
Python的文件编码,复制,缓冲,删除
Python的文件编码,复制,缓冲,删除
181 0
Python的文件编码,复制,缓冲,删除
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问