是否存在IDictionary的LRU实现？

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

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

Answer 1

基类库中没有任何内容可以执行此操作。

在免费方面，也许像C5的HashedLinkedList这样的东西可行。

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

Answer 2

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

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

 namespace LRUCache { public class LRUCache { private int capacity; private Dictionary>> cacheMap = new Dictionary>>(); private LinkedList> lruList = new LinkedList>(); public LRUCache(int capacity) { this.capacity = capacity; } [MethodImpl(MethodImplOptions.Synchronized)] public V get(K key) { LinkedListNode> 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 cacheItem = new LRUCacheItem(key, val); LinkedListNode> node = new LinkedListNode>(cacheItem); lruList.AddLast(node); cacheMap.Add(key, node); } private void RemoveFirst() { // Remove from LRUPriority LinkedListNode> node = lruList.First; lruList.RemoveFirst(); // Remove from cache cacheMap.Remove(node.Value.key); } } class LRUCacheItem { public LRUCacheItem(K k, V v) { key = k; value = v; } public K key; public V value; } } 

Answer 3

发现你在google搜索时回答，也发现了这个：

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

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

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

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

Answer 4

我最近发布了一个名为LurchTable的类，以满足对LinkedHashMap的C＃变体的需求。 可以在这里找到关于LurchTable的简短讨论。

基本function：

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

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

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

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

PM>安装包CSharpTest.Net.Collections

Answer 5

这需要马丁的代码与T先生的建议，并使Stylecop友好。 哦，它还允许在循环退出缓存时处理值。

 namespace LruCache { using System; using System.Collections.Generic; /// 
 /// A least-recently-used cache stored like a dictionary. /// 
 ///  /// The type of the key to the cached item ///  ///  /// The type of the cached item. ///  ///  /// Derived from https://stackoverflow.com/a/3719378/240845 ///  public class LruCache { private readonly Dictionary> cacheMap = new Dictionary>(); private readonly LinkedList lruList = new LinkedList(); private readonly Action dispose; /// 
 /// Initializes a new instance of the  /// class. /// 
 ///  /// Maximum number of elements to cache. ///  ///  /// When elements cycle out of the cache, disposes them. May be null. ///  public LruCache(int capacity, Action dispose = null) { this.Capacity = capacity; this.dispose = dispose; } /// 
 /// Gets the capacity of the cache. /// 
 public int Capacity { get; } /// 
Gets the value associated with the specified key.
 ///  /// The key of the value to get. ///  ///  /// 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 ///  parameter. This parameter is passed /// uninitialized. ///  ///  /// true if the  /// contains an element with the specified key; otherwise, false. ///  public bool TryGetValue(TKey key, out TValue value) { lock (this.cacheMap) { LinkedListNode 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; } } /// 
 /// Looks for a value for the matching . If not found, /// calls  to retrieve the value and add it to /// the cache. /// 
 ///  /// The key of the value to look up. ///  ///  /// Generates a value if one isn't found. ///  ///  /// The requested value. ///  public TValue Get(TKey key, Func valueGenerator) { lock (this.cacheMap) { LinkedListNode 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(cacheItem); this.lruList.AddLast(node); this.cacheMap.Add(key, node); } return value; } } /// 
 /// Adds the specified key and value to the dictionary. /// 
 ///  /// The key of the element to add. ///  ///  /// The value of the element to add. The value can be null for reference types. ///  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 node = new LinkedListNode(cacheItem); this.lruList.AddLast(node); this.cacheMap.Add(key, node); } } private void RemoveFirst() { // Remove from LRUPriority LinkedListNode 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; } } } } 

Answer 6

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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