Searching in a TreeMap (Java)

Question

I need to do a search in a map of maps and return the keys this element belong. I think this implementation is very slow, can you help me to optimize it?. I need to use TreeSet and I can't use contains because they use compareTo, and equals/compareTo pair are implemented in an incompatible way and I can't change that. (sorry my bad english)

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

The problem here is that the keys and values are backward.

Maps allow one to efficiently find a value (which would be Key and SubKey) associated with a key (Element, in this example).

Going backwards is slow.

There are bi-directional map implementations, like Google Collections BiMap, that support faster access in both directions—but that would mean replacing TreeMap. Otherwise, maintain two maps, one for each direction.

Answer 2

if you can't use contains, and you're stuck using a Map of Maps, then your only real option is to iterate, as you are doing.

alternatively, you could keep a reverse map of Element to Key/SubKey in a separate map, which would make reverse lookups faster.

also, if you're not sure that a given Element can exist in only one place, you might want to store and retrieve a List<Element> instead of just an Element

Answer 3

Using TreeMap and TreeSet work properly when compareTo and equals are implemented in such a way that they are compatible with each other. Furthermore, when searching in a Map, only the search for the key will be efficient (for a TreeMap O(log n)). When searching for a value in a Map, the complexity will become linear.

There is a way to optimize the search in the inner TreeSet though, when implementing your own Comparator for the Element type. This way you can implement your own compareTo method without changing the Element object itself.

Answer 4

Here is a bidirectional TreeMap (or Bijection over TreeMap).

It associates two overloaded TreeMaps Which are tied together.

Each one "inverse" constant field points to the other TreeMap. Any change on one TreeMap is automatically reflected on its inverse.

As a result, each value is unique.

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;
    }
}