3

マップのマップを検索して、この要素が属するキーを返す必要があります。この実装は非常に遅いと思いますが、最適化を手伝ってもらえますか？TreeSetを使用する必要がありますが、compareToを使用しているため、containsを使用できません。また、equals / compareToペアは互換性のない方法で実装されており、変更できません。（私の悪い英語でごめんなさい）

Map<Key, Map<SubKey, Set<Element>>> m = new TreeSet();

public String getKeys(Element element) { 
 for(Entry<Key, Map<SubKey, Set<Element>>> e : m.entrySet()) {
  mapSubKey = e.getValue();
  for(Entry<SubKey, Set<Element>> e2 : mapSubKey.entrySet()) {
   setElements = e2.getValue();
   for(Element elem : setElements)
    if(elem.equals(element)) return "Key: " + e.getKey() + " SubKey: " + e2.getKey();
  }
 }
}
4

4 に答える 4

6

ここでの問題は、キーと値が逆方向になっていることです。

マップを使用すると、キー（この例では、 ）に関連付けられた値（Keyおよび）を効率的に見つけることができます。SubKeyElement

後戻りは遅いです。

GoogleコレクションBiMapのように、両方向へのより高速なアクセスをサポートする双方向マップの実装がありますが、それはを置き換えることを意味しTreeMapます。それ以外の場合は、各方向に1つずつ、合計2つのマップを維持します。

于 2010-06-01T23:04:39.190 に答える
1

を使用できずcontains、マップのマップの使用に行き詰まっている場合、実際の唯一のオプションは、実行しているように反復することです。

Elementまたは、 toの逆引きマップをKey/SubKey別のマップに保持して、逆引き参照を高速化することもできます。

Elementまた、特定の場所が1つの場所にしか存在できないかどうかわからない場合はList<Element>、Element

于 2010-06-01T23:01:36.707 に答える
1

TreeMapとTreeSetの使用は、 compareToとequalsが相互に互換性のある方法で実装されている場合に適切に機能します。さらに、マップで検索する場合、キーの検索のみが効率的です（TreeMap O（log n）の場合）。マップで値を検索する場合、複雑さは線形になります。

ただし、要素タイプ用に独自のコンパレータを実装する場合は、内部TreeSetでの検索を最適化する方法があります。このようにして、Elementオブジェクト自体を変更せずに、独自のcompareToメソッドを実装できます。

于 2010-06-01T23:01:46.050 に答える
0

これが双方向のTreeMap（またはTreeMap上の全単射）です。

これは、互いに結び付けられている2つのオーバーロードされたTreeMapを関連付けます。

それぞれの「逆」定数フィールドは、他のTreeMapを指します。1つのTreeMapでの変更は、その逆に自動的に反映されます。

その結果、各値は一意になります。

public class BiTreeMap<K, V> extends TreeMap<K, V> {
    public final BiTreeMap<V, K> inverse;

    private BiTreeMap(BiTreeMap inverse) {
        this.inverse = inverse;
    }

    public BiTreeMap() {
        inverse = new BiTreeMap<V, K>(this);
    }

    public BiTreeMap(Map<? extends K, ? extends V> m) {
        inverse = new BiTreeMap<V, K>(this);
        putAll(m);
    }

    public BiTreeMap(Comparator<? super K> comparator) {
        super(comparator);
        inverse = new BiTreeMap<V, K>(this);
    }

    public BiTreeMap(Comparator<? super K> comparatorK, Comparator<? super V> comparatorV) {
        super(comparatorK);
        inverse = new BiTreeMap<V, K>(this, comparatorV);
    }

    private BiTreeMap(BiTreeMap<V, K> inverse, Comparator<? super K> comparatorK) {
        super(comparatorK);
        this.inverse = inverse;
    }

    @Override
    public V put(K key, V value) {
        if(key == null || value == null) {
            throw new NullPointerException();
        }
        V oldValue = super.put(key, value);
        if (oldValue != null && inverse._compareKeys(value, oldValue) != 0) {
            inverse._remove(oldValue);
        }
        K inverseOldKey = inverse._put(value, key);
        if (inverseOldKey != null && _compareKeys(key, inverseOldKey) != 0) {
            super.remove(inverseOldKey);
        }
        return oldValue;
    }

    private int _compareKeys(K k1, K k2) {
        Comparator<? super K> c = comparator();
        if (c == null) {
            Comparable<? super K> ck1 = (Comparable<? super K>) k1;
            return ck1.compareTo(k2);
        } else {
            return c.compare(k1, k2);
        }
    }

    private V _put(K key, V value) {
        return super.put(key, value);
    }

    @Override
    public V remove(Object key) {
        V value = super.remove(key);
        inverse._remove(value);
        return value;
    }

    private V _remove(Object key) {
        return super.remove(key);
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> map) {
        for (Map.Entry<? extends K, ? extends V> e : map.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            put(key, value);
        }
    }

    @Override
    public void clear() {
        super.clear();
        inverse._clear();
    }

    private void _clear() {
        super.clear();
    }

    public boolean containsValue(Object value) {
        return inverse.containsKey(value);
    }

    @Override
    public Map.Entry<K, V> pollFirstEntry() {
        Map.Entry<K, V> entry = super.pollFirstEntry();
        inverse._remove(entry.getValue());
        return entry;
    }

    @Override
    public Map.Entry<K, V> pollLastEntry() {
        Map.Entry<K, V> entry = super.pollLastEntry();
        inverse._remove(entry.getValue());
        return entry;
    }
}
于 2015-11-04T09:41:55.240 に答える