How WeakHashMap works – Its internal implementation

In Java we have four types of references. One of them is Weak Reference which gets garbage collected once system’s garbage collector is invoked. It will be collected by garbage collector irrespective of available memory in the system unlike Soft references which get collected only if system is running out of memory.

You can read about various Java references here : Types of references in Java

WeakHashmap uses WeakReferece as it’s keys. So these keys will get collected whenever GC is invoked.

Here is an example code which uses WeakHashmap. It inserts two entries and each key is assigned to a null afterwards. After that garbage collector is called and thread goes to sleep state for 2 seconds as GC can get executed after some time and not instantly.

public class WeakHashmapExample {
	public static void main(String[] args) throws InterruptedException {
		WeakHashMap<Object, String> weakMap = new WeakHashMap<Object, String>();
		Object obj = new Object();
		weakMap.put(obj, "value");
		Object obj2 = new Object();
		weakMap.put(obj2, "value2");
		System.out.println(weakMap.size());
		obj2 = null;
		obj = null;
		System.gc();
		Thread.sleep(2000);
		System.out.println(weakMap.size());
 
	}
}

Output of above code would be : 2 0

Methods like put(), get(), delete() are very similar to the ones present in HashMap. Key difference is how WeakHashmap gets rid of stale keys which are no longer referenced by any strong reference and has been garbage collected. In the above code obj and obj2 were made null and WeakHashmap was able to remove these keys without we removing them explicitly from the map. So how is this magic happening?

The Entry class of WeakHashmap extends WeakReference

 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;
        final int hash;
        Entry<K,V> next;
 
        /**
         * Creates new entry.
         */
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
 
        @SuppressWarnings("unchecked")
        public K getKey() {
            return (K) WeakHashMap.unmaskNull(get());
        }
...........

Key is stored as a WeakReference which has a ReferenceQueue(queue). Whenever JVM collects the WeakReference key, it adds this reference to the queue. So WeakHashmap class always checks this queue and if it finds any reference, it deletes it from its own table also.

This is the code from WeakHashmap which basically keeps an eye on the queue and updates its internal table accordingly. This method is called before each operation like get,put,size etc.

 private void expungeStaleEntries() {
        for (Object x; (x = queue.poll()) != null; ) {
            synchronized (queue) {
                @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>) x;
                int i = indexFor(e.hash, table.length);
 
                Entry<K,V> prev = table[i];
                Entry<K,V> p = prev;
                while (p != null) {
                    Entry<K,V> next = p.next;
                    if (p == e) {
                        if (prev == e)
                            table[i] = next;
                        else
                            prev.next = next;
                        // Must not null out e.next;
                        // stale entries may be in use by a HashIterator
                        e.value = null; // Help GC
                        size--;
                        break;
                    }
                    prev = p;
                    p = next;
                }
            }
        }
    }

Mar Java Mit Java 🙂

Uday Ogra

Connect with me at http://facebook.com/tendulkarogra and lets have some healthy discussion :)

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *