Does a HashMap use a HashSet to store its keys?

Question

I'm wondering if a HashMap uses a HashSet to store its keys. I would guess it does, because a HashMap would correspond with a HashSet, while a TreeMap would correspond with a TreeSet.

I looked at the source code for the HashMap class, and the method returns an AbstractSet that's implemented by some kind of Iterator.

Additionally...when I write

    HashMap map = new HashMap();

    if(map.keySet() instanceof HashSet){
        System.out.println("true");
    }

The above if statement never runs. Now I'm unsure

Could someone explain how the HashMap stores its keys?

Answer 1

You're actually asking two different questions:

1. Does a HashMap use a HashSet to store its keys?
2. Does HashMap.keySet() return a HashSet?

The answer to both questions is no, and for the same reason, but there's no technical reason preventing either 1. or 2. from being true.

A HashSet is actually a wrapper around a HashMap; HashSet has the following member variable:

private transient HashMap<E,Object> map;

It populates a PRESENT sentinel value as the value of the map when an object is added to the set.

Now a HashMap stores it's data in an array of Entry objects holding the Key, Value pairs:

transient Entry<K,V>[] table;

And it's keySet() method returns an instance of the inner class KeySet:

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

private final class KeySet extends AbstractSet<K> {
  // minimal Set implementation to access the keys of the map
}

Since KeySet is a private inner class, as far as you should be concerned it is simply an arbitrary Set implementation.

Like I said, there's no reason this has to be the case. You could absolutely implement a Map class that used a HashSet internally, and then have your Map return a HashSet from .keySet(). However this would be inefficient and difficult to code; the existing implementation is both more robust and more efficient than naive Map/Set implementations.

_{Code snippets taken from Oracle JDK 1.7.0_17. You can view the source of your version of Java inside the src.zip file in your Java install directory.}

Answer 2

I'm wondering if a HashMap uses a HashSet to store its keys.

That would not work too well, because a Set only keeps track of the keys. It has no way to store the associated value mapping.

The opposite (using a Map to store Set elements) is possible, though, and this approach is being used:

HashSet is implemented by using a HashMap (with a dummy value for all keys).

The set of keys returned by HashMap#keySet is implemented by a private inner class (HashMap.KeySet extends AbstractSet).

You can study the source for both class, for example on GrepCode: HashMap and HashSet.

Could someone explain how the HashMap stores its keys?

It uses an array of buckets. Each bucket has a linked list of entries. See also

• How does Java HashMap store entries internally
• Hashmap and how this works behind the scene

Answer 3

The set that is returned by the keySet is backed by the underlying map only.

As per 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. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. Blockquote

HashMap stores keys into buckets. Keys that have same hash code goes into the same bucket. When retrieving value for an key if more than one key is found in the bucket than equals method is used to find the right key and hence the right value.

Answer 4

Answer is: NO.

HashMap.keySet() is a VIEW of the keys contained in this map.

The data of the map is stored in Entry[] table of HashMap.