编写 C++ 程序在哈希表中实现开放寻址

在本文中，我们将讨论C++中哈希表中开放寻址的实现。

在实现关联数组或键值映射时，哈希表的用法至关重要。这是因为它基于哈希映射；当两个不同的键具有相同的哈希值时，就会发生冲突。遇到冲突时，开放寻址方案会搜索另一个位置，将冲突的键及其对应的值放入其中。

关键要素

• 哈希函数：给定一个键作为输入，此函数返回哈希表中应存储匹配值的索引。键应由它均匀地分布在表中。
• 冲突解决：开放寻址的过程，也称为“探测序列”搜索，在哈希表中找到一个空槽来解决冲突。为此，可以应用多种技术，包括双重哈希、二次探测和线性探测。
• 负载因子：负载因子是哈希表大小与其中包含的元素数量之比。高负载因子可能导致冲突增加和性能下降。

方法

可以通过将要哈希的{键, 值}对存储在每个数组元素中，并使用结构数组作为哈希表，以及模哈希函数来解决给定问题。线性探测和开放寻址是解决冲突情况的可行方法。

定义一个要哈希的节点，例如HashNode结构，到键值对。

• 为了存储所有键值对，使用HashNode类型的指针初始化一个数组，例如*arr[]。
• 插入 (键, 值)：将 {键, 值} 对放入哈希表。
• 设置HashNode变量（例如temp）的初始值为 {键, 值}。
• 使用哈希函数，确定可以存储键的索引。之后，将索引放入名为HashIndex的变量中。
• 为了执行线性探测，只要arr[HashIndex]不为空或存在另一个键，就使用公式 HashIndex = (HashIndex+1)%capacity 持续更新哈希索引。
• 如果arr[HashIndex]不为空，则通过将temp的地址赋给arr[HashIndex]来插入指定的节点。

查找(键)：Find(Key) 函数从哈希表中检索键的值。

• 哈希函数可用于查找键可能位于的索引。之后，索引可以存储在名为HashIndex的变量中。
• 如果键存在于arr[HashIndex]中，则返回键的值。
• 如果不是，则使用线性探测，使用公式 hash index = (HashIndex+1)%capacity 持续更新哈希索引。如果找到键，则返回该HashIndex处的值，然后返回 true。
• 它返回 -1 以指示无法找到键。如果不是，则返回键的值。

删除(键)：Delete(Key) 函数用于从哈希表中删除键。

• 使用哈希函数，我们可以找到键可能位于的索引，并将其存储在名为HashIndex的变量中。
• 如果它存在于arr[HashIndex]中，则返回true，并通过将{-1, -1}赋给arr[HashIndex]来删除键。
• 如果未达到HashIndex = (HashIndex+1)%capacity，则通过迭代更新HashIndex来执行线性探测。之后，如果找到键，则返回true，并删除该哈希索引处的键值。
• 如果找不到键，则返回 false。

示例

让我们举一个例子来说明C++中哈希表中开放寻址的实现。

输出

1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 10 20 30 40
Enter key at which element to be inserted: 1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit