Java HashMap with ArrayList wildcards

Question

I have a HashMap where the values are ArrayLists, and I'm trying to write a function to accept generic instances of these HashMaps

HashMap<String, ArrayList<Integer>> myMap = new HashMap<String, ArrayList<Integer>>();
public static void foo(HashMap<?, ArrayList<?>> a) {}
public static void bar(HashMap<?, ? extends ArrayList<?>> a) {}

// Compilation Failure!
foo(myMap);

// This works, but why do I need ? extends ArrayList
bar(myMap)

The error message is

The method foo(HashMap<?,ArrayList<?>>) in the type Example is not applicable for the arguments (HashMap<String,ArrayList<Integer>>).

Why do I need to have a wildcard for the extends ArrayList?

I thought that by having ArrayList<?>(without the ? extends), I could restrict the function to only HashMaps with ArrayList values.

I also know that the following generic method works:

public static <K,V> void printer(HashMap<K, ArrayList<V>> list) { }

Which behaves how I thought ArrayList<?> would work. Can someone explain the subtleties here?

Answer 1

The wildcard syntax was deliberately designed to (mis)lead people to believe it matches any type. This works for simple cases

List<?> <= List<String> // OK, right is subtype of left

But remember, it only works on the 1st level, not deeper

List<List<?> <= List<List<String>>  // FAIL

This is fine

List<? extends List<?>> <= List<List<String>>

because of the new 1st level ?. If S is subtype of T, G<S> is subtype of G<? extends T>. Apply that in case ofS=List<String>, T=List<?>.

Answer 2

1. The type HashMap<?, ArrayList<?>> means about a map which maps keys of some unknown (fixed) type to lists, each of which has elements of some unknown fixed type.

2. A concrete instantiation of such a map would be, for example:

   new HashMap<String, ArrayList<?>>();
   

   This is a map in which we can add arbitrary ArrayLists as values, and for values (lists) we get out of them we don't know anything about the parameter type.

3. The type HashMap<String, ArrayList<Integer>> means a map from strings to lists of integer. This is a map in which we can only add ArrayLists of Integers as values, not arbitrary ArraysLists. Thus, it cannot be a subtype of the type 2 (since it allows less than it).

   (Type 1 is a supertype of 2, which also lets the key type unknown.)

4. The type HashMap<String, ? extends ArrayList<?>> means a map from strings to some unknown type, which is only known to be a subtype of ArrayList<?>. In such a map we can't insert anything (as value), but all values we get out of it are guaranteed to be of type ArrayList<?>, i.e. a arraylist of something unknown (which may be another something for each list). We can insert new String keys, but only with a null value.

   Both type 2 and type 3 are subtypes of type 4 (since both ArrayList<?> and ArrayList<Integer> fulfill the extends ArrayList<?> condition), but not of each other.

5. HashMap<?, ? extends ArrayList<?>> is like 4, but we don't know the key type, either. This means we can't really do anything with the map, apart from iterating it (or looking up values for keys - get() takes an Object argument, not K) and removing stuff. For the values we retrieve, we only can iterate and remove stuff, not insert or even reorder anything. (I.e. type 4 is a subtype of type 5.)

6. The method argument type HashMap<K, ArrayList<V>> with type variables <K, V> means a map from some type K to lists of some type V, where K and V are decided by the caller of the method. The type 3 obviously fits this (with <String, Integer>), thus you are allowed to call this method. You can't really put new keys into the map, since your method does not know what K is, but you could map existing keys to new values. You can use new ArrayList<V>() (and put these elements into the map as values), but you can only put existing V objects from your existing lists into these lists. Still a lot more possible than with type 5.

---

Just a side note: You should have used the more general types Map<K,V> and List<E> instead of HashMap<K,V> and ArrayList<E> for your methods, since most certainly the method will work on any type of map/list and does not care about the specific implementation. You also would use

Map<String, List<Integer>> myMap = new HashMap<String, List<Integer>>();

to declare and initialize your variable. (You can still put ArrayList<Integer> objects as values.)

Answer 3

It's very simple. HashMap<K, V> is not a subtype of HashMap<K, W> even if V is a subtype of W. (You know this already, right?) Here, V is ArrayList<Integer>, and W is ArrayList<?>. (What matters is that they are different.) Yes, ArrayList<Integer> is a subtype of ArrayList<?>, but that's what we covered earlier, i.e. it's irrelevant. However, HashMap<K, V> is a subtype of HashMap<K, ? extends W>, because of the wildcard.