在 TreeMap 中搜索 (Java)

Question

我需要在地图的地图中进行搜索并返回该元素所属的键。 我觉得这个实现很慢，你能帮我优化一下吗？ 我需要使用 TreeSet，但不能使用 contains，因为它们使用compareTo，而 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();
  }
 }
}

Answer 1

这里的问题是键和值是向后的。

映射允许人们高效地查找与键（本例中为 Element）关联的值（即 Key 和 SubKey）。

向后走是缓慢的。

有双向地图实现，例如 Google Collections BiMap， 支持双向更快的访问，但这意味着替换 TreeMap。否则，维护两张地图，每个方向一张。

Answer 2

如果您无法使用 contains，并且您被困在使用 Map of Maps 中，那么您唯一真正的选择就是迭代，就像您正在做的那样。

或者，您可以在单独的映射中保留 Element 到 Key/SubKey 的反向映射，这将使反向查找更快。

另外，如果您不确定给定的 Element 只能存在于一个位置，您可能需要存储和检索 List 而不仅仅是 <代码>元素

Answer 3

使用 TreeMap 和 TreeSet 在 compareTo 和 equals 的实现方式是：彼此兼容。此外，当在 Map 中搜索时，只有对键的搜索才是有效的（对于 TreeMap O(log n)）。当在 Map 中搜索值时，复杂度将变为线性。

有一种方法可以优化内部 TreeSet 中的搜索 不过，在实现您自己的 Comparator< /a> 用于元素类型。这样您就可以实现自己的compareTo 方法，而无需更改Element 对象本身。

Answer 4

这是一个双向 TreeMap（或 TreeMap 上的双射）。

它将两个重载的 TreeMap 关联在一起，并将它们捆绑在一起。

每个“逆”常量字段都指向另一个 TreeMap。一个 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;
    }
}