У меня есть класс Foo с идентификатором свойства. Моя цель состоит в том, что нет двух экземпляров Foo с одним и тем же идентификатором одновременно.
Итак, я создал метод factory CreateFoo, который использует кеш, чтобы вернуть тот же экземпляр для одного и того же идентификатора.
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;
}
Кэш реализован в виде словаря < TKey, WeakReference > , на основе @JaredPar Построение таблиц 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 в Что происходит с WeakReference после GC WeakReference.Target.
Мой вопрос: Какая лучшая стратегия для компактного словаря слова WeakReference?
Параметры, которые я вижу, следующие:
-
Не удаляйте WeakReferences из Словаря. IMO это плохо, потому что кеш используется в течение всего срока службы моего приложения, и много мертвых WeakReferences будет накапливаться с течением времени.
-
Пройдите весь словарь на каждом Put и TryGetValue и удалите мертвые WeakReferences. Это несколько портит цель словаря, потому что обе операции становятся O (n).
-
Периодически перемещайте весь словарь в фоновом потоке. Что было бы хорошим интервалом, учитывая, что я не знаю шаблон использования CreateFoo?
-
Добавить каждый вставленный KeyValuePair в список с двойным соединением. Каждый вызов Put и TryGetValue проверяет главу списка. Если WeakReference жив, переместите пару в конец списка. Если он мертв, удалите пару из списка и WeakReference из Словаря.
-
Реализовать пользовательскую хеш-таблицу с незначительной разницей, что, когда ведро заполнено, мертвые WeakReferences сначала удаляются из ведра, прежде чем продолжить, как обычно.
Существуют ли другие стратегии?
Лучшая стратегия - это, вероятно, алгоритм с усредненной временной сложностью. Существует ли такая стратегия?