How entrySet() works internally in HashMap?

Question

I am trying to understand entrySet() function in HashMap but I am not sure how it is working and from where the values are being populated when creating new EntrySet().

public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}

Answer 1

Source

Inside HashMap there is an inner class

private final class EntrySet extends AbstractSet...

This is what is returned by the entrySet() method in HashMap.

When you call a method in the EntrySet class to examine its contents, it looks up the information in the HashMap. If you add or remove items in the EntrySet, it will affect the HashMap (and vice versa). It is essentially just another way of looking at the same container. It does not have its own copy of the Map's contents.

Answer 2

The entrySet() method is used to get a Set view of the mappings contained in this map.

So, this will return you the set representation of values stored in the Map but this is linked with Map so during iteration of Map if you change anything it will be reflected in Set.

On the other hand 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.

Checkout this example to get details on how it works.

http://www.tutorialspoint.com/java/util/hashmap_entryset.htm

Answer 3

you can think in the way that you put < key, value > into a set. It's convenient to traverse the map.

for (Map.Entry me: map.entrySet()) {
    System.out.println("key" + me.getKey() + " value" + me.getValue());
}

instead of using key to find the value in the map

Answer 4

where the values are being populated when creating new EntrySet()

The EntrySet you are looking at in HashMap.java is not a new collection, rather it is a functional wrapper backed by the HashMap itself (read the javadoc).

The operation upon the EntrySet are delegated to the HashMap itself.

Therefore, EntrySet doesn't actually hold anything. The EntrySet doesn't need to be populated.

From the source:

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

As you can see, the class isn't a collection, but rather a view of the actual Map.

Answer 5

The following is the source code of entrySet() in jdk8:

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();//get the iterator
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

First: when we use entrySet() method, it return new EntrySet(), which is an instance of EntrySet. And this class has a iterator() method, which can be used in for ...loop. And the iterator() method return an iterator(class: EntryIterator)

Second: we read the source code of final class EntryIterator:

final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

From the code, we can see it implements next() method. And it return nextNode();

Third: we read the source code of nextNode method (it is in HashIterator class):

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() { //when new EntryIterator, this will load data first.
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

According to the order of new an Object. It will use the constructor function >based on the order: Object ---> Superclass ---> the last will be itself

jsut like : new HashIterator() then new EntryIterator()

when new EntryIterator(), it will use HashIterator's constructor method before itself. We can see it will load the data of HashMap when we use HashIterator's constructor method.

And nextNode() method get the data from these data. So we can use for ... loop to get all node of HashMap Object.

Answer 6

the entryset is not need populated the values,if you call iterator()，it will call newEntryIterator(),

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
}
Iterator<Map.Entry<K,V>> newEntryIterator()   {
    return new EntryIterator();
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}
final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }