为什么使用哈希表
哈希表
1、作用:
用来快速判断一个元素是否出现在集合中,可以将查找元素的复杂度从O(n)降低到O(1).
2、哈希映射
(1)对于每一个给定的关键字key值,通过哈希函数映射 f(key) 之后,就可以得到一个在哈希表M中 记录该关键字的地址。
(2)通常的操作:
key % (总长度) = 哈希表M中的位置
每个关键字key对应的位置是固定的
(3)<font color="red"存储的数据结构
在python中,其实就是一个字典。
将每个元素都对应一个序号,构成key-value的形式,存在字典中。关键字key的值是元素,经过哈希表映射之后得到的位置是value的值。
当需要查找元素的时候,直接利用dict[key] = value 的形式就可以找到。
3、解决哈希碰撞问题
常用的解决方案有散列法和拉链法。散列法又分为开放寻址法和再散列法
4、哈希表的优势
(1)在列表查找中,使用最广泛的二分查找算法,复杂度为O(log2n),但其始终只能用于有序列表。普通无序列表只能采用遍历查找,复杂度为O(n)。
(2)拥有较为理想的哈希函数实现的哈希表,对其任意元素可以直接通过计算获取位置,查找速度始终为常数级,即O(1)。
5、js中哈希表的实现
js中只有Map,没有HashMap。HashMap只是map的一种底层实现方式。
// 创建一个Map对象
var map = new Map();
// 可以用数组当中的下标作为key,也可以用值作为key
// 检查key是否存在
map.has(key);
// 通过key取对应的value
map.get(key);
// 删除
m.delete('Adam');
// 添加
m.set('Adam', 67);
6、哈希表的空间消耗
使用哈希表的时候,需要用到栈,所以空间复杂度为O(n)
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhficefg
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13