views:

1452

answers:

7

What are the reasons behind the decision to not have a fully generic get method in the interface of java.util.Map<K,V>.

To clarify the question, the signature of the method is

V get(Object key)

instead of

V get(K key)

and I'm wondering why (same thing for remove, containsKey, containsValue).

+1  A: 

Backwards compatibility, I guess. Map (or HashMap) still needs to support get(Object).

Anton Gogolev
+7  A: 

The contract is expressed thus:

More formally, if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

(my emphasis)

and as such, a successful key lookup depends on the input key's implementation of the equality method. That is not necessarily dependent on the class of k.

Brian Agnew
It is also dependent on `hashCode()`. Without a proper implementation of hashCode(), a nicely implemented `equals()` is rather useless in this case.
rudolfson
I guess, in principle, this would let you use a lightweight proxy for a key, if recreating the whole key was impractical - as long as equals() and hashCode() are correctly implemented.
Bill Michell
@rudolfson: As far as I'm aware, only a HashMap is reliant upon the hash code to find the correct bucket. A TreeMap, for example, uses a binary search tree, and doesn't care about hashCode().
Rob
+12  A: 

An awesome Java coder at Google, Kevin Bourrillion, wrote about exactly this issue in a blog post a while ago (admittedly in the context of Set instead of Map). The most relevant sentence:

Uniformly, methods of the Java Collections Framework (and the Google Collections Library too) never restrict the types of their parameters except when it's necessary to prevent the collection from getting broken.

I'm not entirely sure I agree with it as a principle - .NET seems to be fine requiring the right key type, for example - but it's worth following the reasoning in the blog post. (Having mentioned .NET, it's worth explaining that part of the reason why it's not a problem in .NET is that there's the bigger problem in .NET of more limited variance...)

Jon Skeet
I'm sure Josh Bloch has written about it somewhere. An earlier attempt did use the generic parameter for the parameter, but was found to be too awkward.
Tom Hawtin - tackline
The problem that Kevin cites with Set<? extends Foo> is an artificial one, even in Java. If you pass a type parameter <F extends Foo> and then use Set<F>, the problem goes away. So I very much doubt that this is the reason why get, contains, and containsKey take Object.
Apocalisp
Apocalisp: that's not true, the situation is still the same.
Kevin Bourrillion
A: 

The reason is that containment is determined by equals and hashCode which are methods on Object and both take an Object parameter. This was an early design flaw in Java's standard libraries. Coupled with limitations in Java's type system, it forces anything that relies on equals and hashCode to take Object. If Object were defined Object<A extends Object>, then you would be able to write generic equals and hashCode, but this would have obvious negative consequences since every class in Java extends Object.

The only way to have type-safe hash tables and equality in Java is to eschew Object.equals and Object.hashCode and use a generic substitute. Functional Java comes with type classes for just this purpose: Hash<A> and Equal<A>. A wrapper for HashMap<K, V> is provided that takes Hash<K> and Equal<K> in its constructor. This class's get and contains methods therefore take a generic argument of type K.

Example:

HashMap<String, Integer> h =
  new HashMap<String, Integer>(Equal.stringEqual, Hash.stringHash);

h.add("one", 1);

h.get("one"); // All good

h.get(Integer.valueOf(1)); // Compiler error
Apocalisp
This in itself does not prevent the type of 'get' from being declared as "V get(K key)", because 'Object' is always an ancestor of K, so "key.hashCode()" would still be valid.
finnw
+23  A: 

As mentioned by people above, the reason why get(), etc. is not generic because the key of the entry you are retrieving does not have to be the same type as the object that you pass in to get(); the specification of the method only requires that they be equal. This follows from how the equals() method takes in an Object as parameter, not just the same type as the object.

Although it may be commonly true that many classes have equals() defined so that its objects can only be equal to objects of its own class, there are many places in Java where this is not the case. For example, the specification for List.equals() says that two List objects are equal if they are both Lists and have the same contents, even if they are different implementations of List. So coming back to the example in this question, according to the specification of the method is possible to have a Map<ArrayList, Something> and for me to call get() with a LinkedList as argument, and it should retrieve the key which is a list with the same contents. This would not be possible if get() were generic and restricted its argument type.

newacct
+1  A: 

I think this section of Generics Tutorial explains the situation (my emphasis):

"You need to make certain that the generic API is not unduly restrictive; it must continue to support the original contract of the API. Consider again some examples from java.util.Collection. The pre-generic API looks like:

interface Collection { 
  public boolean containsAll(Collection c);
  ...
}

A naive attempt to generify it is:

interface Collection<E> { 
  public boolean containsAll(Collection<E> c);
  ...
}

While this is certainly type safe, it doesn’t live up to the API’s original contract. The containsAll() method works with any kind of incoming collection. It will only succeed if the incoming collection really contains only instances of E, but:

  • The static type of the incoming collection might differ, perhaps because the caller doesn’t know the precise type of the collection being passed in, or perhaps because it is a Collection<S>,where S is a subtype of E.
  • It’s perfectly legitimate to call containsAll() with a collection of a different type. The routine should work, returning false."
Yardena
+3  A: 

It's an application of Postel's Law, "be conservative in what you do, be liberal in what you accept from others."

Equality checks can be performed regardless of type; the equals method is defined on the Object class and accepts any Object as a parameter. So, it makes sense for key equivalence, and operations based on key equivalence, to accept any Object type.

When a map returns key values, it conserves as much type information as it can, by using the type parameter.

erickson