C#实现LRU缓存替换策略
算法基本实现
上文提到，LRU算法需要维护一个有序的数据结构，来记录数据的访问历史。通常我们会用双向链表来实现这个数据结构，因为双向链表可以在O(1)的时间复杂度内往链表的头部或者尾部插入数据，以及在O(1)的时间复杂度内删除数据。
我们将数据存储在双向链表中，每次访问数据的时候，就将数据移动到链表的尾部，这样就可以保证链表的尾部就是最近访问的数据，链表的头部就是最久没有被访问的数据。
当缓存满了之后，如果需要插入新的数据，因为链表的头部就是最久没有被访问的数据，所以我们就可以直接将链表的头部删除，然后将新的数据插入到链表的尾部。
如果我们要实现一个键值对的缓存，我们可以用一个哈希表来存储键值对，这样就可以在O(1)的时间复杂度内完成查找操作，.NET 中我们可以使用 Dictionary。
同时我们使用 LinkedList 来作为双向链表的实现，存储缓存的 key，以此记录数据的访问历史。
我们在每次操作 Dictionary 进行插入、删除、查找的时候，都需要将对应的 key 也插入、删除、移动到链表的尾部。
// 实现 IEnumerable 接口，方便遍历public class LRUCache<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>{ private readonly LinkedList<TKey> _list; private readonly Dictionary<TKey, TValue> _dictionary; private readonly int _capacity; public LRUCache(int capacity) { _capacity = capacity; _list = new LinkedList<TKey>(); _dictionary = new Dictionary<TKey, TValue>(); } public TValue Get(TKey key) { if (_dictionary.TryGetValue(key, out var value)) { // 在链表中删除 key，然后将 key 添加到链表的尾部 // 这样就可以保证链表的尾部就是最近访问的数据，链表的头部就是最久没有被访问的数据 // 但是在链表中删除 key 的时间复杂度是 O(n)，所以这个算法的时间复杂度是 O(n) _list.Remove(key); _list.AddLast(key); return value; } return default; } public void Put(TKey key, TValue value) { if (_dictionary.TryGetValue(key, out _)) { // 如果插入的 key 已经存在，将 key 对应的值更新，然后将 key 移动到链表的尾部 _dictionary[key] = value; _list.Remove(key); _list.AddLast(key); } else { if (_list.Count == _capacity) { // 缓存满了，删除链表的头部，也就是最久没有被访问的数据 _dictionary.Remove(_list.First.Value); _list.RemoveFirst(); } _list.AddLast(key); _dictionary.Add(key, value); } } public void Remove(TKey key) { if (_dictionary.TryGetValue(key, out _)) { _dictionary.Remove(key); _list.Remove(key); } } public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() { foreach (var key in _list) { yield return new KeyValuePair<TKey, TValue>(key, _dictionary[key]); } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }}var lruCache = new LRUCache<int, int>(4);lruCache.Put(1, 1);lruCache.Put(2, 2);lruCache.Put(3, 3);lruCache.Put(4, 4);Console.WriteLine(string.Join(" ", lruCache));Console.WriteLine(lruCache.Get(2));Console.WriteLine(string.Join(" ", lruCache));lruCache.Put(5, 5);Console.WriteLine(string.Join(" ", lruCache));lruCache.Remove(3);Console.WriteLine(string.Join(" ", lruCache));
输出：
[1, 1] [2, 2] [3, 3] [4, 4] // 初始化2 // 访问 2[1, 1] [3, 3] [4, 4] [2, 2] // 2 移动到链表尾部[3, 3] [4, 4] [2, 2] [5, 5] // 插入 5[4, 4] [2, 2] [5, 5] // 删除 3
算法优化
上面的实现中，对缓存的查询、插入、删除都会涉及到链表中数据的删除（移动也是删除再插入）。
因为我们在 LinkedList 中存储的是 key，所以我们需要先通过 key 在链表中找到对应的节点，然后再进行删除操作，这就导致了链表的删除操作的时间复杂度是 O(n)。
虽然 Dictionary 的查找、插入、删除操作的时间复杂度都是 O(1)，但因为链表操作的时间复杂度是 O(n)，整个算法的最差时间复杂度是 O(n)。
算法优化的关键在于如何降低链表的删除操作的时间复杂度。
优化思路：
在 Dictionary 中存储 key 和 LinkedList 中节点的映射关系
在 LinkedList 的节点中存储 key-value
也就是说，我们让两个本来不相关的数据结构之间产生联系。
不管是在插入、删除、查找缓存的时候，都可以通过这种联系来将时间复杂度降低到 O(1)。
通过 key 在 Dictionary 中找到对应的节点，然后再从 LinkedList 节点中取出 value，时间复杂度是 O(1)
LinkedList 删除数据之前，先通过 key 在 Dictionary 中找到对应的节点，然后再删除，这样就可以将链表的删除操作的时间复杂度降低到 O(1)
LinkedList 删除头部节点时，因为节点中存储了 key，所以我们可以通过 key 在 Dictionary 中删除对应的节点，时间复杂度是 O(1)
public class LRUCache_V2<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>{ private readonly LinkedList<KeyValuePair<TKey, TValue>> _list; private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _dictionary; private readonly int _capacity; public LRUCache_V2(int capacity) { _capacity = capacity; _list = new LinkedList<KeyValuePair<TKey, TValue>>(); _dictionary = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>(); } public TValue Get(TKey key) { if (_dictionary.TryGetValue(key, out var node)) { _list.Remove(node); _list.AddLast(node); return node.Value.Value; } return default; } public void Put(TKey key, TValue value) { if (_dictionary.TryGetValue(key, out var node)) { node.Value = new KeyValuePair<TKey, TValue>(key, value); _list.Remove(node); _list.AddLast(node); } else { if (_list.Count == _capacity) { _dictionary.Remove(_list.First.Value.Key); _list.RemoveFirst(); } var newNode = new LinkedListNode<KeyValuePair<TKey, TValue>>(new KeyValuePair<TKey, TValue>(key, value)); _list.AddLast(newNode); _dictionary.Add(key, newNode); } } public void Remove(TKey key) { if (_dictionary.TryGetValue(key, out var node)) { _dictionary.Remove(key); _list.Remove(node); } } public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() { return _list.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }}
