7

我想实现一个LRU cache，其中最近最少使用的元素将被异步驱逐。我目前的想法是使用 aDictionary来存储<key,value>对，并跟踪对象的访问时间，以保持 a SortedDictionary <key, timestamp>。这个想法是让异步线程从缓存中获取 LRU 项SortedDictionary并从缓存中删除。但要使其正常工作，SortedDictionary需要按值排序，而事实并非如此。

我本可以使用单独SortedList的而不是SortedDictionary保持 {key and timestamp} 在 timestamp 上排序，但是我必须进行“线性”查找以从列表中查找密钥（当我必须更新时间戳时，当再次访问相同的键时） - 如果可能的话，我正在寻找一种比线性方式更好的方式。有人可以分享解决这个问题的想法吗？

所以，我的问题归结为：

我必须在 <= logn time 中查找键以更新时间戳，同时能够根据时间戳对键进行排序。

一种考虑的方法是根据 {key,timestamp} 的时间戳部分保留其中一个键SortedDictionary的<{key,timestamp},null>顺序。虽然这很好，但问题是hashcode()只需要返回 key.hashcode() （用于在更新时间戳时进行查找），同时equals()还应该使用时间戳。所以 ,equals()和hashcode()是 冲突 的 , 所以 觉得 这 不是 好 主意 ...

4

4 回答 4

4

你应该做的是保留两本字典，一本按时间排序，一本按键排序。

请记住，字典仅保存对您的实际对象的引用，因此您使用哪个字典来更新对象并不重要。

要更新对象，请创建一个将更新两个字典的函数

var oldObj = keyedObject[key];
timedObjects.Remove(oldObj.LastUpdateTime);
timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject);
keyedObject[key] = myUpdatedObject;

现在您可以按时间和键跟踪同一对象。

我只保留一个对timedObjects. 这有助于删除。

您可以根据需要继续修剪您的 timedObjects 字典。

Ofcource，在修剪时，您必须记住还有另一个字典keyedObject引用了同一对象。仅仅打电话Remove是不够的。

您的删除代码必须是这样的：

removeObject = timedObjects[timeToRemove];
timedObjects.Remove(timeToRemove);
keyedObject.Remove(removeObject.key);

timeToRemove 主要来自 for 循环，您可以在其中决定要删除的对象

于 2012-07-26T12:17:19.397 回答
0

代替 sorteddictionary，编写你自己的链表，并让 Dictionary 指向它的节点作为值。它将始终按时间戳排序，更新时间戳和删除最近最少使用的元素将是 O(1)。

于 2012-07-26T12:35:34.603 回答
0

您要查找的地图类型（至少在 Java 中）称为LinkedHashMap.

从javadoc：

Map 接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与 HashMap 的不同之处在于它维护一个双向链表，该列表贯穿其所有条目。这个链表定义了迭代顺序，通常是键插入映射的顺序（插入顺序）。

提供了一个特殊的构造函数来创建一个链接哈希映射，其迭代顺序是其条目最后一次访问的顺序，从最近最少访问到最近访问（访问顺序）。这种映射非常适合构建 LRU 缓存。

LinkedHashMap来自 OpenJDK 的来源

LinkedHashMapAFAIK，在 C#中没有现有的实现。话虽如此，写一个应该不难。

于 2012-07-26T12:28:12.943 回答
0

这是C#中LRU Cache的实现。高效 O(1)，但不是线程安全的；

    static void Main(string[] args)
    {
        var cache = new LruCache(3);
        cache.Put(1, 1);
        cache.Put(2, 2);
        Console.WriteLine(cache.Get(1));       // returns 1
        cache.Put(3, 3);    // evicts key 2
        Console.WriteLine(cache.Get(2));       // returns -1 (not found)
        cache.Put(4, 4);    // evicts key 1
        Console.WriteLine(cache.Get(1));       // returns -1 (not found)
        Console.WriteLine(cache.Get(3));       // returns 3
        Console.WriteLine(cache.Get(4));       // returns 4     

    }

    public class DoubleLinkedList
    {
        public int key;
        public int value;
        public DoubleLinkedList next;
        public DoubleLinkedList prev;
        public DoubleLinkedList(int k, int v)
        {
            key = k;
            value = v;
        }
    }

    public class LruCache
    {
        private int size;
        private int capacity;
        private Dictionary<int, DoubleLinkedList> map;
        private DoubleLinkedList head;
        private DoubleLinkedList tail;
        public LruCache(int cap)
        {
            capacity = cap;
            map = new Dictionary<int, DoubleLinkedList>();
            head = new DoubleLinkedList(0, 0);
            tail = new DoubleLinkedList(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        public int Get(int key)
        {
            if (map.ContainsKey(key))
            {
                if (tail.prev.key != key)
                {
                    var node = map[key];
                    RemoveNode(node);
                    AddToEnd(node);
                }
                return map[key].value;
            }
            return -1;
        }

        private void AddToEnd(DoubleLinkedList node)
        {
            var beforeTail = tail.prev;
            node.prev = beforeTail;
            beforeTail.next = node;
            tail.prev = node;
            node.next = tail;
        }

        private void RemoveNode(DoubleLinkedList node)
        {
            var before = node.prev;
            before.next = node.next;
            node.next.prev = before;
        }

        public void Put(int key, int value)
        {
            if (map.ContainsKey(key))
            {
                map[key].value = value;
                var node = map[key];
                RemoveNode(node);
                AddToEnd(node);
            }
            else
            {
                size++;
                if (size > capacity)
                {
                    var node = head.next;
                    RemoveNode(node);
                    map.Remove(node.key);
                    size--;
                }

                var newNode = new DoubleLinkedList(key, value);
                AddToEnd(newNode);
                map.Add(key, newNode);
            }
        }
    }
于 2019-03-11T04:11:26.003 回答