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();
    }
}