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