Good implementation of weak dictionary in .Net

Question

Where can I find good implementation of IDictionary which uses weak references inside?

Dictionary should be holding only weak references to values and eventually clean up itself of dead references.

Or should I just write it myself?

Answer 1

ConditionalWeakTable Class uses weak keys and automatically removes the key/value entry as soon as no other references to a key exist outside the table.

Answer 2

You'll need to write it yourself. It should be relatively straight forward, implementing the IDictionary<T,T> interface and then storing the actual values as WeakReferences<T>. You can then check the values on add/select using TryGetTarget to see if they're still alive.

public class WeakDictionary <TKey,TValue> : IDictionary<TKey,TValue>
    where TValue : class
{
    private readonly Dictionary<TKey,WeakReference<TValue>> innerDictionary = new Dictionary<TKey,WeakReference<TValue>>();
    
    
    public TValue Index[ TKey key ]
    {
        get
        {
            // Use .TryGetTarget instead of .IsAlive and .Target
            if (this.innerDictionary.TryGetValue(key, out WeakReference<TValue> wf) && wf.TryGetTarget(out TValue value))
            {
                return value;
            }

            return null;
        }
        
    }
    
    private void Cull()
    {
        var deadKeys = this.innerDictionary.Where(kvp => kvp.Value.IsAlive).Select(kvp => kvp.Key).ToList();

        foreach (var key in deadKeys)
        {
            _ = this.innerDictionary.TryRemove(key);
        }
    }
}

Answer 3

One problem with simply holding a dictionary of WeakReference objects is that there's no way, short of enumerating the entire dictionary, of removing from the Dictionary any WeakReference objects whose targets go out of scope.

It would be helpful if a WeakReference could include a delegate which would be invoked when the primary target went out of scope. As far as I know, there's no way to do that. If you don't mind adding another field and a little code to the objects you're storing within your "weak dictionary", I'd suggest creating what I call a "Finasposer" object, whose sole field is a MethodInvoker; when disposed, the MethodInvoker should be nulled out; the finalizer should Interlocked.Exchange() the MethodInvoker to null and--if its old value was non-null--invoke it. The object to be written in the dictionary should create a new Finasposer object, with a delegate that will cause the key to be removed from the dictionary when convenient.

Note that the neither the finalizer nor any delegate invoked thereby should never directly manipulate the dictionary, nor do anything that would require acquiring a lock. If the Finasposer holds a delegate, that delegate itself is guaranteed to be valid when Finalize executes, but the object attached to the delegate, and any objects referenced thereby, may be in unexpected states. It should be safe, however, for the Finasposer-called method to add to a linked list a reference to the object that went out of scope. The Dictionary's Add, Remove, and other methods could poll the linked list to see if any of the WeakReferences therein had died and needed to be cleaned out.

Answer 4

This will work without the performance problems of the other solutions.

