我有一个带有属性Id的类Foo。我的目标是没有两个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;
}
缓存实现为 Dictionary<TKey,WeakReference>,基于@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);
}
}
}
问题是 WeakReference 在其目标被垃圾收集后仍保留在字典中。这意味着需要一些策略来手动“垃圾收集”失效的 WeakReferences,正如@Pascal Cuoq在WeakReference.Target GC 后 WeakReference 会发生什么中所解释的那样。
我的问题是:压缩弱引用字典的最佳策略是什么?
我看到的选项是:
不要从 Dictionary 中删除 WeakReferences。IMO 这很糟糕,因为在我的应用程序的整个生命周期中都会使用缓存,并且随着时间的推移会积累很多死的 WeakReferences。
在每个Put和TryGetValue上遍历整个字典,并删除死的 WeakReferences。这在某种程度上违背了字典的目的,因为这两个操作都变成了O(n)。
在后台线程中定期遍历整个字典。鉴于我不知道CreateFoo的使用模式,什么是一个好的间隔?
将每个插入的 KeyValuePair 附加到一个双端链表。每次调用Put和TryGetValue都会检查列表的头部。如果 WeakReference 是活动的,则将该对移动到列表的末尾。如果它已死,则从列表中删除该对并从 Dictionary 中删除 WeakReference。
实现一个自定义哈希表,其细微差别是,当存储桶已满时,首先从存储桶中删除失效的 WeakReference,然后再照常进行。
还有其他策略吗?
最好的策略可能是具有摊销时间复杂度的算法。这样的策略存在吗?