0

我已经实现了一个简单的 LRU 缓存，它是一个从头开始手动编写的双向链表。缓存中填充了对象请求，这些对象通过它们的数字（整数）ID 来区分。这些 Request 对象作为对一组 N < L 个预定义的 Request 对象的 L 个随机独立且相同分布的请求流生成，并一个一个到达缓存（即以串行方式）。然后我检查缓存命中或未命中以及当前缓存大小是否已达到最大缓存大小，然后根据具体情况，我执行将请求项插入缓存或从请求项替换 LRU 缓存项。

缓存的操作之一如下：当我遇到缓存命中时，如果请求的项目不在头部，则必须将其移动到那里。

例如，假设缓存的最大大小 M = 4，其在给定时间的内容如下：

项目：7 | 3 | 4 | 5

缓存位置索引：0 | 1 | 2 | 3（0是头，3是尾）

现在，如果我们有一个缓存命中项目 4，因为这个项目不在缓存的头部，它应该被移动到那里，结果将是：

项目：4 | 7 | 3 | 5

缓存位置索引：0 | 1 | 2 | 3（0是头，3是尾）

但是，当我运行代码时，结果是这样的：

项目：4| 7 | 3 | 4 | 5

缓存位置索引：0 | 1 | 2 | 3 | 4（0是头，4是尾）

换句话说，相关项（在本例中为第 4 项）并没有从缓存中删除然后添加到头部，而是简单地添加到头部。因此，缓存大小增加了 1（在本例中，它变为 5，大于最大缓存大小 M = 4）。

这是相关代码，以及显示我认为问题性质的注释：

public void moveToHead(Request request) {

        if(request != head) {

            // set previous node equal to the requested item
            request.left = request;

            // --> if I set here request = null; then I will move to the head a null object!!! What to do? <--

            // move requested item to head
            head.left = request;
            request.right = head;
            head = request;

        }

    }

正如我在评论中所说，如果在第一行代码之后我将对象请求设置为 null 以将其删除，那么以下代码行将移动到一个 null 对象的头部。如何解决这个问题？我假设我必须在下面的代码中使用临时请求变量，但我还没有弄清楚如何去做。

4

1 回答 1

1

为此，变量head由一个虚拟对象初始化：

head = new Request();
head.left = head;
head.right = head,

对于缓存命中，首先从列表中删除条目：

request.left.right = request.right;
request.right.left = request.left,

然后将其添加到列表头：

request.left = head;
request.right = head.right;
request.right.left = request;
head.right = request;

也许在这里看到一些现实世界的实现：https ://github.com/headissue/cache2k/blob/master/core/src/main/java/org/cache2k/impl/LruCache.java

祝你好运！

于 2014-03-06T12:47:48.450 回答