java - 使用 V 和 java hashmap 获取 K 的 O(1) 方法?

标签 java performance dictionary hashmap

在 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/

相关文章:

python - 循环多个值的多个生成器

java - Guice 辅助注入(inject)多个构造函数总是调用默认构造函数

java - 在 Android(或 java)中使用没有对象的 "."是什么意思?

javascript - 在多维数组中查找值的最快方法?

performance - 显示初始图像几秒钟是空白的

java - 使用字典计算文件中的正面和负面单词(Java)

swift - 在 Swift 中,如何声明键为函数的字典? (不符合协议(protocol) 'Hashable' )

java - 在抽象表模型中实现复选框

Java RegEx - 仅从网页中提取数字

mysql - SUM(val/2) 和 SUM(val)/2 哪个更好?