java – 在O(1)中使用getKey(B)的一对一映射数据结构(A,B)?

栏目: Java · 发布时间: 5年前

内容简介:我不知道现有的类为containsKey和containsValue做了O(1),但是你可以通过扩展HashMap来实现它,这样在插入时,你可以将每个值添加到内部HashSet.重载containsValue以对值HashSet执行查找.标准HashMap有O(1)containsKey,但O(n)containsValue.同样,您可以在插入中强制执行1:1并检查现有值.请注意,如果您遇到大量冲突,HashSet查找在最坏的情况下可以达到O(n).

这个问题最初是错误的,请参阅下面的编辑.我会把它留给上下文.

我一直在考虑建立双向(即一对一)映射的智能方法.映射函数A-> B(多对一)基本上是HashMap(A,B)所做的.如果我现在想要一个与O(1)中的contains()实现一对一的数据结构,那么我可以使用 java 标准库中的某些东西吗?请注意,我现在不需要这个,这只是我最近想到的,无法提供数据结构,所以答案并不急.有类似的课吗?如果没有,您认为为什么会这样?

我所能找到的就是关于冬眠的事情,这对我没有帮助.

编辑:

我的问题是措辞不好,所以应该作出一些解释.

我的意思是“向后”映射B-> A. HashMap(A,B)在O(1)中包含(A)和包含(B),所以这甚至不是我的意思,对于混淆感到遗憾.我的意思是,是否有一个数据结构映射A<- > B在O(1)中有getValue(A)和getKey(B)?

我意识到这可以通过维护包含相同关系的两个HashMaps(A,B)和(B,A)来完成,但我觉得应该有一个数据结构处理它而不必“手动”执行.

我不知道现有的类为containsKey和containsValue做了O(1),但是你可以通过扩展HashMap来实现它,这样在插入时,你可以将每个值添加到内部HashSet.重载containsValue以对值HashSet执行查找.标准HashMap有O(1)containsKey,但O(n)containsValue.

同样,您可以在插入中强制执行1:1并检查现有值.

请注意,如果您遇到大量冲突,HashSet查找在最坏的情况下可以达到O(n).

翻译自:https://stackoverflow.com/questions/11162843/one-to-one-mapping-data-structure-a-b-with-getkeyb-in-o1


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

敏捷软件开发

敏捷软件开发

Robert C.Martin,、Micah Martin / 邓辉、孙鸣 / 人民邮电出版社 / 2010-12 / 79.00元

要想成为一名优秀的软件开发人员,需要熟练应用编程语言和开发工具,更重要的是能够领悟优美代码背后的原则和前人总结的经验——这正是本书的主题。本书凝聚了世界级软件开发大师Robert C. Martin数十年软件开发和培训经验,Java版曾荣获计算机图书最高荣誉——Jolt大奖,是广受推崇的经典著作,自出版以来一直畅销不衰。 不要被书名误导了,本书不是那种以开发过程为主题的敏捷软件开发类图书。在......一起来看看 《敏捷软件开发》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

随机密码生成器
随机密码生成器

多种字符组合密码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试