101

「キーと値」ではなく、「キーとキー」形式で編成されたデータがあります。これは HashMap のようなものですが、双方向で O(1) ルックアップが必要になります。このタイプのデータ構造の名前はありますか? また、Java の標準ライブラリに含まれているようなものはありますか? (または、Apache Commons でしょうか?)

基本的に 2 つのミラー化されたマップを使用する独自のクラスを作成することもできますが、車輪を再発明したくはありません (これが既に存在しているが、適切な用語を探していない場合)。

4

7 に答える 7

110

Java API にはそのようなクラスはありません。必要な Apache Commons クラスは、BidiMapの実装の 1 つになります。

数学者として、私はこの種の構造を全単射と呼びます。

于 2009-11-03T20:47:38.523 に答える
79

Apache Commons に加えて、GuavaにはBiMapもあります。

于 2009-11-03T20:54:54.773 に答える
21

これを行うために使用した単純なクラスを次に示します (別のサード パーティの依存関係を持ちたくありませんでした)。マップで利用可能なすべての機能を提供するわけではありませんが、良いスタートです。 

    public class BidirectionalMap<KeyType, ValueType>{
        private Map<KeyType, ValueType> keyToValueMap = new ConcurrentHashMap<KeyType, ValueType>();
        private Map<ValueType, KeyType> valueToKeyMap = new ConcurrentHashMap<ValueType, KeyType>();

        synchronized public void put(KeyType key, ValueType value){
            keyToValueMap.put(key, value);
            valueToKeyMap.put(value, key);
        }

        synchronized public ValueType removeByKey(KeyType key){
            ValueType removedValue = keyToValueMap.remove(key);
            valueToKeyMap.remove(removedValue);
            return removedValue;
        }

        synchronized public KeyType removeByValue(ValueType value){
            KeyType removedKey = valueToKeyMap.remove(value);
            keyToValueMap.remove(removedKey);
            return removedKey;
        }

        public boolean containsKey(KeyType key){
            return keyToValueMap.containsKey(key);
        }

        public boolean containsValue(ValueType value){
            return keyToValueMap.containsValue(value);
        }

        public KeyType getKey(ValueType value){
            return valueToKeyMap.get(value);
        }

        public ValueType get(KeyType key){
            return keyToValueMap.get(key);
        }
    }
于 2011-10-20T09:52:20.573 に答える
10

衝突が発生しない場合は、いつでも両方の方向を同じ HashMap に追加できます :-)

于 2009-11-03T21:11:46.597 に答える
0

ここではかなり古い質問ですが、他の誰かが私のように脳ブロックを患っていて、これに出くわした場合、うまくいけばこれが役に立ちます.

私も双方向の HashMap を探していましたが、最も役立つのは最も単純な答えである場合があります。

車輪の再発明を望まず、他のライブラリやプロジェクトをプロジェクトに追加したくない場合は、並列配列 (または設計が必要な場合は ArrayLists) の単純な実装はどうでしょうか。

SomeType[] keys1 = new SomeType[NUM_PAIRS];
OtherType[] keys2 = new OtherType[NUM_PAIRS];

2 つのキーのうちの 1 つのインデックスがわかれば、もう 1 つのキーを簡単に要求できます。したがって、ルックアップ メソッドは次のようになります。

SomeType getKey1(OtherType ot);
SomeType getKey1ByIndex(int key2Idx);
OtherType getKey2(SomeType st); 
OtherType getKey2ByIndex(int key2Idx);

これは、メソッドのみがこれらの配列/ArrayLists を変更している適切なオブジェクト指向構造を使用していると仮定しています。それらを並列に保つことは非常に簡単です。並行して追加/削除する限り、配列のサイズが変更された場合に再構築する必要がないため、ArrayList の方がさらに簡単です。

于 2015-01-31T22:21:13.813 に答える