帶有期望項目的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 Collections的一些工作，因爲他們會盲目地返回內部字典集合的完整內容，而沒有任何到期檢查......如果您不需要特別粒度的到期。您可以將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(); 
    } 
} 

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，並且（它會更加正確）異步委託可以替換爲定時器，但是我希望通用的方法很明確