Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can HashMap.keySet() return a view of keys?

Here is the keySet() function inside java.util.HasMap class :

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

In the comment, it says this function

Returns a {@link 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.

Therefore, I expected the object of KeySet type, which this functions returns would contain a reference to the "view of keys". However when I look at the code, the KeySet class does not contain any field at all, and all of its super classes either.

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> 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.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

Could somebody please explain

  1. What does "a view of the keys" mean? What kind of data is "a view"?
  2. How can the HashMap.keySet() returns a view of the keys by using KeySet object, which doesn't contain any reference to anything at all?

To make it more clear :

Here is a code sample to print out the keyset value. Although the KeySet object holds the reference to the containing map data, how can this exactly output the key data but not other data of the map (not value data or anything else). What is the thing that tells this KeySet object to hold only MapKeys? I can't see such instruction in its code.

package com.tutorialspoint;
import java.util.*;

public class HashMapDemo {
   public static void main(String args[]) {

     // create hash map
     HashMap newmap = new HashMap();

     // populate hash map
     newmap.put(1, "tutorials");
     newmap.put(2, "point");
     newmap.put(3, "is best");

     // get keyset value from map
     Set keyset = newmap.keySet();

     // check key set values
     System.out.println("Key set values are: " + keyset);
   }    
}

Ouput :

Key set values are: [1, 2, 3]

like image 682
Bonsaisteak Avatar asked Jan 03 '23 02:01

Bonsaisteak


1 Answers

  1. A "view" is a type of object whose data is backed by a different object, but is provided in a different way. In this case, it's providing a "view" of the Map's keys as a Set. This has a number of benefits, both for users and for performance.

    Notably, since it shares its data with the backing class there's very little memory overhead - it doesn't need to copy all the keys into a whole new Set. Additionally, users don't need to worry about the view getting out of sync with the backing structure - additions and removals will be visible via the view immediately.

  2. Because KeySet is an inner class it has access to the fields of an instance of its containing class (HashMap). Notice the HashMap.this notation in your code snippet.

    • size()'s return size; is a reference to HashMap's size field
    • clear()'s HashMap.this.clear(); calls HashMap's clear() method (it needs to use HashMap.this to reference the map's clear() method rather than its own)
    • contains() delegates HashMap's containsKey() method - this doesn't require HashMap.this because KeySet doesn't have a colliding containsKey() method
    • remove() similarly delegates to HashMap's removeNode()

    If it was instead declared as final static class KeySet it would be a static nested class, which is not tied to an instance of the containing class (it's just a way of organizing related classes). In that case KeySet would need an explicit HashMap field, and the map in question would need to be passed into the constructor. Inner classes make this implicit (which is concise, but certainly sometimes confusing).

  3. What is the thing that tells this KeySet object to hold only MapKeys?

    To be clear, there is no such instruction. A KeySet instance transitively has access to all the fields and methods of the backing map. However your example (System.out.println("Key set values are: " + keyset);) is implicitly calling keyset.toString(), which is (intentionally) not implemented to return the map's values. Because KeySet extends AbstractSet (which in turn extends AbstractCollection) its .toString() relies on the KeySet's iterator() implementation, which provides an iterator over the map's keys, not its values.

like image 55
dimo414 Avatar answered Jan 08 '23 08:01

dimo414