How can I remove all items in a HashMap where key value is greater than a defined value

Question

In my Android project I have a method to partially invalidate a cache (HashMap<Integer, Boolean>).

I am currently using a HashMap for compatibility with third party code.

I found a great answer here but it requires switching to a TreeMap. The given solution is:

treeMap.tailMap(key).clear();

The TreeMap solution is much better than my effort on HashMap:

//where hashMap is a copied instance for the method
for (Integer key : hashMap.keySet()) {
    if (key > minPosition) {
        hashMap.remove(key);
    }
}

Is there a better time/complexity solution for doing this in a HashMap, similar to the TreeMap solution?

Answer 1

If you are required to use HashMap, there is no better (more efficient) solution than iterating the entry set, and removing entries one at a time. This is going to be an O(N) operation. You need to visit / test all entries in the map.

As you correctly observed you can bulk remove entries more neatly and more efficiently from a TreeMap. It will be an O(logN) operation. But the downside is that insertions and deletions are O(logN) rather than O(1).

A LinkedHashMap can help in certain use-cases, but not in this one. (It orders the entries based on the sequence of insertion, not on the values of the keys.)