data-structures - 如何使用 HashSet 实现 HashTable

Question

我被问到以下面试问题:

Suppose you have a HashSet implementation providing its ordinary interface. How can you use one or more instances of HashSet to implement a HashTable providing the ordinary HashTable interface it its ordinary time constraints?

我问了两次，但他们的意思是这样，而不是相反(使用 HashTable 实现 HashSet 非常简单，例如 Java 就是这样做的)。

我回答说不可能。这个答案似乎没有让面试官满意，所以我正在寻找一个更好的答案。即使在互联网和 Stack Overflow 上搜索，我也找不到解决方案。

我认为这是一个棘手的问题，但为了确保我在 SO 上发布了这个问题。

Answer 1

一个标准的方法是将哈希表视为键/值对的哈希集，其中键/值对的哈希码纯粹是键的哈希码，相等比较函数表示任何两个键/值对在它们的键相等时恰好相等。这样，正常的哈希集操作将以一种方式存储键/值对

• 没有存储具有相同键的两个键/值对，并且
• 在哈希表中查找键，会找到具有该键的键/值对对象，从中可以查找到值。

希望这对您有所帮助!