最大大小字典的数据结构

本文关键字：数据结构 字典 | 更新日期: 2023-09-27 17:57:40

可能重复：
IDictionary是否有LRU实现？

我正在寻找一种类似字典的数据结构，但只能包含一定数量的键值对。当一个键值对被添加到一个已经满的字典中时，一个最近没有访问过的键值对就会被删除。

C#中是否已经存在类似的内容？

我记得我为一个操作系统类实现了这样的东西，数据结构用于决定RAM的哪一部分应该分页到磁盘。这是通过将参考位与每个键值对相关联来实现的，当访问该键值对时，该键值对被设置为true。当需要移除一对时，键值对将被迭代，直到找到一个引用位设置为false的键值对。迭代的每个对的参考位将被设置为false，最后一个将被移除。

如果C#中还没有这样的数据结构，那么我描述的算法是实现它的好方法吗？

最大大小字典的数据结构

看起来.Net框架中还没有任何实现，所以下面是我使用的结果

using System.Collections.Generic;
using System.Linq;
namespace MyProject.Util
{
public class LruCache<Key, Value>
{
    public delegate Value ValueCreator();
    Dictionary<Key, ValueWithReference> cache;
    //The maximum number of elements that can fit in the cache.
    int maxCacheSize;
    IEnumerator<Value> valueRemover;
    public LruCache(int maxCacheSize) {
        this.cache = new Dictionary<Key, ValueWithReference>();
        this.maxCacheSize = maxCacheSize;
        this.valueRemover = GetKeyValuePairRemover().GetEnumerator();
    }
    /// <summary>
    /// Gets the value associated with the specified key. If it doesn't exist in the cache 
    /// then it will be created with createValue() and added to the cache. 
    /// </summary>
    public Value GetAndAddValue(Key key, ValueCreator createValue) {
        if (this.cache.ContainsKey(key) == false)
        {
            while (this.cache.Count >= this.maxCacheSize) {
                this.valueRemover.MoveNext();
            }
            this.cache[key] = new ValueWithReference(createValue());
        }
        this.cache[key].recentlyUsed = true;
        return this.cache[key].value;
    }
    protected IEnumerable<Value> GetKeyValuePairRemover() { 
        while (true) {
            List<Key> keyList = this.cache.Keys.ToList();
            foreach(Key key in keyList) {
                if (this.cache[key].recentlyUsed)
                {
                    this.cache[key].recentlyUsed = false;
                }
                else {
                    Value removedValue = this.cache[key].value;
                    this.cache.Remove(key);
                    yield return removedValue;
                }
            }
        }
    }
    protected class ValueWithReference
    {
        public Value value;
        public bool recentlyUsed;
        public ValueWithReference(Value value)
        {
            this.value = value;
            this.recentlyUsed = true;
        }
    }
}
}
相关文章：