包含过期项的哈希表

Question

我想实现一个 HashTable （或者可能是 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

编辑

好吧，上面的内容不会给系统增加太多的开销，但看看这个。

下面的代码有一些健康警告。

• 它不完整...请参阅底部的抛出新的 NotImplementedException()。我会尝试过一会儿再回来讨论它，因为这是一个有趣的谜题。
• 您可能想要更改过期的方式&重写了添加方法以向构造值提供不同的值
• 我只在控制台应用程序中对其进行了最低限度的测试。查看测试代码
• 它还需要围绕 TKey 和 TKey 进行一些工作。 TValue 集合，因为它们会盲目地返回整个内部字典的集合，而不进行任何过期检查......如果您不需要特别精细的过期。您可以将 system.timer 添加到类中，该类定期遍历整个集合并删除过期的条目。
• 如果您查看 BCL 词典的定义，您会发现它实现了许多其他接口，因此根据您的要求，您可能也想实现这些接口。 IDictionary、ICollection>、IEnumerable>、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();
    }
}

Answer 3

试试这个：

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

}

当然，List 可以替换为 Hashtable，并且（这会更正确）异步委托可以替换为 Timers，但我希望通用方法是明确的