算法基本實現(xiàn)

上文提到，LRU算法需要維護一個有序的數(shù)據(jù)結(jié)構(gòu)，來記錄數(shù)據(jù)的訪問歷史。通常我們會用雙向鏈表來實現(xiàn)這個數(shù)據(jù)結(jié)構(gòu)，因為雙向鏈表可以在O(1)的時間復(fù)雜度內(nèi)往鏈表的頭部或者尾部插入數(shù)據(jù)，以及在O(1)的時間復(fù)雜度內(nèi)刪除數(shù)據(jù)。

我們將數(shù)據(jù)存儲在雙向鏈表中，每次訪問數(shù)據(jù)的時候，就將數(shù)據(jù)移動到鏈表的尾部，這樣就可以保證鏈表的尾部就是最近訪問的數(shù)據(jù)，鏈表的頭部就是最久沒有被訪問的數(shù)據(jù)。

當緩存滿了之后，如果需要插入新的數(shù)據(jù)，因為鏈表的頭部就是最久沒有被訪問的數(shù)據(jù)，所以我們就可以直接將鏈表的頭部刪除，然后將新的數(shù)據(jù)插入到鏈表的尾部。

如果我們要實現(xiàn)一個鍵值對的緩存，我們可以用一個哈希表來存儲鍵值對，這樣就可以在O(1)的時間復(fù)雜度內(nèi)完成查找操作，.NET 中我們可以使用 Dictionary。

同時我們使用 LinkedList 來作為雙向鏈表的實現(xiàn)，存儲緩存的 key，以此記錄數(shù)據(jù)的訪問歷史。

我們在每次操作 Dictionary 進行插入、刪除、查找的時候，都需要將對應(yīng)的 key 也插入、刪除、移動到鏈表的尾部。

// 實現(xiàn) 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 添加到鏈表的尾部 ? ? ? ? ? ?// 這樣就可以保證鏈表的尾部就是最近訪問的數(shù)據(jù)，鏈表的頭部就是最久沒有被訪問的數(shù)據(jù) ? ? ? ? ? ?// 但是在鏈表中刪除 key 的時間復(fù)雜度是 O(n)，所以這個算法的時間復(fù)雜度是 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 已經(jīng)存在，將 key 對應(yīng)的值更新，然后將 key 移動到鏈表的尾部 ? ? ? ? ? ?_dictionary[key] = value; ? ? ? ? ? ?_list.Remove(key); ? ? ? ? ? ?_list.AddLast(key); ? ? ? ?} ? ? ? ?else ? ? ? ?{ ? ? ? ? ? ? ? ? ? ? ?if (_list.Count == _capacity) ? ? ? ? ? ?{ ? ? ? ? ? ? ? ?// 緩存滿了，刪除鏈表的頭部，也就是最久沒有被訪問的數(shù)據(jù) ? ? ? ? ? ? ? ?_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

算法優(yōu)化

上面的實現(xiàn)中，對緩存的查詢、插入、刪除都會涉及到鏈表中數(shù)據(jù)的刪除（移動也是刪除再插入）。

因為我們在 LinkedList 中存儲的是 key，所以我們需要先通過 key 在鏈表中找到對應(yīng)的節(jié)點，然后再進行刪除操作，這就導(dǎo)致了鏈表的刪除操作的時間復(fù)雜度是 O(n)。

雖然 Dictionary 的查找、插入、刪除操作的時間復(fù)雜度都是 O(1)，但因為鏈表操作的時間復(fù)雜度是 O(n)，整個算法的最差時間復(fù)雜度是 O(n)。

算法優(yōu)化的關(guān)鍵在于如何降低鏈表的刪除操作的時間復(fù)雜度。

優(yōu)化思路：

1. 在 Dictionary 中存儲 key 和 LinkedList 中節(jié)點的映射關(guān)系

2. 在 LinkedList 的節(jié)點中存儲 key-value

也就是說，我們讓兩個本來不相關(guān)的數(shù)據(jù)結(jié)構(gòu)之間產(chǎn)生聯(lián)系。

不管是在插入、刪除、查找緩存的時候，都可以通過這種聯(lián)系來將時間復(fù)雜度降低到 O(1)。

1. 通過 key 在 Dictionary 中找到對應(yīng)的節(jié)點，然后再從 LinkedList 節(jié)點中取出 value，時間復(fù)雜度是 O(1)

2. LinkedList 刪除數(shù)據(jù)之前，先通過 key 在 Dictionary 中找到對應(yīng)的節(jié)點，然后再刪除，這樣就可以將鏈表的刪除操作的時間復(fù)雜度降低到 O(1)

3. LinkedList 刪除頭部節(jié)點時，因為節(jié)點中存儲了 key，所以我們可以通過 key 在 Dictionary 中刪除對應(yīng)的節(jié)點，時間復(fù)雜度是 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(); ? ?}}