Search code examples
javatreemap

Searching in a TreeMap (Java)

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();
  }
 }
}
Solution

  • 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.