title: Hash-consing in F# and weak hash tables in .net
body: <p><a href="http://en.wikipedia.org/wiki/Hash_consing" rel="noreferrer">Hash-consing</a> 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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>I have a working implementation that uses <code>System.Collections.Generic.Dictionary&lt;key, node&gt;</code> where <code>key</code> is a tuple giving a shallow summary of the node (suitable for default hashing and equality test) and <code>node</code> is the object. The only problem is that the <code>Dictionary</code> keeps strong references to the nodes !</p>
  
  <p>I could use a <code>Dictionary</code> to <code>WeakReference</code>'s but this would not free the keys pointing to dangling references.</p>
  
  <p>Some advocate using <code>System.Runtime.CompilerServices.ConditionalWeakTable</code> 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.</p>
  
  <p>One could try using <code>System.Runtime.CompilerServices.ConditionalWeakTable&lt;node, node&gt;</code> but I would need custom hashing and equality tests... and <code>ConditionalWeakTable</code> is documented <em>not</em> to use the <code>GetHashCode()</code> virtual method, instead using the default hashing function.</p>
  
  <p>Thus my question : is there some equivalent of <code>Dictionary</code> that would keep weak references to values and free the keys when the references become dangling ?</p>