双向 O(1) 查找的数据结构。哈希表？

Question

6

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

我知道我可以通过拥有两个哈希表来实现这一点-一个用于从姓名到电话号码，另一个用于从电话号码到姓名。然后，我可以在任何方向上以O(1)的时间进行查找。然而，这似乎存储太多数据-每个姓名和每个电话号码都存储了两次。

有没有更高效地实现这一点的方法？我应该使用哪种数据结构来存储姓名和电话号码？

如果相关的话，我是在Java中编码。

谢谢！

- tree-hacker

3个回答

5

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

- Paul Bellora

记住，哈希表提供O(1)摊销。不清楚需求是最坏情况下的O(1)还是摊销。通常情况下，除非另有说明，否则应该是最坏情况下的。 - SomeWittyUsername

1

- amit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

Java没有提供开箱即用的双向哈希表。除非您愿意使用第三方库(将为您隐藏这两个哈希表)或重新实现HashMap<K,V>的大部分内容，否则依赖于两个哈希表的解决方案就是最好的选择。

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

不一定：您可以使用表示电话号码的同一对象，这样每个电话号码只有一个对象，并从两个哈希表中存储两个对它的引用。