What's the quickest way to remove an element from a Map by value in Java?

Question

What's the quickest way to remove an element from a Map by value in Java?

Currently I'm using:

 DomainObj valueToRemove = new DomainObj();
 String removalKey = null;

 for (Map.Entry<String, DomainObj> entry : map.entrySet()) {
  if (valueToRemove.equals(entry.getValue())) {
   removalKey = entry.getKey();
   break;
  }
 }

 if (removalKey != null) {
  map.remove(removalKey);
 }

Answer 1

Without using a Bi-directional map (commons-collections and google collections have them), you're stuck with iterating the Map

Answer 2

If you have no way to figure out the key from the DomainObj, then I don't see how you can improve on that. There's no built in method to get the key from the value, so you have to iterate through the map.

If this is something you're doing all the time, you might maintain two maps (string->DomainObj and DomainObj->Key).

Answer 3

If you don't have a reverse map, I'd go for an iterator.

DomainObj valueToRemove = new DomainObj();

for (
    Iterator<Map.Entry<String, DomainObj>> iter = map.entrySet().iterator();
    iter.hasNext();
) {
    Map.Entry<String, DomainObj> entry = iter.next();
    if (valueToRemove.equals(entry.getValue())) {
        iter.remove();
        break; // if only want to remove first match.
    }
}

Answer 4

You could always use the values collection, since any changes made to that collection will result in the change being reflected in the map. So if you were to call Map.values().remove(valueToRemove) that should work - though I'm not sure if you'll see performance better than what you have with that loop. One idea would be to extend or override the map class such that the backing collection then is always sorted by value - that would enable you to do a binary search on the value which may be faster.

Edit: This is essentially the same as Alcon's answer except I don't think his will work since the entrySet is still going to be ordered by key - in which case you can't call .remove() with the value.

This is also assuming that the value is supposed to be unique or that you would want to remove any duplicates from the Map as well.

Answer 5

i would use this

 Map x = new HashMap();
x.put(1, "value1");
x.put(2, "value2");
x.put(3, "value3");
x.put(4, "value4");
x.put(5, "value5");
x.put(6, "value6");

x.values().remove("value4");

edit: because objects are referenced by "pointer" not by value.

N

Answer 6

I don't think this will happen only once in the lifetime of your app.

So what I would do, is to delegate to another object the responsability to maintain a reference to the objects added to that map.

So the next time you need to remove it, you use that "reverse map" ...

 class MapHolder { 

     private Map<String, DomainObj> originalMap;
     private Map<DomainObj,String> reverseMap;

     public void remove( DomainObj value ) {
           if ( reverseMap.contains( value ) ) { 
                 originalMap.remove( reverseMap.get( value ) );
                 reverseMap.remove( value );
           }
     }
  }

This is much much faster than iterating.

Obviously you need to keep them synchronized. But it should not be that hard if you refector your code to have one object being responsible for the state of the map.

Remember that in OOP we have objects that have an state and behavior. If your data is passing around variables all over the place, you are creating unnecessary dependencies between objects

Yes, It will take you some time to correct the code, but the time spent correcting it, will save you a lot of headaches in the future. Think about it.

Answer 7

Like most of the other posters have said, it's generally an O(N) operation because you're going to have to look through the whole list of hashtable values regardless. @tackline has the right solution for keeping the memory usage at O(1) (I gave him an up-vote for that).

Your other option is to sacrifice memory space for the sake of speed. If your map is reasonably sized, you could store two maps in parallel.

If you have a Map then maintain a Map in parallel to it. When you insert/remove on one map, do it on the other also. Granted this is uglier because you're wasting space and you'll have to make sure the "hashCode" method of DomainObj is written properly, but your removal time drops from O(N) to O(1) because you can lookup the key/object mapping in constant time either direction.

Not generally the best solution, but if your number one concern is speed, I think this is probably as fast as you're gonna get.

==================== Addendum: This essentially what @msaeed suggested just sans the third party library.

Answer 8

We know this situation arise rarely but is extremely helpful. I'll prefer BidiMap from org.apache.commons.collections .

Answer 9

A shorter usage of iterator is to use a values() iterator.

DomainObj valueToRemove = new DomainObj();
for (Iterator<DomainObj> it = map.values().iterator(); it.hasNext();)) {
        if (valueToRemove.equals(it.next())) {
                it.remove();
                break;
        }
}

Answer 10

Here's the one-line solution:

map.values().remove(valueToRemove);

That's probably faster than defining your own iterator, since the JDK collection code has been significantly optimized.

As others have mentioned, a bimap will have faster value removes, though it requires more memory and takes longer to populate. Also, a bimap only works when the values are unique, which may or may not be the case in your code.

Answer 11

The correct and fast one-liner would actually be: while(map.values().remove(valueObject));

kind of strange that most examples above assume the value object to be unique.