9

この質問は最初は誤解されていました。以下の編集を参照してください。文脈のために残しておきます。

私は全単射 (すなわち 1 対 1) マッピングを構築するスマートな方法について考えてきました。関数 A->B (多対 1) のマッピングは、基本的に HashMap(A,B) が行うことです。O(1) で contains() を使用して 1 対 1 で何かを実装するデータ構造が必要な場合、Java 標準ライブラリに使用できるものはありますか? 気をつけてください、今のところこれは必要ありません。これは最近考えたものであり、データ構造を思い付くことができなかったので、答えは急いではありません. そんなクラスある？そうでない場合、その理由は何だと思いますか。

SOで見つけることができたのは、休止状態に関するものだけで、それは私には役に立ちませんでした。

編集：私の質問は言い回しが悪かったので、説明が必要です。

私が意味したのは、「後方」マッピング B->A です。HashMap(A,B) は、O(1) に contains(A) と contains(B) の両方を持っているため、それは私が意図したものでもありません。混乱して申し訳ありません。つまり、O(1) に getValue(A) と getKey(B) を持つデータ構造マッピング A<->B はありますか?

これは、同じ関係を保持するように維持されている 2 つの HashMap (A,B) と (B,A) を使用して実行できることを認識していますが、「手動で」行う必要なくそれを処理する 1 つのデータ構造が必要だと感じています。

4

5 に答える 5

16

2つの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 に追加することで実行できます。値 HashSet のルックアップを行うために、containsValue をオーバーロードします。標準の HashMap には O(1) の containsKey がありますが、O(n) の containsValue があります。

同様に、挿入と既存の値のチェックで 1:1 を適用できます。

大量の衝突が発生した場合、HashSet ルックアップは最悪の場合 O(n) になる可能性があることに注意してください。

于 2012-06-22T19:42:18.553 に答える
4

サードパーティのライブラリを使用する場合、Guava はこのための優れた API を として提供していBiMapます。getKeyメソッドの代わりに、inverse()を返すビューを提供しますBiMap<V, K>。(もちろん、定数時間を提供しますcontainsValue。)

現時点では、HashBiMapは基本的に内部的に 2 つHashMapの s を同期させていますが、それらを互いに一致させる方法については非常に一貫していますが、実装は将来的によりスマートになる可能性があります。

于 2012-06-22T20:59:35.230 に答える
2

私の最初の考えは、標準のマップを使用することです。完全なハッシュ関数があれば、HashMap を 1 対 1 のマッピングとして使用できます。あなたが何をしているのか理解できれば、次のことで十分です。 

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