2

当键是唯一的时，Map 可以解决 O(1) 的搜索解。

但是是否存在一种结构，其中按键搜索和值搜索都采用 O(1) 顺序？

给定一个结构：

Put(key,value)
GetValueOf(Key) in O(1)
GetKeyOf(Value) in O(1)

有没有一种方法可以在不使用 2 张地图的情况下按 1 次顺序进行两次搜索？

我对 java 实现特别感兴趣。

提前致谢 ！！

4

5 回答 5

3

您注意到，当键是唯一的时，地图可以解决 O(1) 搜索解决方案。当两个键都是唯一的任何值时，您需要一个 O(1) 搜索解决方案。那么，这个数据结构就足够了：

class YourDoubleHashMap<K,V>() {
  private HashMap<K,V> keyMap;
  private HashMap<V,K> valMap;

  YourDoubleHashMap<K,V>() {
    keyMap = new HashMap<K,V>();
    valMap = new HashMap<V,K>();
  }
  public boolean put(K key,V val) {
    return keyMap.put(key,val) && valMap.put(val,key);
  }
  public V getValueOfKey(K key) {
    return keyMap.get(key);
  }
  public K getKeyOfValue(V val) {
    return valMap.get(val);
  }
}

这种时间-内存权衡方法牺牲了空间效率以换取运行时效率。

于 2013-03-02T19:06:48.000 回答
1

在 boost 中有boost::bimap。它基于执行两个映射的两个映射，我相信对于您遇到的问题没有更好的解决方案。

于 2013-03-01T14:31:48.937 回答
1

如果您知道如何正确地“散列”值（正确地，我的意思是两个不同的值会很有可能给您两个不同的散列），您可以使用 2 个散列表，（一个从键到值，另一个从值到钥匙）

于 2013-03-01T14:33:01.477 回答
1

boost bimap 是一种旨在满足此类要求的数据结构。它非常灵活，查找的复杂性取决于您告诉它用于存储基础值的数据结构。

更多细节在这里

于 2013-03-01T14:33:43.703 回答
1

Apache commons 集合有一个BidiMap. 或者去谷歌的BiMap .

于 2013-11-19T20:28:58.857 回答