Why can't I refer to an interface inside of generic brackets in a variable declaration?

Question

I tried to write the following:

public class AdjacencyList<Vertex> {

    Map<Vertex, Set<Edge<Vertex>>> adj = new HashMap<Vertex, HashSet<Edge<Vertex>>>();
}

But I get the error:

Type mismatch: cannot convert from HashMap<Vertex,HashSet<Edge<Vertex>>> to Map<Vertex,Set<Edge<Vertex>>>

Eclipse wants me to change the line to:

Map<Vertex, HashSet<Edge<Vertex>>> adj = new HashMap<Vertex, HashSet<Edge<Vertex>>>();

(Note it's specifying the type of Set on the left.

I'm trying to get into the habit of specifying interfaces instead of exact types. Why is it not letting me in this case?

Answer 1

I believe that unless specifically specified, generics in Java are invariant, meaning that (to simplify), a List<string> does not inherit from List<Object>, even though String does inherit Object. Consider that a List<Object> has an add(Object o) method, which, if it was inherited by List<String>, be used to add non-Strings to the list and break the very type safety that generics are here to provide us. Similarly, a Map<Vertex,Set<...>> isn't the base class of a Map<Vertex, HashSet<...>>, even though Set is of HashSet.

Try reading this article on Covariance and Contravariance in Java, which explains this issue in general terms, and shows how to use Generic Bounds to extend the possible generic arguments of a type:

Unbounded wildcards allow assignment with any type parameter:

List<?> list = new ArrayList<Clazz>();

Bounded wildcards affect assignment like you might expect:

List<? extends Clazz> list = new ArrayList<SubClazz>();
List<? super Clazz> list2 = new ArrayList<Object>();

Answer 2

Make what you're instantiating concrete (HashMap), but keep the generic type abstract. Something like:

Map<Vertex, Set<Edge<Vertex>>> adj = new HashMap<Vertex, Set<Edge<Vertex>>>();

adj.put(new Vertex(), new HashSet<Edge<Vertex>>());

Note that this will allow other types of Set to be used as values in the Map, which may or may not be what you intend. If you only want HashSets in the Map, then Eclipse's suggestion would be the way to go.