我有一个类Foo，它有一个属性Id。我的目标是没有两个 Foo 实例同时具有相同的 Id。

所以我创建了一个工厂方法 CreateFoo，它使用缓存以便为相同的 Id 返回相同的实例。

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

缓存实现为字典，基于@JaredPar 的Building a WeakReference Hashtable :

class WeakDictionary<TKey, TValue> where TValue : class {
    private readonly Dictionary<TKey, WeakReference> items;
    public WeakDictionary() {
        this.items = new Dictionary<TKey, WeakReference>();
    }
    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);
        }
    }
}

问题是 WeakReferences 在其目标被垃圾回收后仍保留在字典中。这意味着需要一些策略来手动“垃圾收集”死的 WeakReferences，正如 @Pascal Cuoq 在 What happens to a WeakReference after GC of WeakReference.Target 中所解释的那样.

我的问题是:压缩弱引用字典的最佳策略是什么？

我看到的选项是:

1. 不要从字典中删除 WeakReferences。 IMO 这很糟糕，因为缓存在我的应用程序的整个生命周期中都在使用，很多死的 WeakReferences 会随着时间的推移而累积。

2. 在每个 Put 和 TryGetValue 上遍历整个字典，并移除无效的 WeakReferences。这在某种程度上违背了字典的目的，因为这两个操作都变成了O(n)。

3. 在后台线程中定期遍历整个词典。如果我不知道 CreateFoo 的使用模式，那么什么时间间隔比较合适？

4. 将每个插入的 KeyValuePair 附加到双端链表。每次调用 Put 和 TryGetValue 都会检查列表的头部。如果 WeakReference 还活着，则将该对移动到列表的末尾。如果它已死，则从列表中删除该对并从字典中删除 WeakReference。

5. 实现一个自定义哈希表，其中的细微差别在于，当桶已满时，首先会从桶中删除失效的 WeakReferences，然后再照常进行。

还有其他策略吗？

最好的策略可能是具有分摊时间复杂度的算法。是否存在这样的策略？

最佳答案

如果你可以将托管对象切换为字典的键，那么你可以使用.Net 4.0的ConditionalWeakTable(命名空间System.Runtime.CompilerServices)。

根据 Richter 先生的说法，ConditionalWeakTable 是由垃圾收集器通知对象收集的，而不是使用轮询线程。

    static ConditionalWeakTable<TabItem, TIDExec> tidByTab = new ConditionalWeakTable<TabItem, TIDExec>();

    void Window_Loaded(object sender, RoutedEventArgs e)
    {
        ...
        dataGrid.SelectionChanged += (_sender, _e) =>
        {
            var cs = dataGrid.SelectedItem as ClientSession;

            this.tabControl.Items.Clear();

            foreach (var tid in cs.GetThreadIDs())
            {
                tid.tabItem = new TabItem() { Header = ... };
                tid.tabItem.AddHandler(UIElement.MouseDownEvent,
                    new MouseButtonEventHandler((__sender, __e) =>
                    {
                        tabControl_SelectionChanged(tid.tabItem);
                    }), true);
                tidByTab.Add(tid.tabItem, tid);
                this.tabControl.Items.Add(tid.tabItem);
            }
        };
    }

    void tabControl_SelectionChanged(TabItem tabItem)
    {
        this.tabControl.SelectedItem = tabItem;
        if (tidByTab.TryGetValue(tabControl.SelectedItem as TabItem, out tidExec))
        {
            tidExec.EnsureBlocksLoaded();
            ShowStmt(tidExec.CurrentStmt);
        }
        else
            throw new Exception("huh?");
    }

这里重要的是，唯一引用 TabItem 对象的是 tabControls.Items 集合，以及 ConditionalWeakTable 的键。 ConditionalWeakTable 的键不算。因此，当我们清除 tabControl 中的所有项时，这些 TabItem 就可以被垃圾回收(因为不再有任何内容引用它们，ConditionalWeakTable 的键也不算在内)。当它们被垃圾收集时，会通知 ConditionalWeakTable 并删除具有该键值的条目。所以我庞大的 TIDExec 对象在那个时候也被垃圾收集了(没有任何引用它们，除了 ConditionalWeakTable 的值)。

关于c# - 压缩弱引用字典，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2047591/