C# 是否有任何 IDictionary 的 LRU 实现？

Is it there any LRU implementation of IDictionary?

提问by Antonello

I would like to implement a simple in-memory LRU cache system and I was thinking about a solution based on an IDictionary implementation which could handle an hashed LRU mechanism. Coming from java, I have experiences with LinkedHashMap, which works fine for what I need: I can't find anywhere a similar solution for .NET.

我想实现一个简单的内存中 LRU 缓存系统，我正在考虑一个基于 IDictionary 实现的解决方案，它可以处理散列 LRU 机制。来自 Java，我有使用LinkedHashMap.NET 的经验，它可以很好地满足我的需要：我找不到任何类似的 .NET 解决方案。

Has anyone developed it or has anyone had experiences like this?

有没有人开发过它或者有没有人有过这样的经历？

采纳答案by Reed Copsey

There is nothing in the base class libraries that does this.

基类库中没有任何东西可以做到这一点。

On the free side, maybe something like C5's HashedLinkedListwould work.

在免费方面，也许像 C5 的HashedLinkedList这样的东西会起作用。

If you're willing to pay, maybe check out this C# toolkit.It contains an implementation.

如果您愿意付费，也许可以查看此 C# 工具包。它包含一个实现。

回答by Orion Edwards

I don't believe so. I've certainly seen hand-rolled ones implemented several times in various unrelated projects (which more or less confirms this. If there was one, surely at least one of the projects would have used it).

我不相信。我肯定已经在各种不相关的项目中看到过多次实施的手卷（这或多或少证实了这一点。如果有的话，肯定至少有一个项目会使用它）。

It's pretty simple to implement, and usually gets done by creating a class which contains both a Dictionaryand a List.

实现起来非常简单，通常通过创建一个包含 aDictionary和 a的类来完成List。

