在 Java 8 中是否有 O(1) 方法通过使用 V 作为 HashMap 来获取 K?我是否必须使用两个 HashMap (KV 和 VK),如果是这样,这会破坏 O(1) 的目的吗?
对于上下文,我试图找到使用值或键获取(String userName,Integer userIdentifier)的最有效方法。
最佳答案
作为一般说明 - 这里有一个隐藏的假设,即这些值也是唯一的。否则,您将无法通过值检索单个键,而是通过键列表检索,尽管即使您考虑到这一点,也不会改变答案太多。此外,对于您的 userName 和 userId 用例,这可能完全是一个没有实际意义的问题。
正如您所提到的,一个简单的 HashMap
是不够的 - 这意味着您需要迭代条目以查找具有特定键的条目,该键将是 O( n) 操作。
使用两个 HashMap
(名称到 id 和 id 到名称)是一个好方法。虽然这意味着每次添加/删除/修改用户时您必须执行两项操作而不是一次,但这不会影响数量级(因为您仍在执行恒定数量的恒定时间操作) ),并且您将保留 O(1) 插入时间。
这实际上是一种非常常见的方法,如果您可以将第三方库引入到您的项目中,那么这个概念就有相当可靠的实现,例如 Apache Commons Collections 的 DualHashBidiMap .
关于java - 使用 V 和 java hashmap 获取 K 的 O(1) 方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53203616/