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

Question

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

我一直在考虑建立双向(即一对一)映射的智能方法.映射函数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)来完成,但我觉得应该有一个数据结构来处理它而不必"手动"执行.

Answer 1

我认为你不会比两个HashMaps做得更好.编写包装器界面非常简单:

class OneToOneMap<Key, Value> {

    public void add(Key k, Value v) {
        if (!keyToVal_.contains(k) && !valToKey_.contains(v)) {
            keyToVal_.add(k, v);
            valToKey_.add(v, k);
        }
    }

    private HashMap<K, V> keyToVal_;
    private HashMap<V, K> valToKey_;
}

我不确定这是否是有效的Java,但你明白了.

Answer 2

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

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

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