Java WeakHashMap with multiple keys?

Question

I'm looking for an equivalent to the

WeakHashMap<K, V>

class, except that it maps multiple keys to a value, so it's really more like

WeakHashMap<K1, K2, V>
WeakHashMap<K1, K2, K3, V>
etc.

The way you get and set entries would be like a multi-column primary key in a database: you put items using multiple keys e.g. (K1, K2), and to get that item back out you need to provide all the same keys you used to put it in. Given these get & set semantics, the GC semantics would be: an entry would be GCed when no longer reachable, which means that any of its keys is no longer reachable.

Has anyone else needed something like this before? How would you approach such a requirement? Storing a Tuple as the key, like you could do in a non-weak HashMap, doesn't work (the Tuple gets GCed almost immediately, with nobody pointing to it).

If something like this has been made before I'd be happy to use it, but just trying to think of how I would construct such a thing out of WeakReferences and a normal hashmap and am coming up with a blank.

Answer 1

Interesting problem. I don't know of any implementations of this, but I would approach it by adapting the source for WeakHashMap. It uses a ReferenceQueue and polls it at the start of pretty much every public method, removing entries for every gc'ed referent.

Here's my rough outline of how to adapt WeakHashMap to be a multi-key weak map:

1. Define a compound key like you described and use it for the main entry set
2. Maintain an internal map from key component to the set of keys in which it participates
3. When you find a referent component on the ReferenceQueue, look up the set of keys in which it participates and remove those keys from the main entry set
4. You also need to remove each of the keys in which it participates from every other key component's set. That is, suppose you find a key component c₁ on the reference queue and it participates in keys k₁, ..., k_n. Then for each k_i, if the other key components are c₂ and c₃, you need to remove k_i from the key sets for c₂ and c₃, as well as remove the entire entry for c₁.
5. When a key set for a component is empty, you should probably also remove the key set map entry for that component. That means that you may find a component on the reference queue that has no corresponding data in the component-to-key-set map.

The fly in the ointment here is that all these internal maps must be set up in a way that will not prevent a key component from being gc'ed. That is, there must be no hard (or soft) references within this multi-key-map structure. WeakHashMap accomplishes this by making its internal Entry class (that implements Map.Entry) extend WeakReference. When a key is gc'ed, it is the Entry object, not the key itself, that is placed in the reference queue. Something like this would have to be used in the design of all the internal structures (the compound key object, the entry set, the map from key component to the set of keys, and the set of keys themselves).