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

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

我一直在考虑建立双向(即一对一)映射的智能方法.映射函数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

原文 

https://codeday.me/bug/20190112/513995.html

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » java – 在O(1)中使用getKey(B)的一对一映射数据结构(A,B)?

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址