3

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

4 回答 4

6

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

映射允许人们有效地找到与键关联的值（将是Keyand ）（在本例中）。SubKeyElement

后退很慢。

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

于 2010-06-01T23:04:39.190 回答
1

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

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

此外，如果您不确定一个给定Element的只能存在于一个地方，您可能想要存储和检索 aList<Element>而不仅仅是一个Element

于 2010-06-01T23:01:36.707 回答
1

当compareTo和equals以相互兼容的方式实现时，使用TreeMap和TreeSet可以正常工作。此外，在 Map 中搜索时，仅搜索键是有效的（对于 TreeMap O(log n)）。在 Map 中搜索值时，复杂度将变为线性。

但是，在为 Element 类型实现自己的Comparator时，有一种方法可以优化内部TreeSet中的搜索。这样您就可以实现自己的 compareTo 方法，而无需更改 Element 对象本身。

于 2010-06-01T23:01:46.050 回答
0

这是一个双向 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;
    }
}
于 2015-11-04T09:41:55.240 回答