JavaScript中的哈希表数据结构

哈希表是一种以关联方式存储数据的数据结构。在哈希表中，数据以数组格式存储，每个数据值都有其唯一的索引值。如果我们知道所需数据的索引，则访问数据会非常快。

因此，它成为一种数据结构，其中插入和搜索操作非常快，而不管数据的大小如何。哈希表使用数组作为存储介质，并使用哈希技术生成要插入元素或从中定位元素的索引。

哈希

哈希是一种将一系列键值转换为数组索引范围的技术。我们将使用模运算符来获得一系列键值。考虑一个大小为 20 的哈希表的示例，以及要存储的以下项目。项目采用 (键，值) 格式。

这里我们有一个哈希函数，它接收键并为表生成索引。这些索引让我们知道值存储在哪里。现在，每当我们想要搜索与键关联的值时，我们只需要再次对键运行哈希函数，并在几乎恒定的时间内获取值。

然而，哈希函数的设计相当困难。让我们来看一个例子：

假设我们有以下哈希函数：

示例

function modBy11(key) {
   return key % 11;
}

并且我们开始对我们要存储的键值对运行它，例如：

  • (15, 20) - 哈希码：4
  • (25, 39) - 哈希码：3
  • (8, 55) - 哈希码：8
  • (26, 84) - 哈希码：4

在这里，我们看到发生了冲突，即，如果我们先存储 15，然后遇到使用此哈希函数的键 26，它将尝试在此条目中修复相同的空间。这称为冲突。为了处理这种情况，我们需要定义冲突处理机制。有一些定义明确的简单冲突解决算法。例如：

  • 线性探测：在此算法中，我们可以通过查看下一个单元格直到找到空单元格来搜索数组中的下一个空位置。在我们的示例中，由于 4 位置已占用，我们可以将其填充到 5。
  • 单独链：在此实现中：我们将哈希表中的每个位置与一个列表关联。每当发生冲突时，我们都会将键值对附加到此列表的末尾。如果链不断变长，这可能会导致更长的搜索时间。

现在我们了解了哈希表的工作原理以及如何使用冲突解决，让我们实现 HashTable 类。

我们将实现的方法

我们将在我们的实现中实现这些方法：

  • put(key, value)：将新的键值对添加到哈希表
  • get(key)：获取与键关联的值
  • remove(key)：从表中删除键值对
  • forEach()：允许迭代所有键值对
  • static join()：一个静态方法，用于将 2 个哈希表加入到一个新的哈希表中

更新于：2020年6月15日

1K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始学习
广告