6

我正在实施一个系统，其中我有一个姓名列表，每个人都有 1 个电话号码。我需要能够获取姓名并查找电话号码，或者获取电话号码并查找姓名。

我知道我可以通过拥有两个哈希表来做到这一点——一个从名字到电话号码，一个从电话号码到名字。然后我可以在 O(1) 时间内朝​​任一方向查找。然而，这似乎我存储了太多数据——每个名字和每个电话号码都存储了两次。

有没有办法更有效地做到这一点？我应该使用什么数据结构来存储姓名和电话号码？

如果相关的话，我正在用 Java 编码。

非常感谢！

4

3 回答 3

8

Java 不提供开箱即用的双向哈希表。依赖于两个哈希表的解决方案是最好的，除非您愿意使用第三方库（它会为您隐藏两个哈希表）或重新实现HashMap<K,V>.

然后我可以在 O(1) 时间内朝​​任一方向查找。然而，这似乎我存储了太多数据——每个名字和每个电话号码都存储了两次。

不一定：您可以使用表示电话号码的相同对象，在这种情况下，电话号码将只有一个对象，其中两个引用存储在两个哈希表中。

于 2012-11-09T19:48:38.637 回答
5

考虑使用 Guava's HashBiMap，它基本上HashMap是在幕后链接在一起的两个 s。另请参阅BiMap界面及其相关文章。

于 2012-11-09T19:48:14.047 回答
1
  1. 请记住，对象本身只存储一次，而不是在两个映射中。您只需要双倍的引用 - 所以它可能没那么糟糕。
  2. 您可以使用提供该功能的 Gauva BiMap（及其接口HashBiMap）
于 2012-11-09T19:48:24.727 回答