HashTable с экспиральными элементами

Question

Я хочу реализовать HashTable (или mabybe 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

EDIT

Что ж, вышесказанное не должно добавить ЭТО значительную нагрузку на систему, но посмотрите на это.

Несколько предупреждений о вреде для здоровья, указанные в приведенном ниже коде.

• Это неполно ... см. throw new NotImplementedException() внизу. Я постараюсь вернуться к нему через некоторое время, потому что это интересная головоломка.
• Возможно, вы захотите изменить способ окончания срока действия и иметь переопределения в методах добавления для предоставления различных значений для созданного значения
• Я тестировал только минимум в консольном приложении. см тестовый код
• Требуется также немного поработать с коллекциями 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();
    }
}

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, но я надеюсь, что общий подход понятен