The keys go in the list (in-order) and the items go in the dictionary.
When you Add a new item to the collection, the function checks the length of the list, pulls out the last Key (if it's too long) and then evicts the key and value from the dictionary to match. Not much more to it really

键进入列表（按顺序），项目进入字典。
当您向集合中添加新项目时，该函数会检查列表的长度，拉出最后一个键（如果它太长），然后从字典中逐出键和值以进行匹配。真的不多了

回答by JP Alioto

The Caching Application Blockof EntLib has an LRU scavenging option out of the box and can be in memory. It might be a bit heavyweight for what you want tho.

EntLib的缓存应用程序块有一个开箱即用的 LRU 清理选项，可以在内存中。对于你想要的东西，它可能有点重量级。

回答by Tony Lee

If it's an asp.net app you can use the cache class[1] but you'll be competing for space with other cached stuff, which may be what you want or may not be.

如果它是一个 asp.net 应用程序，您可以使用缓存类 [1]，但您将与其他缓存内容竞争空间，这可能是您想要的，也可能不是。

[1] http://msdn.microsoft.com/en-us/library/system.web.caching.cache.aspx

[1] http://msdn.microsoft.com/en-us/library/system.web.caching.cache.aspx

回答by Martin

This a very simple an fast implementation we developed for a web site we own.

这是我们为我们拥有的网站开发的一个非常简单的快速实现。

We try to improve the code as much as possible but keeping it thread safe. I think the code is very simple and clear, but if you need some explanation or a guide related to how to use it, don't hesitate to ask.

我们尝试尽可能地改进代码，但要保持线程安全。我认为代码非常简单明了，但是如果您需要一些解释或有关如何使用它的指南，请不要犹豫询问。

namespace LRUCache
{
    public class LRUCache<K,V>
    {
        private int capacity;
        private Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>> cacheMap = new Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>>();
        private LinkedList<LRUCacheItem<K, V>> lruList = new LinkedList<LRUCacheItem<K, V>>();

        public LRUCache(int capacity)
        {
            this.capacity = capacity;
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public V get(K key)
        {
            LinkedListNode<LRUCacheItem<K, V>> node;
            if (cacheMap.TryGetValue(key, out node))
            {
                V value = node.Value.value;
                lruList.Remove(node);
                lruList.AddLast(node);
                return value;
            }
            return default(V);
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public void add(K key, V val)
        {
            if (cacheMap.Count >= capacity)
            {
                RemoveFirst();
            }

            LRUCacheItem<K, V> cacheItem = new LRUCacheItem<K, V>(key, val);
            LinkedListNode<LRUCacheItem<K, V>> node = new LinkedListNode<LRUCacheItem<K, V>>(cacheItem);
            lruList.AddLast(node);
            cacheMap.Add(key, node);
        }

        private void RemoveFirst()
        {
            // Remove from LRUPriority
            LinkedListNode<LRUCacheItem<K,V>> node = lruList.First;
            lruList.RemoveFirst();

            // Remove from cache
            cacheMap.Remove(node.Value.key);
        }
    }

    class LRUCacheItem<K,V>
    {
        public LRUCacheItem(K k, V v)
        {
            key = k;
            value = v;
        }
        public K key;
        public V value;
    }
}

回答by Jerry Ju

I like Lawrence's implementation. Hashtable + LinkedList is a good solution. Regarding threading I would not lock this [MethodImpl(MethodImplOptions.Synchronized)], but rather using ReaderWriterLockSlim or spin lock (since contention usually fast) instead. In get function I would check if it's already the 1st item first, rather than always removing and adding. This gives you possibility to keep within a reader lock that not blocking other readers.

我喜欢劳伦斯的实现。Hashtable + LinkedList 是一个很好的解决方案。关于线程，我不会锁定这个 [MethodImpl(MethodImplOptions.Synchronized)]，而是使用 ReaderWriterLockSlim 或自旋锁（因为竞争通常很快）。在 get 函数中，我会先检查它是否已经是第一个项目，而不是总是删除和添加。这使您可以保持在不阻塞其他读者的读者锁内。

回答by mcintyre321

Found you answer while googling, also found this:

在谷歌搜索时找到你的答案，还发现了这个：

http://code.google.com/p/csharp-lru-cache/

http://code.google.com/p/csharp-lru-cache/

csharp-lru-cache: LRU cache collection class library

This is a collection class that functions as a least-recently-used cache. It implements ICollection<T>, but also exposes three other members:

• Capacity, the maximum number of items the cache can contain. Once the collection is at capacity, adding a new item to the cache will cause the least recently used item to be discarded. If the Capacity is set to 0 at construction, the cache will not automatically discard items.
• Oldest, the oldest (i.e. least recently used) item in the collection.
• DiscardingOldestItem, an event raised when the cache is about to discard its oldest item. This is an extremely simple implementation. While its Add and Remove methods are thread-safe, it shouldn't be used in heavy multithreading environments because the entire collection is locked during those methods.

csharp-lru-cache: LRU 缓存集合类库

这是一个集合类，用作最近最少使用的缓存。它实现了ICollection<T>，但也暴露了其他三个成员：

• Capacity，缓存可以包含的最大项目数。一旦集合达到容量，将新项目添加到缓存将导致最近最少使用的项目被丢弃。如果在构造时将容量设置为 0，则缓存不会自动丢弃项目。
• Oldest，集合中最旧（即最近最少使用）的项目。
• DiscardingOldestItem，当缓存即将丢弃其最旧的项目时引发的事件。这是一个极其简单的实现。虽然它的 Add 和 Remove 方法是线程安全的，但它不应该在繁重的多线程环境中使用，因为在这些方法期间整个集合都被锁定。

回答by csharptest.net

I've recently released a class called LurchTable to address the need for a C# variant of the LinkedHashMap. A brief discussion of the LurchTable can be found here.

我最近发布了一个名为 LurchTable 的类来满足对 LinkedHashMap 的 C# 变体的需求。可以在此处找到对LurchTable 的简要讨论。

Basic features:

基本功能：

• Linked Concurrent Dictionary by Insertion, Modification, or Access
• Dictionary/ConcurrentDictionary interface support
• Peek/TryDequeue/Dequeue access to 'oldest' entry
• Allows hard-limit on items enforced at insertion
• Exposes events for add, update, and remove

• 通过插入、修改或访问链接的并发字典
• Dictionary/ConcurrentDictionary 接口支持
• Peek/TryDequeue/Dequeue 访问“最旧”条目
• 允许对插入时强制执行的项目进行硬限制
• 公开事件以进行添加、更新和删除

Source Code: http://csharptest.net/browse/src/Library/Collections/LurchTable.cs

源代码：http: //csharptest.net/browse/src/Library/Collections/LurchTable.cs

GitHub: https://github.com/csharptest/CSharpTest.Net.Collections

GitHub：https: //github.com/csharptest/CSharpTest.Net.Collections

HTML Help: http://help.csharptest.net/

HTML 帮助：http: //help.csharptest.net/

PM> Install-Package CSharpTest.Net.Collections

PM> 安装包CSharpTest.Net.Collections

回答by mheyman

This takes Martin's code with Mr T's suggestions and makes it Stylecop friendly. Oh, it also allows for disposal of values as they cycle out of the cache.

这需要Martin的代码和Mr T的建议，并使其对 Stylecop 友好。哦，它还允许在值从缓存中循环时对其进行处理。

namespace LruCache
{
    using System;
    using System.Collections.Generic;

    /// <summary>
    /// A least-recently-used cache stored like a dictionary.
    /// </summary>
    /// <typeparam name="TKey">
    /// The type of the key to the cached item
    /// </typeparam>
    /// <typeparam name="TValue">
    /// The type of the cached item.
    /// </typeparam>
    /// <remarks>
    /// Derived from https://stackoverflow.com/a/3719378/240845
    /// </remarks>
    public class LruCache<TKey, TValue>
    {
        private readonly Dictionary<TKey, LinkedListNode<LruCacheItem>> cacheMap =
            new Dictionary<TKey, LinkedListNode<LruCacheItem>>();

        private readonly LinkedList<LruCacheItem> lruList =
            new LinkedList<LruCacheItem>();

        private readonly Action<TValue> dispose;

        /// <summary>
        /// Initializes a new instance of the <see cref="LruCache{TKey, TValue}"/>
        /// class.
        /// </summary>
        /// <param name="capacity">
        /// Maximum number of elements to cache.
        /// </param>
        /// <param name="dispose">
        /// When elements cycle out of the cache, disposes them. May be null.
        /// </param>
        public LruCache(int capacity, Action<TValue> dispose = null)
        {
            this.Capacity = capacity;
            this.dispose = dispose;
        }

        /// <summary>
        /// Gets the capacity of the cache.
        /// </summary>
        public int Capacity { get; }

        /// <summary>Gets the value associated with the specified key.</summary>
        /// <param name="key">
        /// The key of the value to get.
        /// </param>
        /// <param name="value">
        /// When this method returns, contains the value associated with the specified
        /// key, if the key is found; otherwise, the default value for the type of the 
        /// <paramref name="value" /> parameter. This parameter is passed
        /// uninitialized.
        /// </param>
        /// <returns>
        /// true if the <see cref="T:System.Collections.Generic.Dictionary`2" /> 
        /// contains an element with the specified key; otherwise, false.
        /// </returns>
        public bool TryGetValue(TKey key, out TValue value)
        {
            lock (this.cacheMap)
            {
                LinkedListNode<LruCacheItem> node;
                if (this.cacheMap.TryGetValue(key, out node))
                {
                    value = node.Value.Value;
                    this.lruList.Remove(node);
                    this.lruList.AddLast(node);
                    return true;
                }

                value = default(TValue);
                return false;
            }
        }

        /// <summary>
        /// Looks for a value for the matching <paramref name="key"/>. If not found, 
        /// calls <paramref name="valueGenerator"/> to retrieve the value and add it to
        /// the cache.
        /// </summary>
        /// <param name="key">
        /// The key of the value to look up.
        /// </param>
        /// <param name="valueGenerator">
        /// Generates a value if one isn't found.
        /// </param>
        /// <returns>
        /// The requested value.
        /// </returns>
        public TValue Get(TKey key, Func<TValue> valueGenerator)
        {
            lock (this.cacheMap)
            {
                LinkedListNode<LruCacheItem> node;
                TValue value;
                if (this.cacheMap.TryGetValue(key, out node))
                {
                    value = node.Value.Value;
                    this.lruList.Remove(node);
                    this.lruList.AddLast(node);
                }
                else
                {
                    value = valueGenerator();
                    if (this.cacheMap.Count >= this.Capacity)
                    {
                        this.RemoveFirst();
                    }

                    LruCacheItem cacheItem = new LruCacheItem(key, value);
                    node = new LinkedListNode<LruCacheItem>(cacheItem);
                    this.lruList.AddLast(node);
                    this.cacheMap.Add(key, node);
                }

                return value;
            }
        }

        /// <summary>
        /// Adds the specified key and value to the dictionary.
        /// </summary>
        /// <param name="key">
        /// The key of the element to add.
        /// </param>
        /// <param name="value">
        /// The value of the element to add. The value can be null for reference types.
        /// </param>
        public void Add(TKey key, TValue value)
        {
            lock (this.cacheMap)
            {
                if (this.cacheMap.Count >= this.Capacity)
                {
                    this.RemoveFirst();
                }

                LruCacheItem cacheItem = new LruCacheItem(key, value);
                LinkedListNode<LruCacheItem> node = 
                    new LinkedListNode<LruCacheItem>(cacheItem);
                this.lruList.AddLast(node);
                this.cacheMap.Add(key, node);
            }
        }

        private void RemoveFirst()
        {
            // Remove from LRUPriority
            LinkedListNode<LruCacheItem> node = this.lruList.First;
            this.lruList.RemoveFirst();

            // Remove from cache
            this.cacheMap.Remove(node.Value.Key);

            // dispose
            this.dispose?.Invoke(node.Value.Value);
        }

        private class LruCacheItem
        {
            public LruCacheItem(TKey k, TValue v)
            {
                this.Key = k;
                this.Value = v;
            }

            public TKey Key { get; }

            public TValue Value { get; }
        }
    }
}

回答by Mohsen Shakiba

I've created an implementation of the LRU cache
https://github.com/mohsenShakiba/LRUCache

我已经创建了 LRU 缓存的实现
https://github.com/mohsenShakiba/LRUCache