Good implementation of weak dictionary in .Net

问题:

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?

回答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.

回答2:

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

Pseudo code - won't really compile:

public class WeakDictionary <TKey,TValue> : IDictionary<TKey,TValue>
{
    private IDictionary<TKey,WeakReference> _innerDictionary = new Dictionary<TKey,WeakReference>();


    public TValue Index[ TKey key ]
    {
        get{
            var reference = _innerDictionary[ key ];
            if( reference.IsAlive )
                return (TValue)reference.Target;
            throw new InvalidOperation( "Key not found." );
        }

    }

    private void Cull()
    {
        var deadKeys = new List<TKey>();
        foreach( var pair in _innerDictionary )
        {
            if( ! pair.Value.IsAlive )
                deadKeys.Add( pair.Key );
        }

        foreach( var key in deadKeys )
            _innerDictionary.Remove( key );
    }
}

回答3:

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

}

回答4:

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.

回答5:

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.

回答6:

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