HashTable with expirable items

Question

I want to implement a HashTable (or mabybe a HashSet or Dictionary) which has unique members which expire after a while. For example:

// Items expire automatically after 10 seconds (Expiration period = 10 sec)
bool result = false;
// Starting from second 0
result = MyHashSet.Add("Bob");   // second 0 => true
result = MyHashSet.Add("Alice"); // second 5 => true
result = MyHashSet.Add("Bob");   // second 8 => false (item already exist)
result = MyHashSet.Add("Bob");   // second 12 => true (Bob has expired)

How to do that in a thread-safe manner with lowest costs?

Answer 1

You could create you own Hash Table where each item contains a creation time and a timespan. In the indexer where you try to return the value return null if the lifetime of the item has expired. And remove the item. A background thread that removes items from the table will not ensure you that you will never return an expired item without this. Then you can create a thread that does this just to remove expired items altogether to minimize memory consumption if a lot of items are never acessed.

Answer 2

Have you considered using System.Web.Caching instead of having to roll your own ?

http://www.hanselman.com/blog/UsingTheASPNETCacheOutsideOfASPNET.aspx

EDIT

Well the above should not add THAT much of an overhead to the system but have a look at this.

A few health warnings on the code below.

• It's incomplete... see the throw new NotImplementedException()s at the bottom. I'll try and come back to it in a while as it's an interesting puzzle.
• You may want to cange the way expiration is done & have overrides on the Add Methods to supply different values to the constructed value
• I've only tested it the bare minimum in a console app. see test code
• It also needs a bit of work around the TKey & TValue Collections as they'll blindly return the entirety of the inner dictionary's collections without any expiration checking... if you don't need particularly granular expiration. You could add a system.timer to the class which periodically walked the entire collection and removed expired entries.
• If you look at the Definition for the BCL Dictionary you'll see it implements a hell of a lot of other interfaces to so depending on your requirements you may want to implement these as well. IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback

Test Code

TimeSpan t = new TimeSpan(0,0,5); //5 Second Expiry
ExpiringDictionary<int, string> dictionary 
    = new ExpiringDictionary<int,string>(t);

dictionary.Add(1, "Alice");
dictionary.Add(2, "Bob");
dictionary.Add(3, "Charlie");
//dictionary.Add(1, "Alice"); //<<this will throw a exception as normal... 

System.Threading.Thread.Sleep(6000);
dictionary.Add(1, "Alice"); //<< this however should work fine as 6 seconds have passed

Implementation

public class ExpiringDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private class ExpiringValueHolder<T> {
        public T Value { get; set; }
        public DateTime Expiry { get; private set; }
        public ExpiringValueHolder(T value, TimeSpan expiresAfter)
        {
            Value = value;
            Expiry = DateTime.Now.Add(expiresAfter);
        }

        public override string ToString() { return Value.ToString(); }

        public override int GetHashCode() { return Value.GetHashCode(); }
    };
    private Dictionary<TKey, ExpiringValueHolder<TValue>> innerDictionary;
    private TimeSpan expiryTimeSpan;

    private void DestoryExpiredItems(TKey key)
    {
        if (innerDictionary.ContainsKey(key))
        {
            var value = innerDictionary[key];

            if (value.Expiry < System.DateTime.Now)
            { 
                //Expired, nuke it in the background and continue
                innerDictionary.Remove(key);
            }
        }
    }

    public ExpiringDictionary(TimeSpan expiresAfter)
    {
        expiryTimeSpan = expiresAfter;
        innerDictionary = new Dictionary<TKey, ExpiringValueHolder<TValue>>();
    }

    public void Add(TKey key, TValue value)
    {
        DestoryExpiredItems(key);

        innerDictionary.Add(key, new ExpiringValueHolder<TValue>(value, expiryTimeSpan));
    }

    public bool ContainsKey(TKey key)
    {
        DestoryExpiredItems(key);

        return innerDictionary.ContainsKey(key);
    }

    public bool Remove(TKey key)
    {
        DestoryExpiredItems(key);

        return innerDictionary.Remove(key);
    }

    public ICollection<TKey> Keys
    {
        get { return innerDictionary.Keys; }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        bool returnval = false;
        DestoryExpiredItems(key);

        if (innerDictionary.ContainsKey(key))
        {
            value = innerDictionary[key].Value;
            returnval = true;
        } else { value = default(TValue);}

        return returnval;
    }

    public ICollection<TValue> Values
    {
        get { return innerDictionary.Values.Select(vals => vals.Value).ToList(); }
    }

    public TValue this[TKey key]
    {
        get
        {
            DestoryExpiredItems(key);
            return innerDictionary[key].Value;
        }
        set
        {
            DestoryExpiredItems(key);
            innerDictionary[key] = new ExpiringValueHolder<TValue>(value, expiryTimeSpan);
        }
    }

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

        innerDictionary.Add(item.Key, new ExpiringValueHolder<TValue>(item.Value, expiryTimeSpan));
    }

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

    public int Count
    {
        get { return innerDictionary.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

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

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

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

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        throw new NotImplementedException();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }
}

Answer 3

try this:

static void Main() {
    ExpirationList<string> list = new ExpirationList<string>(new List<string>());
    bool r1 = list.Add("Bob", 3000); // true
    Thread.Sleep(2000);
    bool r2 = list.Add("Bob", 3000); // false
    Thread.Sleep(2000);
    bool r3 = list.Add("Bob", 3000); // true
}

public class ExpirationList<T> {
    private List<T> _list;

    public ExpirationList(List<T> list) {
        if (list == null) throw new ArgumentException();
        _list = list;
    }

    public bool Add(T item, int lifetime) {

        lock (_list) {
            if (_list.Contains(item))
                return false;
            _list.Add(item);
        }

        new Action<int>(time => Thread.Sleep(time))
            .BeginInvoke(lifetime, new AsyncCallback(result => {
                T obj = (T)result.AsyncState;
                lock (_list) {
                    _list.Remove(obj);
                }
            }), item);

        return true;

    }

    // add other proxy code here

}

of course, List can be replaced with Hashtable and (it would be even more correct) async delegates can be replaced with Timers, but I hope that common approach is clear