title: Compacting a WeakReference Dictionary
body: <p>I've got a class <em>Foo</em> with a property <em>Id</em>. My goal is that there are no two instances of <em>Foo</em> with the same <em>Id</em> at the same time.</p>
  
  <p>So I created a factory method <em>CreateFoo</em> which uses a cache in order to return the same instance for the same <em>Id</em>.</p>
  
  <pre><code>static Foo CreateFoo(int id) {
      Foo foo;
      if (!cache.TryGetValue(id, out foo)) {
          foo = new Foo(id);
          foo.Initialize(...);
          cache.Put(id, foo);
      }
      return foo;
  }
  </code></pre>
  
  <p>The cache is implemented as a Dictionary&lt;TKey,WeakReference&gt;, based on <em>@JaredPar</em>'s <a href="http://blogs.msdn.com/jaredpar/archive/2009/03/03/building-a-weakreference-hashtable.aspx" rel="nofollow noreferrer">Building a WeakReference Hashtable</a>:</p>
  
  <pre><code>class WeakDictionary&lt;TKey, TValue&gt; where TValue : class {
      private readonly Dictionary&lt;TKey, WeakReference&gt; items;
      public WeakDictionary() {
          this.items = new Dictionary&lt;TKey, WeakReference&gt;();
      }
      public void Put(TKey key, TValue value) {
          this.items[key] = new WeakReference(value);
      }
      public bool TryGetValue(TKey key, out TValue value) {
          WeakReference weakRef;
          if (!this.items.TryGetValue(key, out weakRef)) {
              value = null;
              return false;
          } else {
              value = (TValue)weakRef.Target;
              return (value != null);
          }
      }
  }
  </code></pre>
  
  <p>The problem is that the WeakReferences remain in the dictionary after their targets have been garbage collected. This implies the need for some strategy how to manually "garbage collect" dead WeakReferences, as explained by <em>@Pascal Cuoq</em> in <a href="https://stackoverflow.com/questions/1813740">What happens to a WeakReference after GC of WeakReference.Target</a>.</p>
  
  <hr>
  
  <p>My question is: <strong>What's the best strategy to compact a WeakReference Dictionary?</strong></p>
  
  <p>The options that I see are:</p>
  
  <ol>
  <li><p>Don't remove WeakReferences from the Dictionary. IMO this is bad, because the cache is used in the full lifetime of my application, and <em>a lot</em> of dead WeakReferences will accumulate over time.</p></li>
  <li><p>Walk the entire dictionary on each <em>Put</em> and <em>TryGetValue</em>, and remove dead WeakReferences. This defeats somewhat the purpose of a dictionary because both operations become <em>O(n)</em>.</p></li>
  <li><p>Walk the entire dictionary periodically in a background thread. What would be a good interval, given that I don't know the usage pattern of <em>CreateFoo</em>?</p></li>
  <li><p>Append each inserted KeyValuePair to a double-ended linked list. Each call to <em>Put</em> and <em>TryGetValue</em> examines the head of the list. If the WeakReference is alive, move the pair to the end of the list. If it is dead, remove the pair from the list and the WeakReference from the Dictionary.</p></li>
  <li><p>Implement a custom hash table with the minor difference that, when a bucket is full, dead WeakReferences are first removed from the bucket before proceeding as usual.</p></li>
  </ol>
  
  <p>Are there other strategies?</p>
  
  <p>The best strategy is probably an algorithm with amortized time complexity. Does such a strategy exist?</p>