设计一个哈希表

Question

我在面试中被问到这个问题，并被难住了，尽管我想出了一个答案，但我对我的解决方案感到不满意。我想看看这里的专家对这个问题有何看法。

我完全引用了面试官提出的问题。 “设计一个哈希表，您可以使用任何您想要的数据结构。我想看看您如何实现 O(1) 查找时间”。最后他说这更像是通过另一个数据结构模拟哈希表。

谁能给我提供有关这个问题的更多信息。谢谢！

PS：我提出这个问题的主要原因是想知道专业设计师如何开始解决这个问题的设计&&另一件事是，我根据提出的其他问题以某种方式通过了面试，但这个问题在我的脑海中，我想找到答案！

Answer 1

哈希表提供了一种高效（通常在常数/O(1) 时间内）插入和检索数据的方法。为此，我们使用一个非常大的数组来存储目标值和一个哈希函数，该函数通常将目标值映射到哈希值中，哈希值只不过是这个大数组中的有效索引。将要存储到唯一键（或表中的索引）的值完美散列的散列函数称为完美散列函数。但在实践中，为了存储这些没有已知方法来获取唯一哈希值（表中的索引）的值，我们通常使用哈希函数，该函数可以将每个值映射到特定索引，以便将冲突保持在最低限度。这里的冲突是指哈希表中存储的两个或多个项映射到相同的哈希值。

现在回到原来的问题，即：
“设计一个哈希表，您可以使用任何您想要的数据结构。我想看看您如何实现 O(1) 查找时间”。最后他说，这更像是通过另一个数据结构来模拟哈希表。“

如果我们可以设计一个完美的哈希函数，那么查找就可以在 O(1) 时间内完成。底层的数据结构仍然是一个数组。但这取决于要存储的值，例如，考虑字符串到英文字母，因为没有已知的哈希函数可以将每个有效的英文单词映射到唯一的 int （32 位）。 ）（或 long long int 64 位）值，因此总会存在一些冲突，为了处理冲突，我们可以使用单独的链接方法进行冲突处理，其中每个哈希表槽存储一个指向链表的指针，该链表实际上存储了所有内容。例如，考虑一个哈希函数，该函数将每个英文字母字符串视为基于 26 的数字（因为英文字母中有 26 个字符），这可以编码为：

unsigned int hash(const std::string& word)
{
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);
    unsigned int key=0;
    for(int i=0;i<word.length();++i)
    {
         key = (key<<4) + (key<<3)+(key<<2) + word[i];
         key = key% tableSize;
    }
    return key;
}

其中 tableSize 是一个适当的值。选择的素数刚好大于要存储在哈希表中的英语词典单词的总数。

以下是大小为 144554 的字典和大小 = 144563 的表的结果：

[映射到同一单元格的项目 -->哈希表中此类槽的数量] =======>

[ 0  -->   53278 ]
[1 --> 52962 ]
[2 --> 26833 ]
[3 --> 8653  ]
[4 --> 2313 ]
[5 --> 437 ]
[6  --> 78 ]
[7  -->  9 ]

在这种情况下，要搜索已映射到仅包含一项的单元格的项，查找时间复杂度为 O(1)，但如果它映射到包含超过 1 个项的单元格，则我们必须迭代此链接列表可能包含 2 到 7 个节点，然后我们就能找到该元素。所以在这种情况下它不是恒定的。

因此，是否可以在 O(1) 约束下执行查找，仅取决于完美哈希函数的可用性。否则，它不会完全是 O(1)，但非常接近它。

Answer 2

考虑宇宙U（例如，所有可能的IP地址、或所有可能的名称、或所有可能的移动电话号码、或所有可能的棋盘配置）。您可能已经注意到宇宙 U 非常大。

集合S的大小是合理的S⊆U。所以，这个集合S的大小是合理的，就像你保存朋友的电话号码一样。

选择要实施的数据结构
没有数据结构，我们将无法得到好的解决方案。我们可以使用数组来快速插入、删除和查找，但是它会占用大量空间，因为宇宙的大小非常大。另外，你的朋友名字应该是整数，并且空间需求与宇宙成正比。

另一方面，我们可以使用链表。这只会占用与对象（即集合 S）一样多的空间，但 3 个操作不会是 O(1)。为了解决这个问题，我们可以同时使用两者。

因此，解决方案是利用两全其美的方法，即数组的快速查找和链接列表等小型存储。

但是，这些现实世界的实体需要通过哈希函数转换为整数，以便它们可以用作数组索引。所以，假设你想保存你朋友的名字 alice，只需将他的名字转换为整数

插入爱丽丝：
<代码>
int k = hashFunc(alice);
arr[k] = Alice //这需要 O(1) 时间

查找 alice：
<代码>
int k = hashFunc(alice);
字符串名称 = arr[k] ;
print name;//打印 alice

当然事情没那么简单，但这就是我现在可以解释的。有不清楚的地方请告诉我。谢谢。有关哈希表的更多信息，请参阅此处

Answer 3

如果我处于你的立场，我应该做以下事情：

• 讨论哈希表到底是什么以及应该在什么情况下使用它。
• 从消费者的角度讨论其中一种实现（例如它的 .net 框架实现）。
• 与面试官讨论“哈希表内部如何运作”。这非常重要。只有了解哈希表的工作原理，您才能设计它。
• 破解问题：a.数据结构的选择b.哈希函数的选择
• 使用TDD（测试驱动开发）来设计和实现HashTable类。仅实现您要求的功能。

Answer 4

使用数组 => O(1)

因此，您可以使用哈希函数将密钥转换为数字，然后使用该数字作为数组的索引来检索该值。

Answer 5

您需要一个列表数组或“桶”来存储您的值。然后使用哈希函数来确定要查找的数组元素，最后对那里的列表元素进行线性搜索。

您可以不断查找数组位置，并对小列表中的哈希值进行线性搜索。

Answer 6

这是一个相当标准的面试问题，表明您了解有用的 Java 数据结构的基本概念，例如 HashSet 和 HashMap。

您将使用一系列列表，这些列表通常称为存储桶。您以给定容量 n 开始哈希表，这意味着您有一个包含 10 个列表的数组（全部为空）。

要将一个对象添加到你的 hastable 中，你可以调用对象 hashCode 函数，它会为你提供一个 int （一个相当大范围内的数字）。因此，您必须将 hashCode 取模到 n 才能得到它所在的存储桶。将该对象添加到该存储桶中列表的末尾。

要查找对象，您需要再次使用 hashCode 和 mod 函数来查找存储桶，然后需要使用 .equals() 迭代列表以查找正确的对象。

随着表变得越来越满，您最终将进行越来越多的线性搜索，因此您最终将需要重新散列。这意味着建立一个全新的、更大的桌子并将对象再次放入其中。

如果您想要的存储桶已满，您可以重新计算不同的存储桶位置，而不是在每个数组位置中使用列表，一种常见的方法是 二次探测。这样做的优点是不需要任何动态数据结构（例如列表），但更复杂。