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

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 2

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.