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 个哈希表连接到一个新的哈希表中

Samual Sam

更新于： 2020年6月15日

1K+ 浏览量

启动您的 职业生涯

通过完成课程获得认证

开始学习