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

Question

我被问到以下面试问题：

假设您有一个提供其普通接口的 HashSet 实现。您如何使用一个或多个 HashSet 实例来实现一个提供普通 HashTable 接口的 HashTable 以及它通常的时间限制？

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

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

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

Answer 1

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

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

希望这可以帮助！