How does HashMap.keySet() return a keySet

Question

Recently when I looked over HashMap, I found an interesting thing about the keySet method (and then asked a question on StackOverflow).

The source code of HashMap.keySet() is shown as follows

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

As you can see, when the keySet() method first called, it just returns a KeySet object. The KeySet object is a subclass of AbstractSet with an empty constructor, and contains no element.

Source codes of KeySet and AbstractSet are shown below:

    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();
        }
    }

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
    /**
     * Sole constructor.  (For invocation by subclass constructors, typically
     * implicit.)
     */
    protected AbstractSet() {
    }

    // some other methods
}

But when you call the method like this

Collection<String> keySet = map.keySet();
System.out.println(keySet);

the method returns a set rapidly, and you can get a set of keys shown on the screen.

Not only keySet(), but also values() and entrySet() method could do similar things.

What happened here? Is there any magical thing in Java?

Yes, there is really a "magician" do some incredible things here, and his magic wand is called Iterator.

Answer

Let's start off with how you would use the method in a program. When you first call keySet, it returns a KeySet object. However, the object does contain an implicit reference to the HashMap object created it which means it's an inner class of HashMap rather than contains nothing.

Now we get an Set object, but it contains no element of the given type(that is, the generic type of HashMap's key). Then we use a println method to print the set. When println is ready to print a non-String object, it will call object.toString() method to change the object to a String object like this

    public void println(Object x) {
        String s = String.valueOf(x);
        synchronized (this) {
            print(s);
            newLine();
        }
    }

AbstractCollection uses an iterator to iterate its elements in toString method

    public String toString() {
        // iterator() method is called here
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

And now we find something familiar -- the iterator method. As we talked above, this method would return a newKeyIterator object, which also associated to the HashMap object and then used by toString method to iterate such HashMap object. Then, we can get a "set" of keys after toString method returned. Finally the "set" will be printed by println method, and we also know how that "magic wand" works.

Some more things

Someone uses an IDE(like Eclipse) to develop program might have another question: when a breakpoint is set at the Collection<String> keySet = map.keySet(); line in IDE, run the program as debug mode, and step over the line, the IDE will show that the variable values has been a collection filled with all keys of Hashmap, rather than an object only with an reference to the HashMap object, what happened here?

You might have guessed that "Someone" is me, and yep, you are right :D I knew the iterator things but was still confused with this question for a long time. The question comes from the fact that when moving the mouse to hover over the values variable, or just clicking the values variable in the Variables view, there would be a small window with all keys in the keySet variable. Nevertheless, that's actually not a question as clicking variable in the Variables view just means executing the toString method and you know what will happen next.

Conclusion

Inner classes KeySet, Values and EntrySet do not contains any explicit fields except a implicit reference to the HashMap object which created them. Every time you call keySet(), values() or entrySet() methods, they just return such "empty" objects, and do nothing until iterator method is called. That means the so-called keySet, values and entrySet are all varied with the HashMap object contemporaneously. That's why we can always get the latest mapper of the related HashMap object.

Thank @mastov and @Eran for excellent answers.

Every time I take a look at source codes of kinds of frameworks, I can always find some interesting new things. That's actually what makes programming so charming :-)