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


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

查看所有标签

猜你喜欢:

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

C++ How to Program (5th Edition) (How to Program)

C++ How to Program (5th Edition) (How to Program)

Harvey & Paul) Deitel & Associates / Prentice Hall / 2005-01-05 / USD 98.00

With over 250,000 sold, Harvey and Paul Deitel's C++ How to Program is the world's best-selling introduction to C++ programming. Now, this classic has been thoroughly updated! The Deitels' groundbreak......一起来看看 《C++ How to Program (5th Edition) (How to Program)》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具