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 回答