(It doesn't rely on a "shrink" method being called upon every request in order to manually get rid of dead objects. And these "shrink" methods would have to loop through every item on every call. I do have a "shrink" method, but it is only called when the items would be enumerated anyway.)

The key to the problem is to use a "holder" object as a value in the ConditionalWeakTable, so that when the key gets dropped, the holder's finalizer will trigger, which removes the key from the "active list" of keys.

I tested this and it works.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace Util
{
    public class WeakDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDisposable
        where TKey : class
        where TValue : class
    {
        private readonly object locker = new object();
        //private readonly HashSet<WeakReference> weakKeySet = new HashSet<WeakReference>(new ObjectReferenceEqualityComparer<WeakReference>());
        private ConditionalWeakTable<TKey, WeakKeyHolder> keyHolderMap = new ConditionalWeakTable<TKey, WeakKeyHolder>();
        private Dictionary<WeakReference, TValue> valueMap = new Dictionary<WeakReference, TValue>(new ObjectReferenceEqualityComparer<WeakReference>());


        private class WeakKeyHolder
        {
            private WeakDictionary<TKey, TValue> outer;
            private WeakReference keyRef;

            public WeakKeyHolder(WeakDictionary<TKey, TValue> outer, TKey key)
            {
                this.outer = outer;
                this.WeakRef = new WeakReference(key);
            }

            public WeakReference WeakRef { get; private set; }

            ~WeakKeyHolder()
            {
                this.outer?.onKeyDrop(this.WeakRef);  // Nullable operator used just in case this.outer gets set to null by GC before this finalizer runs. But I haven't had this happen.
            }
        }

        private void onKeyDrop(WeakReference weakKeyRef)
        {
            lock(this.locker)
            {
                if (!this.bAlive)
                    return;

                //this.weakKeySet.Remove(weakKeyRef);
                this.valueMap.Remove(weakKeyRef);
            }
        }

        
    // The reason for this is in case (for some reason which I have never seen) the finalizer trigger doesn't work
    // There is not much performance penalty with this, since this is only called in cases when we would be enumerating the inner collections anyway.
        private void manualShrink()
        {
            var keysToRemove = this.valueMap.Keys.Where(k => !k.IsAlive).ToList();

            foreach (var key in keysToRemove)
                valueMap.Remove(key);
        }

        private Dictionary<TKey, TValue> currentDictionary
        {
            get
            {
                lock(this.locker)
                {
                    this.manualShrink();
                    return this.valueMap.ToDictionary(p => (TKey) p.Key.Target, p => p.Value);
                }
            }
        }

        public TValue this[TKey key]
        {
            get
            {
                if (this.TryGetValue(key, out var val))
                    return val;

                throw new KeyNotFoundException();
            }

            set
            {
                this.set(key, value, isUpdateOkay: true);
            }
        }

        private bool set(TKey key, TValue val, bool isUpdateOkay)
        {
            lock (this.locker)
            {
                if (this.keyHolderMap.TryGetValue(key, out var weakKeyHolder))
                {
                    if (!isUpdateOkay)
                        return false;

                    this.valueMap[weakKeyHolder.WeakRef] = val;
                    return true;
                }

                weakKeyHolder = new WeakKeyHolder(this, key);
                this.keyHolderMap.Add(key, weakKeyHolder);
                //this.weakKeySet.Add(weakKeyHolder.WeakRef);
                this.valueMap.Add(weakKeyHolder.WeakRef, val);

                return true;
            }
        }

        public ICollection<TKey> Keys
        {
            get
            {
                lock(this.locker)
                {
                    this.manualShrink();
                    return this.valueMap.Keys.Select(k => (TKey) k.Target).ToList();
                }
            }
        }

        public ICollection<TValue> Values
        {
            get
            {
                lock (this.locker)
                {
                    this.manualShrink();
                    return this.valueMap.Select(p => p.Value).ToList();
                }
            }
        }

        public int Count
        {
            get
            {
                lock (this.locker)
                {
                    this.manualShrink();
                    return this.valueMap.Count;
                }
            }
        }

        public bool IsReadOnly => false;

        public void Add(TKey key, TValue value)
        {
            if (!this.set(key, value, isUpdateOkay: false))
                throw new ArgumentException("Key already exists");
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            this.Add(item.Key, item.Value);
        }

        public void Clear()
        {
            lock(this.locker)
            {
                this.keyHolderMap = new ConditionalWeakTable<TKey, WeakKeyHolder>();
                this.valueMap.Clear();
            }
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            WeakKeyHolder weakKeyHolder = null;
            object curVal = null;

            lock (this.locker)
            {
                if (!this.keyHolderMap.TryGetValue(item.Key, out weakKeyHolder))
                    return false;

                curVal = weakKeyHolder.WeakRef.Target;
            }

            return (curVal?.Equals(item.Value) == true);
        }

        public bool ContainsKey(TKey key)
        {
            lock (this.locker)
            {
                return this.keyHolderMap.TryGetValue(key, out var weakKeyHolder);
            }
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            ((IDictionary<TKey, TValue>) this.currentDictionary).CopyTo(array, arrayIndex);
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return this.currentDictionary.GetEnumerator();
        }

        public bool Remove(TKey key)
        {
            lock (this.locker)
            {
                if (!this.keyHolderMap.TryGetValue(key, out var weakKeyHolder))
                    return false;

                this.keyHolderMap.Remove(key);
                this.valueMap.Remove(weakKeyHolder.WeakRef);

                return true;
            }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            lock (this.locker)
            {
                if (!this.keyHolderMap.TryGetValue(item.Key, out var weakKeyHolder))
                    return false;

                if (weakKeyHolder.WeakRef.Target?.Equals(item.Value) != true)
                    return false;

                this.keyHolderMap.Remove(item.Key);
                this.valueMap.Remove(weakKeyHolder.WeakRef);

                return true;
            }
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            lock (this.locker)
            {
                if (!this.keyHolderMap.TryGetValue(key, out var weakKeyHolder))
                {
                    value = default(TValue);
                    return false;
                }
                
                value = this.valueMap[weakKeyHolder.WeakRef];
                return true;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        private bool bAlive = true;

        public void Dispose()
        {
            this.Dispose(true);
        }

        protected void Dispose(bool bManual)
        {
            if (bManual)
            {
                Monitor.Enter(this.locker);

                if (!this.bAlive)
                    return;
            }
            
            try
            {
                this.keyHolderMap = null;
                this.valueMap = null;
                this.bAlive = false;
            }
            finally
            {
                if (bManual)
                    Monitor.Exit(this.locker);
            }
        }

        ~WeakDictionary()
        {
            this.Dispose(false);
        }
    }


public class ObjectReferenceEqualityComparer<T> : IEqualityComparer<T>
{
    public static ObjectReferenceEqualityComparer<T> Default = new ObjectReferenceEqualityComparer<T>();

    public bool Equals(T x, T y)
    {
        return ReferenceEquals(x, y);
    }

    public int GetHashCode(T obj)
    {
        return RuntimeHelpers.GetHashCode(obj);
    }
}

public class ObjectReferenceEqualityComparer : ObjectReferenceEqualityComparer<object>
{
}

}

Answer 5

This is my version of a concurrent weak (value) dictionary:

public class WeakConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue> where TValue : class
{
    private readonly ConcurrentDictionary<TKey, WeakReference<TValue>> _internalDictionary =
        new ConcurrentDictionary<TKey, WeakReference<TValue>>();

    public TValue this[TKey key]
    {
        get
        {
            if (_internalDictionary.TryGetValue(key, out var weakReference) &&
                weakReference.TryGetTarget(out var value))
                return value;

            return null;
        }
        set
        {
            _internalDictionary.TryAdd(key, new WeakReference<TValue>(value));
        }
    }

    public ICollection<TKey> Keys => _internalDictionary.Keys;

    public ICollection<TValue> Values => _internalDictionary.Values
        .Select(_ => _.GetTarget())
        .Where(_ => _ != null)
        .ToList();

    public int Count => _internalDictionary.Count;

    public bool IsReadOnly => false;

    public void Add(TKey key, TValue value)
    {
        Purge();
        if (!_internalDictionary.TryAdd(key, new WeakReference<TValue>(value)))
        {
            throw new InvalidOperationException("Key already existing");
        }
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        throw new NotSupportedException();
    }

    public void Clear()
    {
        _internalDictionary.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item) => _internalDictionary.TryGetValue(item.Key, out var weakReference) &&
                weakReference.GetTarget() == item.Value;

    public bool ContainsKey(TKey key) => _internalDictionary.TryGetValue(key, out var weakReference) &&
                weakReference.IsAlive();

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        Purge();
        _internalDictionary
            .Select(_ => new KeyValuePair<TKey, TValue>(_.Key, _.Value.GetTarget()))
            .Where(_ => _.Value != null)
            .ToList()
            .CopyTo(array, arrayIndex);
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        Purge();
        return _internalDictionary
            .Select(_ => new KeyValuePair<TKey, TValue>(_.Key, _.Value.GetTarget()))
            .Where(_ => _.Value != null)
            .GetEnumerator();
    }

    public bool Remove(TKey key)
    {
        return _internalDictionary.TryRemove(key, out var weakReference);
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        throw new NotSupportedException();
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        value = null;
        if (_internalDictionary.TryGetValue(key, out var weakReference))
        {
            value = weakReference.GetTarget();
        }

        return value != null;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        Purge();
        return GetEnumerator();
    }

    public void Purge()
    {
        foreach (var itemToRemove in _internalDictionary
            .Select(_ => new KeyValuePair<TKey, TValue>(_.Key, _.Value.GetTarget()))
            .Where(_ => _.Value == null))
        {
            _internalDictionary.TryRemove(itemToRemove.Key, out var weakReference);
        }
    }
}

public static class WeakReferenceExtensions
{
    public static bool IsAlive<T>([NotNull] this WeakReference<T> weakReference) where T : class =>
        weakReference.TryGetTarget(out var target);

    public static T GetTarget<T>([NotNull] this WeakReference<T> weakReference, T defaultValue = default(T)) where T : class
    {
        if (!weakReference.TryGetTarget(out T target))
            return defaultValue;

        return target;
    }
}

and a test proving that reference to value is actually discarded:

    [TestMethod]
    public void TestWeakDictionary()
    {
        var weakDict = new WeakConcurrentDictionary<string, TestItem>();

        {
            var testItem = new TestItem();
            weakDict.Add("testitem", testItem);

            Assert.AreEqual(1, weakDict.Count);
            Assert.AreSame(testItem, weakDict["testitem"]);
        }

        GC.Collect();
        Assert.IsNull(weakDict["testitem"]);
        weakDict.Purge();
        Assert.AreEqual(0, weakDict.Count);
    }

Some notes:

1. Property Keys returns all keys even of those entries whose value has been collected, but Values always returns live not-null objects.
2. this[key] CAN return null
3. You can optionally call Purge to clear entries whose values have been collected
4. Test works when compiled and executed in Release mode

Answer 6

It seems that all existing answers either:

• implement a dictionary with weak references to the keys as opposed to the values, or
• rely on an explicit "purge" operation that needs to be called from time to time in order to clean up old references

I've implemented a version that applies weak references to the dictionary values, removing the entries of garbage collected values immediately.

Repo: bhaeussermann/weak-dictionary

NuGet package: BernhardHaus.Collections.WeakDictionary

Article: Creating a weak dictionary in .NET

Implementation notes:

• The ConditionalWeakTable class holds a weak reference to its key, but we want the weak reference to be on the value. Therefore we use our dictionary's values as the keys of the ConditionalWeakTable.
• When the key gets garbage collected, ConditionalWeakTable removes the relevant entry and this causes the value to be garbage collected as well (assuming there are no other references to the value). This causes the deconstructor of the value object to be invoked. We leverage this in order to immediately remove the corresponding entry from the internal dictionary.

public class WeakDictionary<TKey, TValue> : IDictionary<TKey, TValue>
    where TValue : class
{
    private readonly Dictionary<TKey, WeakReference> internalDictionary = new Dictionary<TKey, WeakReference>();
    private readonly ConditionalWeakTable<TValue, Finalizer> conditionalWeakTable = new ConditionalWeakTable<TValue, Finalizer>();

    public TValue this[TKey key]
    {
        get => (TValue)internalDictionary[key].Target;
        set
        {
            Remove(key);
            Add(key, value);
        }
    }

    public ICollection<TKey> Keys => internalDictionary.Keys;

    public ICollection<TValue> Values => internalDictionary.Values.Select(r => (TValue)r.Target).ToArray();

    public int Count => internalDictionary.Count;

    public bool IsReadOnly => false;

    public void Add(TKey key, TValue value)
    {
        internalDictionary.Add(key, new WeakReference(value));
        var finalizer = new Finalizer(key);
        finalizer.ValueFinalized += k => Remove(k);
        conditionalWeakTable.Add(value, finalizer);
    }

    public void Add(KeyValuePair<TKey, TValue> item) => Add(item.Key, item.Value);

    // Implement the remaining IDictionary<,> methods to simply relay the method call to internalDictionary.
    // See https://github.com/bhaeussermann/weak-dictionary/blob/main/src/WeakDictionary/WeakDictionary.cs for the complete implementation.
    // ...

    private sealed class Finalizer
    {
        private readonly TKey valueKey;

        public Finalizer(TKey valueKey)
        {
            this.valueKey = valueKey;
        }

        ~Finalizer()
        {
            ValueFinalized?.Invoke(valueKey);
        }

        public event ValueFinalizedDelegate ValueFinalized;
    }

    private delegate void ValueFinalizedDelegate(TKey valueKey);
}

Here's an NUnit test that shows that an entry is removed once its value no longer has any references to it.

This has been tested on both .NET Framework and .NET Core. Note that in order to see it work with .NET Core compiler optimizations need to be switched on, and the debugger must not be attached. See this post.

[Test]
public void WeakDictionary()
{
    var v1 = new ValueType();
    var v2 = new ValueType();
    var v3 = new ValueType();

    var dictionary = new WeakDictionary<int, ValueType>
    {
        { 1, v1 },
        { 2, v2 },
        { 3, v3 }
    };

    var weakReference = new WeakReference(v2);
    v2 = null;

    // Loop forces non-referenced values to be garbage collected on .NET Core (see https://stackoverflow.com/a/68836653/359765)
    for (int i = 0; i < 1; i++)
    {
        GC.Collect();
    }

    Assert.IsFalse(weakReference.IsAlive);
    CollectionAssert.AreEquivalent(new int[] { 1, 3 }, dictionary.Keys, "Unexpected keys after garbage collection.");

    // These references to v1 and v2 prevent the compiler from adding optimizations that will cause v1 and v2 to be garbage collected.
    v1.ToString();
    v3.ToString();
}

private class ValueType { }

Answer 7

It is one thing to have WeakReferences to values, but I found that Dictionary keys can also be a source of memory leaks. Here is a bare bones implementation with WeakReference to keys:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Common.library.collections {

    /// <summary>
    /// THIS DICTIONARY WILL NOT "HANG ON" TO THE KEYS IT USES
    /// IF THE KEY IS GARBAGE COLLECTED, THE VALUE WILL BE RELEASED TOO
    /// </summary>
    public class Dictionary_usingWeakKey<K, V> {
        //MAP FROM HASH CODE TO LIST OF KEY/VALUE PAIRS
        private Dictionary<int, List<Pair>> dic = new Dictionary<int, List<Pair>>();


        public void Add(K key, V value) {
            if (value==null){
                this.Remove(key);
                return;
            }//endif

            List<Pair> list = null;
            dic.TryGetValue(key.GetHashCode(), out list);
            if (list == null) {
                list = new List<Pair>();
                dic.Add(key.GetHashCode(), list);
            }//endif

            Boolean isDirty = false;            
            foreach(Pair p in list){
                if (p.Key.Target == null) {
                    isDirty = true;
                    continue;
                }//endif
                if (p.Key.Target == (Object)key) {
                    p.Value = (Object)value;
                    if (isDirty) cleanList(list);
                    return;
                }//endif
            }//for
            if (isDirty) cleanList(list);

            Pair newP=new Pair();
            newP.Key = new WeakReference(key);
            newP.Value = value;
            list.Add(newP);
        }//method


        public bool ContainsKey(K key) {
            List<Pair> list = null;
            dic.TryGetValue(key.GetHashCode(), out list);
            if (list == null) return false;

            Boolean isDirty = false;
            foreach (Pair p in list) {
                if (p.Key.Target == null) {
                    isDirty = true;
                    continue;
                }//endif
                if (p.Key.Target == (Object)key) {
                    if (isDirty) cleanList(list);
                    return true;
                }//endif
            }//for
            if (isDirty) cleanList(list);

            return false;
        }//method



        private void cleanList(List<Pair> list) {
            var temp = (from Pair p in list where p.Key.Target != null select p);
            list.Clear();
            list.AddRange(temp);
        }//method



        public bool Remove(K key) {
            List<Pair> list = null;
            dic.TryGetValue(key.GetHashCode(), out list);
            if (list == null) return true;

            foreach (Pair p in list) {
                if (p.Key.Target == (Object)key) {
                    p.Value = null;
                    break;
                }//endif
            }//for
            cleanList(list);

            return true;
        }//method





        public V this[K key] {
            get {
                List<Pair> list = null;
                dic.TryGetValue(key.GetHashCode(), out list);
                if (list == null) return default(V);

                Boolean isDirty = false;
                foreach (Pair p in list) {
                    if (p.Key.Target == null) {
                        isDirty = true;
                        continue;
                    }//endif

                    if (p.Key.Target == (Object)key) {
                        if (isDirty) cleanList(list);
                        return (V)p.Value;
                    }//endif
                }//for
                if (isDirty) cleanList(list);

                return default(V);
            }
            set {
                this.Add(key, value);
            }
        }


        public void Add(KeyValuePair<K, V> item) {
            throw new NotImplementedException();
        }

        public void Clear() {
            dic.Clear();
        }

        public bool Contains(KeyValuePair<K, V> item) {
            throw new NotImplementedException();
        }

        public void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex) {
            throw new NotImplementedException();
        }

        public int Count {
            get {
                throw new NotImplementedException();            
                //return dic.Count();           
            }
        }

        public bool IsReadOnly {
            get { return false; }
        }

        public bool Remove(KeyValuePair<K, V> item) {
            throw new NotImplementedException();
        }



        public IEnumerator<KeyValuePair<K, V>> GetEnumerator() {
            throw new NotImplementedException();    
            //return dic.GetEnumerator();
        }


        //System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
        //    return ((System.Collections.IEnumerable)dic).GetEnumerator();
        //}





    }//class



    public class Pair{
        public WeakReference Key;
        public Object Value;
    }//method

}

Answer 8

If identity comparison cannot be used then ConditionalWeakTable is not an option.

In this case I dare to suggest our implementation WeakTable.cs, and our description in the blog WeakTable.