具有双向O(1)查找的数据结构。 哈希表?
我正在实施一个系统,我有一个名单列表,每个人都有1个电话号码。 我需要能够取一个名字并查找电话号码,或者拿一个电话号码并查找姓名。
我知道我可以通过两个哈希表来实现这一点 – 一个从名称到电话号码,一个从电话号码到名字。 然后我可以在O(1)时间向任意方向查找。 然而,这似乎是我存储了太多数据 – 每个名称和每个电话号码都存储了两次。
有没有办法更有效地做到这一点? 我应该使用什么数据结构来存储姓名和电话号码?
如果相关,我用Java编码。
非常感谢!
Java没有提供开箱即用的双向哈希表。 除非您愿意使用第三方库(这会为您隐藏两个哈希表)或重新实现HashMap
的重要部分HashMap
,否则您依赖于两个哈希表的解决方案就一样好了。 HashMap
。
然后我可以在O(1)时间向任意方向查找。 然而,这似乎是我存储了太多数据 – 每个名称和每个电话号码都存储了两次。
不一定:您可以使用代表电话号码的相同对象,在这种情况下,电话号码将有一个对象,其中两个对象存储在两个哈希表中。
考虑使用Guava的HashBiMap
,它基本上是两个在幕后链接在一起的HashMap
。 另请参阅BiMap
界面及其相关文章 。
- 请记住,对象本身只存储一次,而不是存储在两个映射中。 您只需要双倍数量的引用 – 因此它可能不会那么糟糕。
- 您可以使用提供该function的Gauva BiMap (及其界面HashBiMap )