我正在实现一个系统，其中我有一个姓名列表，每个人都有 1 个电话号码。我需要能够输入姓名并查找电话号码，或者输入电话号码并查找姓名。
我知道我可以通过两个哈希表来做到这一点 - 一个从姓名到电话号码，另一个从电话号码到姓名。然后我可以在 O(1) 时间内向任一方向查找。然而，这似乎是我存储了太多数据 - 每个姓名和每个电话号码都存储了两次。
有什么方法可以更有效地做到这一点？我应该使用什么数据结构来存储姓名和电话号码？
如果相关的话，我正在用 Java 编码。
非常感谢!
最佳答案
Java 不提供开箱即用的双向哈希表。依赖于两个哈希表的解决方案已经很好了，除非您愿意使用第三方库(这会为您隐藏两个哈希表)或重新实现 HashMap<K,V> 的重要部分。 .
Then I can look up in either direction in O(1) time. However this seems like I am storing too much data - every name and every phone number is stored twice.
不一定:您可以使用表示电话号码的同一个对象，在这种情况下，电话号码只有一个对象，两个哈希表中存储了对它的两个引用。
关于java - 具有两种 O(1) 查找方式的数据结构。哈希表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13314905/