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