Why does Java's Map interface have a containsValue(Object) method, but no value->keys lookup?

Question

There are questions here how to get a Maps keys associated with a given value, with answers pointing to google collections (for bidirectional maps) or essentially saying "loop over it".

I just recently noticed that the Map interface has a boolean containsValue(Object value) method that "will probably require time linear in the map size for most implementations of the Map interface" and the implementation in AbstractMap indeed iterates over the entrySet().

What could be the reason for the design decision to include containsValue in Map, but no Collection<V> getKeysForValue(Object)? I can see why one would omit both, or include both, but if there is one, why not the other?

One thing that came to my mind is that it would require any Map implementation to know about a Collection implementation for the return value, but that is not actually a good reason as the Collection<V> values() method also returns a collection (an anonymous new AbstractCollection<V>() in case of AbstractMap).

Peter Lawrey · Accepted Answer · 2011-11-22 08:09:00Z

There are collections which support this, but they usually involve mainlining a reverse lookup map which is more expensive that than the relatively simple one to one mapping. As such supporting this could make all Maps more than twice as expensive on update.

Another problem is generalisation. Keys have to implement hashCode and equals (for Hash maps) or comparable (for Sorted Maps) Values don't have to implement anything which makes constructing a generalised reverse lookup either impossible, or it places extra requirements on values which are unlikely to be needed.

Well, I really like the arguments from the 2nd paragraph. But problem with need for implementing equals is also a problem with existing method containsValue(Object). It is only useful when the value class implements a proper equals method. And here we are back to the question... In my opinion the containsValue(Object) is an API accident but cannot be deleted due to compatibility reasons. What do you think?
I think containsValue has dubious value and if you really need it you can just do the following for(V value: map.values()) if (value.equals(loopup)) ... I would say its inconsistent with a minimalist design approach.

solendil · Accepted Answer · 2011-11-22 08:03:00Z

Maps can return a Collection of their keys and values since 1.2, so it was trivial to look for a value: public Object containsValue(Object v) {return values().contains(v);} This method uses natively optimisations from values() and contains() for any implementation of Map, but is likely to be slow anyway in most of them...

The getKeysForValue(Object) you're looking for is NOT trivial. It requires a specific algorithm, and this algorithm cannot be made generic enough, it must be optimised for every implmentation of Map.

It could be the reason, or it is simply that the Collection API is full of this kind of little loopholes...

Interestingly, AbstractMap.values() returns a Collection whose contains(Object v) method just returns AbstractMap.this.containsValue(v), and containsValue itself iterates over the entrySet().

Collectives™ on Stack Overflow

Why does Java's Map interface have a containsValue(Object) method, but no value->keys lookup?

2 Answers 2

2 Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Related