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


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

查看所有标签

猜你喜欢:

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

Ordering Disorder

Ordering Disorder

Khoi Vinh / New Riders Press / 2010-12-03 / USD 29.99

The grid has long been an invaluable tool for creating order out of chaos for designers of all kinds—from city planners to architects to typesetters and graphic artists. In recent years, web designers......一起来看看 《Ordering Disorder》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具