JavaScript 数据结构之散列表的创建(2)

前言：

在上一篇文章中，我们介绍了散列表的基本概念，用通俗的语言解析了其存储结构，并动手实现了一个基础的散列表。相信通过之前的学习，大家对散列表已经有了初步的认识。

如果对散列表的概念尚不熟悉，建议先阅读上一篇文章：JavaScript 数据结构之散列表的创建(1)。

上篇末尾我们遗留了一个关键问题：当字符串转化为散列值后，可能会出现重复。在散列表中，散列值（hash 值）通常作为存储数据的 key。如果不同的键计算出相同的散列值，直接存储新数据会覆盖已有数据，导致信息丢失。本篇我们将探讨如何处理这种散列值冲突，并实现一个更完善的散列表。

一、处理散列值冲突

在某些情况下，不同的键可能会计算出相同的散列值。例如 aab 和 baa，从字符串角度看它们是不同的值，但按照我们之前的散列函数逻辑（将每个字母的 Unicode 码累加），它们计算出的散列值是完全一样的。

我们知道在 JavaScript 对象中，如果赋值时指定的 key 已存在，新的值会覆盖原有的值。

比如这个例子：

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

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

目前处理冲突的可靠方法主要有两种：分离链接 和 线性探查。

1.分离链接

分离链接法（Separate Chaining）是指在散列表存储数据时，将 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 相匹配的键值对，最后返回找到的值。

在 while 循环中使用 return 可以直接中止当前函数的执行。

到此这篇关于 JavaScript 数据结构之散列表的创建的文章就介绍到这了，更多相关 JavaScript 散列表内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！