具有可过期项目的HashTable

Question

我想实现一个HashTable(或mabybe a HashSet或Dictionary),它有一个独特的成员,一段时间后会过期.例如:

// 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)

如何以最低的成本以线程安全的方式做到这一点？

Answer 1

您可以创建自己的哈希表,其中每个项目包含创建时间和时间跨度.在您尝试返回值的索引器中,如果项的生命周期已过期,则返回null.并删除该项目.从表中删除项目的后台线程将无法确保您不会在没有此项的情况下返回过期项目.然后你可以创建一个执行此操作的线程,只是为了最大程度地删除过期的项目,以便在很多项目永远不会被访问时最大限度地减少内存消耗.

Answer 2

您是否考虑过使用System.Web.Caching而不是自己滚动？

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

编辑

那么上面的内容不应该给系统增加很多开销,而是要看一下.

关于以下代码的一些健康警告.

• 它不完整......看到throw new NotImplementedException()底部的s.我会尝试在一段时间内回到它,因为它是一个有趣的谜题.
• 您可能希望完成到期的方式并覆盖添加方法以为构造的值提供不同的值
• 我只在控制台应用程序中测试了它.看测试代码
• 它还需要围绕TKey和TValue集合进行一些工作,因为他们将盲目地返回整个内部字典的集合而不进行任何过期检查......如果您不需要特别精细的过期.您可以将system.timer添加到类中,该类定期遍历整个集合并删除过期的条目.
• 如果你看一下BCL词典的定义,你会看到它实现了很多其他接口,所以根据你的要求你也可能想要实现它们. IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback

测试代码

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

履行

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