9

这个问题最初措辞错误，请参阅下面的编辑。我会把它留给上下文。

我一直在考虑构建双射（即一对一）映射的智能方法。映射函数 A->B（多对一）基本上是 HashMap(A,B) 所做的。如果我现在想要一个数据结构在 O(1) 中实现与 contains() 一对一的东西，那么我可以使用 java 标准库中的东西吗？请注意，我现在什么都不需要这个，这只是我最近想到的东西，无法想出一个数据结构，所以答案并不着急。有这样的课吗？如果不是，你认为这是为什么？

我只能在 SO 上找到关于休眠的东西，这对我没有帮助。

编辑：我的问题措辞不当，所以需要做出一些解释。

我的意思是“向后”映射 B->A。HashMap(A,B) 在 O(1) 中包含 contains(A) 和 contains(B)，所以这甚至不是我的意思，抱歉造成混淆。我的意思是，是否有一个数据结构映射 A<->B 在 O(1) 中具有 getValue(A) 和 getKey(B)？

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

4

5 回答 5

16

我认为你不会比两个 HashMap 做得更好。编写包装器接口非常简单：

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，但你明白了。

于 2012-06-22T19:49:52.313 回答
7

我不知道现有的类对 containsKey 和 containsValue 执行 O(1)，但您可以通过扩展 HashMap 来实现，以便在插入时将每个值添加到内部 HashSet。重载 containsValue 以查找值 HashSet。标准的 HashMap 有 O(1) containsKey，但 O(n) containsValue。

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

请注意，如果您遇到大量冲突，则 HashSet 查找在最坏的情况下可能会达到 O(n)。

于 2012-06-22T19:42:18.553 回答
4

如果您愿意使用第三方库，Guava 为此提供了一个不错的 API，如BiMap. getKey它提供了一个inverse()返回 a 的视图，而不是一个方法BiMap<V, K>。（当然，它确实提供恒定时间containsValue。）

目前，HashBiMap基本上两个HashMaps 在内部保持同步——尽管它如何保持它们相互匹配非常一致——但未来的实现可能会变得更加智能。

于 2012-06-22T20:59:35.230 回答
3

我有同样的需求，想出了这个可能有用的 BiMap。它只使用一个 hashmap 并返回一个 entry 对象，以便可以为返回值提供特定类型并允许映射到 null。

public class BiMap<T1, T2>
{
    public static class Entry<T1, T2>
    {
        public final T1 item1;
        public final T2 item2;

        public Entry( T1 item1, T2 item2 )
        {
            this.item1 = item1;
            this.item2 = item2;
        }
    }

    private final HashMap< Object, Entry<T1, T2> > mappings = new HashMap<>();
    private int loopedLinkCount;

    public void put( T1 item1, T2 item2 )
    {
        remove(item1);
        remove(item2);
        Entry<T1, T2> entry = new Entry<T1, T2>( item1, item2 );
        mappings.put( item1, entry );
        mappings.put( item2, entry );
        if( Objects.equals(item1, item2) ){
            loopedLinkCount++;
        }
    }

    /**
     * 
     * @param key 
     * @return an entry containing the key and it's one to one mapping or null if there is
     * no mapping for the key.
     */
    public Entry<T1, T2> get( Object key )
    {
        return mappings.get( key );
    }

    public Entry<T1, T2> remove( Object key )
    {
        Entry<T1, T2> entry = mappings.remove( key );
        if( entry == null ){
            return null;
        }
        if( Objects.equals( entry.item2, entry.item1 ) ){
            loopedLinkCount--;
            return entry;
        }
        return mappings.remove( Objects.equals( key, entry.item1 )  ?  entry.item2  :  entry.item1 );
    }

    public Set< Entry<T1, T2> > entrySet()
    {
        return new HashSet<>( mappings.values() );
    }

    public int size()
    {
        return ( mappings.size() + loopedLinkCount ) / 2;
    }
}
于 2015-07-26T11:34:39.603 回答
2

我最初的想法只是使用标准映射，如果您有完美的哈希函数，您可以使用 HashMap 作为一对一映射。如果我了解您在做什么，则以下内容就足够了： 

Map<String,Object> map = new HashMap<String,Object>();
于 2012-06-22T19:32:00.560 回答