Brandon Ling February 2016

Why doesn't LinkedHashMap keyset() return LinkedHashSet vs Set?

I've read in java documentation and also in this post that LinkedHashMaps' keyset() maintains order. Is the order guaranteed for the return of keys and values from a LinkedHashMap object?

My question is, if it guarantees order then why doesn't the source code of LinkedHashMap return an Object of type Set that guarantees order like LinkedHashSet?

One reason I can maybe think of is that LinkedHashSet uses a map which would increase memory allocation (depending on how AbstractSet is implemented). Is it also because it future proofs implementation of keyset?

Like this answer says in this post : Is it better to use List or Collection?

Returning a List is in line with programming to the Highest Suitable Interface.

Returning a Collection would cause ambiguity to the user, as a returned collection could be either: Set, List or Queue.

So, without reading the documentation of the keyset() isn't this ambiguous?

keyset() source code:

public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
}

private final class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
        return newKeyIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsKey(o);
    }
    public boolean remove(Object o) {
        return HashMap.this.removeEntryForKey(o) != null;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

Answers


Austin D February 2016

It returns a Set as defined by the Map interface. A Set is simply collection that contains no duplicate elements. On the other hand, a List is an ordered collection (also known as a sequence). The List interface does not specify that elements be unique.

Still, the LinkedHashMap implementation actually returns the underlying keySet which is a LinkedKeySet, and the forEach() method of the LinkedKeySet is order-preserving, i.e.:

//from the source code for the LinkedHashMap:
public Set<K> keySet() {
    Set<K> ks;
    return (ks = keySet) == null ? (keySet = new LinkedKeySet()) : ks;
}

So, in this case, the elements are both unique and ordered.


Andreas February 2016

"why doesn't the source code of LinkedHashMap return an Object of type Set that guarantees order like LinkedHashSet?"

Because LinkedHashSet is a concrete class with it's own implementation maintaining its own data, and the keyset() method must return a view of the Map, so it cannot just copy the key data to a LinkedHashSet. See javadoc:

Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.


John Bollinger February 2016

if it guarantees order then why doesn't the source code of LinkedHashMap return an Object of type Set that guarantees order like LinkedHashSet?

The declared type of the key set is drawn from that declared by Map.keySet(). LinkedHashMap was added to the standard library before covariant return types were added to the Java language. At that time, there was no alternative to using type Set.

In any event, just because the key set must have the same order as the underlying map does not mean that it must be a LinkedHashSet, and in fact it cannot be, because it must not support element additions. Its class is instead a private nested class of class LinkedHashMap. There is no public type between that class and Set that would be any more useful than Set as a return type.

Indeed, I don't think it would be easy to define one. What would be the essential characteristics that distinguish it from any other set? You cannot merely say "iteration order" without specifying what iteration order instances would have, and that order depends on the LinkedHashMap instance from which the set is obtained. In other words, iteration order is an instance characteristic, not a class characteristic. A declared type that expresses the nature of being the key set of a LinkedHashMap would therefore provide almost no information of any practical use beyond what Set provides.

Anyway, I do not find the excerpt you quoted about returning a List vs a Collection to be very persuasive. The fact is that ambiguity about an object's specific class is not inherently a problem. In the Collection vs. List example, if type Collection captures the return-type requirements of the method well, such that there is no particular reason

Post Status

Asked in February 2016
Viewed 2,259 times
Voted 5
Answered 3 times

Search




Leave an answer