Hash-consing consists in keeping in memory only one copy of a given object ; that is, if two objects are semantically equal (same content) then they should be physically equal (same location in memory). The technique is usually implemented by keeping a global hash set and creating new objects only if they are not equal to an object in the hash set.
An additional requirement is that objects in the hash table should be collectable if they are not referenced by anything except the hash table; otherwise said, the hash table should contain weak references.
The issue is furthermore complicated by the need to have constant time, thus shallow, hashing and equality tests ; thus objects have a unique identifier that is incremented when a new object is added to the table.
I have a working implementation that uses System.Collections.Generic.Dictionary<key, node>
where key
is a tuple giving a shallow summary of the node (suitable for default hashing and equality test) and node
is the object. The only problem is that the Dictionary
keeps strong references to the nodes !
I could use a Dictionary
to WeakReference
's but this would not free the keys pointing to dangling references.
Some advocate using System.Runtime.CompilerServices.ConditionalWeakTable
but this class seems to do the opposite : it frees the value when the key is collected, whereas I need to free the key when the value is collected.
One could try using System.Runtime.CompilerServices.ConditionalWeakTable<node, node>
but I would need custom hashing and equality tests... and ConditionalWeakTable
is documented not to use the GetHashCode()
virtual method, instead using the default hashing function.
Thus my question : is there some equivalent of Dictionary
that would keep weak references to values and free the keys when the references become dangling ?
DependentHandle
may help: Ephemerons in .NET and C#