JavaScript数据结构之散列表怎么创建
导读:本文共1674字符,通常情况下阅读需要6分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 一、处理散列值冲突有时候一些键会有相同的散列值。比如aab和baa,从字符串的角度来说它们是不同的值,但是按照我们的散列函数逻辑,将每个字母的 Unicode 码累加得出的散列值,一定是一样的。我们知道在 JavaScript 对象当中,如果赋值时指定的 key 已存在,那么就会覆盖原有的值,比如这个例子:varjson={18:'雷欧'}js... ...
目录
(为您整理了一些要点),点击可以直达。有时候一些键会有相同的散列值。比如aab
和baa
,从字符串的角度来说它们是不同的值,但是按照我们的散列函数逻辑,将每个字母的 Unicode 码累加得出的散列值,一定是一样的。
我们知道在 JavaScript 对象当中,如果赋值时指定的 key 已存在,那么就会覆盖原有的值,比如这个例子:
为了避免上述代码中出现的风险,我们需要想办法处理,如何使key != key
,则hash != hash
?
目前可靠的方法有两个,分别是:分离链接
和线性探查
。
分离链接法是指在散列表存储数据时,value 部分用链表
来代替之前的键值对
。键值对只能存储一个,而链表可以存储多个键值对。如果遇到相同的散列值,则在已有的链表中添加一个键值对即可。
我们需要重写三个方法:put、get 和 remove。我们看如何实现:
首先还是基本的类结构,然后看put
方法:
LinkedList 类是标准的链表类,在链表篇讲过如何实现,这里直接使用
对比上篇的散列表 put 方法,你会发现差别不大,变化的部分如下:
优化后的逻辑是,在存储数据时,将键值对存在一个链表里。如果有相同的hash
值,则向已有的链表中添加一个键值对,这样就避免了覆盖。
不过这种方式也有弊端,每添加一个键值对就要创建一个链表,会增加额外的内存空间。
get 方法:
新的 get 方法明显比之前的复杂了许多。主要逻辑是根据 key 找到一个链表,然后再遍历链表找到与参数 key 相匹配的键值对,最后返回找到的值。
while 循环中使用 return 可以直接中止当前函数
JavaScript数据结构之散列表怎么创建的详细内容,希望对您有所帮助,信息来源于网络。