WeakHashMap how is the entry _actually_ found after the reference is put on the ReferenceQueue

Question

A WeakHashMap works pretty much as a WeakReference coupled with a ReferenceQueue - there is zero news about this. Here is a stripped down example of how it is supposed to work:

public class ReferenceQueuePlayground {

    public static void main(String[] args) {
        ReferenceQueue<Referent> q = new ReferenceQueue<>();

        Referent ref = new Referent();
        WeakReference<Referent> weak = new WeakReference<>(ref, q);

        ref = null;

        // wait for GC to reclaim Referent
        while (weak.get() != null) {
            System.gc();
        }

        // this might return null, because ReferenceQueue is notified asynchronously
        // but I am assuming the happy path here 
        Reference<? extends Referent> reference = q.poll();

        // this will be false
        System.out.println(reference == null);
        // this will be true
        System.out.println(reference.get() == null);
    }

    @RequiredArgsConstructor
    @Getter
    static class Referent {

    }
}

This is exactly how WeakHashMap works - it gets notified when the referent is reclaimed and the reference is put on the ReferenceQueue. At some subsequent operation, expungeStaleEntries is called, which will basically take elements from this ReferenceQueue one by one and act on them.

The problem I have: how can it "act on them" if the referent is now gone? This is a ...HASHMap after all, so in order to remove the element, it must know it's hashCode. How can you know the hashCode for something that is now gone?

Answer 1

There are two ways. The first one would be a linear search.

Since the referent is indeed gone and you can't compute the hashCode on it, you can search for the Reference with ==, across all entries in the Map. In the example posted, you could add a few lines like:

    WeakReference<Referent> weak = new WeakReference<>(ref, q);
    // <--- this
    System.out.println(weak);

    ref = null;

    while (weak.get() != null) {
        System.out.println("not yet");
        System.gc();
    }

    Reference<? extends Referent> reference = q.poll();
    // <---- and this
    System.out.println(reference);

These both will print the same thing, which makes complete sense. So in theory, a WeakHashMap could take the reference it got (which is actually an Entry) and traverse its inner array, until a match is found.

Obviously, this would be slow.

The second approach is the one that WeakHashMap actually takes. When an Entry is first created, it computes the hashCode and puts that into a local field:

/**
  * 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;
}

At this point it knows the Key, so it can compute the hashCode. When expungeStaleEntries is later called:

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

It already knows the hashCode, since it was computed before this. It does not know the Key, but there is no need for it either.

This will help to find the bucket where this Entry will be, but to actually find the specific Entry, it can only use == on the Entry itself. since Key is gone, equals is impossible, but that does not matter.