2

キーが一意の場合、マップは 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

値を適切に「ハッシュ」する方法を知っている場合 (正確には、2 つの異なる値が高い確率で 2 つの異なるハッシュを与えることを意味します)、2 つのハッシュ テーブルを使用できます (1 つはキーから値へ、もう 1 つは値から値へ)。鍵）

于 2013-03-01T14:33:01.477 に答える
1

ブーストにはboost::bimapがあります。これは、2 つのマッピングを行う 2 つのマップに基づいており、問題に対するより良い解決策はないと思います。

于 2013-03-01T14:31:48.937 に答える
1

ブースト Bimap は、このような要件を考慮して設計されたデータ構造です。その柔軟性は非常に高く、ルックアップの複雑さは、基になる値を格納するために使用するように指示するデータ構造によって異なります。

詳細はこちら

于 2013-03-01T14:33:43.703 に答える