Search code examples
javadata-structurestreemap

Efficient way to exclude a specific value from a TreeMap

I am trying to achieve the best performance for my app. At some point in the code, i want to retrieve all the values from a map except one that corresponds to a specific key.

Now, if i wanted to retrieve all the values i would use this:

map.values();

and assuming that the TreeMap class is created efficiently, the 'values()' method is just returning a refference so --> O(1).

In my case though i want to exclude the value of a specific key. This code:

Set<String> set = new ...
for (String key: map.keySet()) {
   if (!key.equals("badKey")) {
      set.add(map.get(key));
   }
}

has a complexity of N*(logN) which is much slower than the initial O(1) and this is caused by the need of removing only one value.

Is there a better way to do this?

Solution

  • You can use entrySet instead of keySet. This way it would take O(1) to find out if a given value belongs to the key you wish to exclude.

    You can call entrySet any time you need to iterate over the values, and exclude the bad key while iterating over them. This would give you the same complexity as iterating over the values() Collection would.