How WeakHashMap works under the hood

Question

I invesigate WeakHashMap ource code to have more knowledge about WeakReference

I have found that entry looks like this:

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;
        }
        ...

Thus when we create new entry we invoke super(key, queue);. It is WeakReference constructor. As far I understand after object will be collected by GC the new reference(I believe it should be reference on key) will be appeared in the queue.

Also I have noticed method which invokes on each operation:

    /**
     * Expunges stale entries from the table.
     */
    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;
                }
            }
        }
    }

Looks like we get (Entry<K,V>) from queue. I don't know how to explain this(first question). this code:

public static void main(String[] args) throws InterruptedException {
    StringBuilder AAA = new StringBuilder();
    ReferenceQueue queue = new ReferenceQueue();
    WeakReference weakRef = new WeakReference(AAA, queue);
    AAA = null;
    System.gc();
    Reference removedReference = queue.remove();
    System.out.println(removedReference.get());
}

always outputs null, because object already collected by GC

Also for me it was strange that we can have reference on Object which was already collected by GC. Actually I expect that reference should appear in queue but I could not read something meaningful because object already collected(second question).

Weller

@downvoter, I added explicitly in text things I want to clarify – Weller

have you looked at other SO questions relating ReferenceQueue? – Rattler

@Rattler I didn't see related tag – Weller

not a tag, just search for ReferenceQueue – Rattler

Answer 1

Looks like we get (Entry) from queue. I don't know how to explain this

queue.poll() gives you the reference instances you put into the queue through the reference constructor. In this case it's Entry<K,V> extends WeakReference<Object>.

Actually I expect that reference should appear in queue but I could not read something meaningful because object already collected

You get the Reference object itself which you can use to do some cleanup, either through subclassing or by associating it with additional data e.g. through an auxiliary Map. The referee you can obtain through get while it is still alive is not relevant, the Reference object itself is.

Rattler

why do I put Entry<K,V> ? – Weller

How gc understand that key related with Entry rather than just WeakReference ? – Weller

Those are new questions. I suggest reading the javadocs or studying other examples relating to ReferenceQueue on SO, there are much simpler examples than WeakHashMap – Rattler

Simpler examples is clear for me. I don't understand with inheritance – Weller

Answer 2

The queue returns the very reference object, you have created before. So with your example code, after executing

Reference removedReference = queue.remove();

the expression removedReference == weakRef would evaluate to true, as that’s the only reference object you’ve ever created. With this test, you can already conclude that the object formerly referenced by AAA has been collected, due to the identity of the reference object, so you already read “something meaningful”.

If you want to associate more information with it, a viable way is to create a subclass of WeakReference, which is exactly what WeakHashMap.Entry is about. In its constructor, it calls super(key, queue);, which is not different to your expression new WeakReference(AAA, queue), the first argument specifies the weakly referenced object.

So the garbage collector will enqueue the specialized WeakReference, i.e. Entry, object if its referent (the key) has become unreachable. At this point, the key can’t be retrieved anymore, i.e. its get() method will return null, but the method expungeStaleEntries() isn’t interested in the key anyway. It wants to remove the Entry instance from the table, allowing the garbage collector to reclaim the Entry instance itself and possibly the referenced value, if there are no other reference to it. It helps that this subclass has remembered the previously calculated hash code, so the map doesn’t need to search linearly.

Peroxy

Answer 3

When a ReferenceQueue is polled it will return a Reference object to the referent. The enqueue operation is done by Reference#enqueue which adds this to the queue. Thus, for WeakReference, since it extends Reference the return value can be cast to WeakReference.

So, in the WeakHashMap implementation since the Entry<K, V> extends WeakReference the return value for poll can be cast to Entry<K, V> as it is a subclass of WeakReference which is a subclass of Reference. In other words, the Reference#enqueue will add to queue this thus in the WeakHashMap implementation it will enqueue the instance of Entry<K, V>.

Do note that the class Entry<K, V> doesn't refer to key since it will lead to strong reference and thus GC will not finalize it. It only keeps the hash so that query for get can be executed under normal circumstances i.e. when the key is strongly referenced.

Adjustment