导航：首页 > 开发技术 >

JavaScript数据结构之散列表怎么创建

发表于：2024-12-13 作者：千家信息网编辑

千家信息网最后更新 2024年12月13日，本文小编为大家详细介绍"JavaScript数据结构之散列表怎么创建"，内容详细，步骤清晰，细节处理妥当，希望这篇"JavaScript数据结构之散列表怎么创建"文章能帮助大家解决疑惑，下面跟着小编的

千家信息网最后更新 2024年12月13日JavaScript数据结构之散列表怎么创建

本文小编为大家详细介绍"JavaScript数据结构之散列表怎么创建"，内容详细，步骤清晰，细节处理妥当，希望这篇"JavaScript数据结构之散列表怎么创建"文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

一、处理散列值冲突

有时候一些键会有相同的散列值。比如 aab 和 baa，从字符串的角度来说它们是不同的值，但是按照我们的散列函数逻辑，将每个字母的 Unicode 码累加得出的散列值，一定是一样的。

我们知道在 JavaScript 对象当中，如果赋值时指定的 key 已存在，那么就会覆盖原有的值，比如这个例子：

var json = { 18: '雷欧' }json[18] = '欧布'console.log(json) // { 18: '欧布' }

为了避免上述代码中出现的风险，我们需要想办法处理，如何使 key != key，则 hash != hash？

目前可靠的方法有两个，分别是：分离链接 和 线性探查。

1.分离链接

分离链接法是指在散列表存储数据时，value 部分用 链表 来代替之前的 键值对。键值对只能存储一个，而链表可以存储多个键值对。如果遇到相同的散列值，则在已有的链表中添加一个键值对即可。

我们需要重写三个方法：put、get 和 remove。我们看如何实现：

class HashTableSeparateChaining {  constructor() {    this.table = {}  }}

2.put 方法

首先还是基本的类结构，然后看 put 方法：

put(key, value) {  if(key !== null && value !== null) {    let pos = this.hashCode(key)    if(!this.table[pos]) {      this.table[pos] = new LinkedList()    }    this.table[pos].push(new ValuePair(key, value))    return true;  }  return false;}

LinkedList 类是标准的链表类，在链表篇讲过如何实现，这里直接使用

对比上篇的散列表 put 方法，你会发现差别不大，变化的部分如下：

// 变化前this.table[pos] = new ValuePair(key, value)// 变化后if(!this.table[pos]) {  this.table[pos] = new LinkedList()}this.table[pos].push(new ValuePair(key, value))

优化后的逻辑是，在存储数据时，将键值对存在一个链表里。如果有相同的 hash 值，则向已有的链表中添加一个键值对，这样就避免了覆盖。

不过这种方式也有弊端，每添加一个键值对就要创建一个链表，会增加额外的内存空间。

3.get 方法

get 方法：

get(key) {   let linkedList = this.table[this.hashCode(key)]  if(linkedList && !linkedList.isEmpty()) {    let current = linkedList.getItemAt(0);    while(current) {      if(current.value.key == key) {        return current.value.value      }      current = current.next    }  }  return undefined; }

新的 get 方法明显比之前的复杂了许多。主要逻辑是根据 key 找到一个链表，然后再遍历链表找到与参数 key 相匹配的键值对，最后返回找到的值。