How to Implement a Cache Eviction Policy using TreeMap in Java?

2025 年 5 月 6 日 | 阅读 8 分钟

最近最少使用（Least Recently Used，LRU）是一种缓存淘汰技术，当缓存大小达到其最大分配容量时，它会移除缓存中最近最少访问的项。此外，缓存必须具有强大的同步机制，因为多个线程可能会访问应用程序中存储的项。

缓存是一种利用内存来存储频繁访问的数据以提高应用程序速度的技术。缓存淘汰策略决定了在缓存已满时需要删除哪些项。Java 的 TreeMap 提供了一个有序映射的实现，可用于构建具有独特淘汰技术的缓存。通过维护键的顺序，TreeMap 可以实现有效的迭代和检索。在本例中，我们将创建一个缓存淘汰方法，该方法使用时间戳作为键的 TreeMap 来优先删除最旧的项。

LRU 的设计

缓存是一种利用内存来存储频繁访问的数据以提高应用程序速度的技术。
缓存淘汰策略决定了在缓存已满时需要删除哪些项。
Java 的 TreeMap 提供了一个有序映射的实现，可用于构建具有独特淘汰技术的缓存。
通过维护键的顺序，TreeMap 可以实现有效的迭代和检索。
在本例中，我们将创建一个缓存淘汰方法，该方法使用时间戳作为键的 TreeMap 来优先删除最旧的项。

Java 的 ConcurrentHashMap（满足属性 1-4）和基本的双向链表（满足属性 5）可以用来创建一个主要的 LRU 缓存，同时考虑以上五个属性。ConcurrentHashMap 用于使用键存储和检索对象。它允许并发访问，提供设置大小限制的功能，并确保访问时间为 O(1) 顺序。

双向链表（DLL）维护指向相同项（在映射中）的指针。借助此 DLL，我们可以实现 LRU 淘汰方法，该方法将最常访问的项放在列表的末尾，将最不常访问的项放在列表的顶部。当向缓存添加新对象并且缓存已满至其总容量时，将发生 LRU 淘汰。本质上，将从 DLL 中删除头部节点（最近最少使用的对象），并且映射也将从中清除。

方法：使用 TreeMap

该代码使用 HashMap 进行键值存储（缓存），另一个HashMap 记录访问频率（freqMap），并使用 TreeMap（freqCount）来维护基于频率的排序，以创建具有容量限制的 LFU 缓存。为了应用 LFU 缓存淘汰策略，我们添加了键值对，并检索了各种键的值。TreeMap 将频率映射到一组键（LinkedHashSet），确保了快速检索和插入以及自然的排序。在访问或修改时，缓存会动态修改键的频率，并且当达到容量时，它会有效地删除利用率最低的键。使用 LFUCache 类创建一个容量为三的对象，并通过 get() 方法添加和检索值。通过利用这些数据结构的特性，此方法最大程度地提高了查找和更新效率。

算法

步骤 1：通过按频率对键进行分组来创建一个固定容量的 LFU 缓存，使用 TreeMap 存储基础值，使用 HashMap 存储基本值，并使用 HashMap 跟踪频率。

步骤 2：执行 Get 操作

步骤 2.1：如果缓存中不存在键，则返回 null。

步骤 2.2：如果存在，则更新频率计数器（TreeMap）和频率映射中的键的频率。

步骤 2.3：返回匹配的值。

步骤 3：执行 Put 操作

步骤 3.1：如果键存在，则使用 get 函数更改键的值和频率。

步骤 3.2：如果缓存已满，则删除利用率最低的键（TreeMap 中的最低频率）。

步骤 3.3：更新频率映射和计数器，插入新的键值组合，并将其频率设置为 1。

实施

文件名：LFUCache.java

import java.io.*;
import java.util.*;
class LFUCache<Key, Value> {
    private final int capacity;
    // create the actual key-value pairs
    private final Map<Key, Value> cache;
    // Store the frequency of every key
    private final Map<Key, Integer> freqMap;
    // TreeMap for efficient tracking of frequencies
    private final TreeMap<Integer, LinkedHashSet<Key>> freqCount;
    public LFUCache(int capacity) 
    {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.freqCount = new TreeMap<>();
    }
    public Value get(Key key) 
    {
         //If the Key is not found
        if (!cache.containsKey(key)) 
        {
            return null;
        }
        // Update the frequency
        int freq = freqMap.get(key);
        freqMap.put(key, freq + 1);
        // Update the frequency Counter
        freqCount.get(freq).remove(key);
        if (freqCount.get(freq).isEmpty()) 
        {
            freqCount.remove(freq);
        }
        freqCount.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);

        return cache.get(key);
    }
    public void put(Key key, Value value) 
    {
        //If no cache is there
        if (capacity <= 0) 
        {
            return;
        }
        if (cache.containsKey(key)) 
        {
            // Update the existing key and also the frequency
            cache.put(key, value);
            // Reuse to get the update frequency
            get(key); 
            return;
        }
        if (cache.size() >= capacity) 
        {
            // using the Least frequently used element
            int lowestFreq = freqCount.firstKey();
            Key leastFreqKey = freqCount.get(lowestFreq).iterator().next();
            // TreeMap for efficient tracking of frequencies
            cache.remove(leastFreqKey);
            freqMap.remove(leastFreqKey);
            // Remove from the frequencyCounter
            freqCount.get(lowestFreq).remove(leastFreqKey);
            if (freqCount.get(lowestFreq).isEmpty()) 
            {
                freqCount.remove(lowestFreq);
            }
        }
        // Add the new key-value pair to cache
        cache.put(key, value);
        // Update frequency maps
        freqMap.put(key, 1);
        // Update frequencyCounter
        freqCount.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    }
}

public class LFUCacheExample {
    public static void main(String[] args) {
        LFUCache<Integer, String> lfu = new LFUCache<>(3);
        lfu.put(1, "One");
        lfu.put(2, "Two");
        System.out.println("The Get 1: " + lfu.get(1));
        lfu.put(3, "Three");
        lfu.put(4, "Four");
        System.out.println("The Get 2: " + lfu.get(2)); 
        System.out.println("The Get 3: " + lfu.get(3)); 
        System.out.println("The Get 4: " + lfu.get(4)); 
        lfu.put(5, "Five");
        System.out.println("The Get 5: " + lfu.get(5)); 
    }
}   

输出

 
The Get 1: One
The Get 2: null
The Get 3: Three
The Get 4: Four
The Get 5: Five

复杂度分析

每个操作的时间复杂度为 O(log F)，其中 F 是唯一频率的数量（通常远小于 C），空间复杂度为 O(C)，其中 C 是缓存容量。

方法：使用 TreeMap 和双向链表

该方法利用 TreeMap 进行基于频率的排序，HashMap 进行 O(1) 键查找，以及双向链表进行高效的节点添加和删除。而 DoublyLinkedList 处理具有相同频率的节点，Node 类则负责跟踪缓存条目数据，如键、值和频率。这些数据结构协同工作，可高效更新频率计数，并在超出容量时淘汰使用频率最低（LFU）的节点，从而确保 LFU 缓存操作的最大性能。技术重点在于利用这些结构来维护内存组织和时间复杂度效率。

算法

步骤 1：声明容量、freqMap（频率-节点列表映射）和 nodeMap（键-节点映射）。

步骤 2：应用 Put 操作

步骤 2.1：如果键存在于 nodeMap 中，则更新其频率和值。

步骤 2.2：如果缓存大小超过容量，则应移除使用频率最低（LFU）的节点。

步骤 2.3：在 nodeMap 和 freqMap 中添加频率为 1 的新节点。

步骤 3：应用 Get 操作

步骤 3.1：如果键不存在于 nodeMap 中，则返回 null。

步骤 3.2：如果存在，则获取节点，返回其值，并更新其频率。

步骤 4：移除节点的当前频率列表。

步骤 5：将其添加到 freqMap 中的新频率列表中，并增加其频率。

步骤 6：使用 freqMap 查找最低频率。

步骤 7：删除关联列表中最近未使用的节点。

步骤 8：如果 nodeMap 为空，则删除节点并更新 freqMap。

步骤 9：使用 put 和 get 说明缓存操作并演示 LFU 功能。

实施

文件名：LFUCacheExample.java

import java.util.*;
import java.io.*;
// Node class representing a cache entry
class Node<Key, Value> 
{
    // Key, value and frequency of the cache entry
    Key k; 
    Value v; 
    int freq; 
    Node<Key, Value> prev, next; 
    public Node(Key k, Value v) 
    {
        this.k = k;
        this.v = v;
        this.freq = 1; // When the node is constructed, the initial frequency is 1.
    }
}
// Managing nodes with the same frequency using a doubly linked list
class DoublyLinkedList<Key, Value> 
{
    Node<Key, Value> head, tail;
    public DoublyLinkedList() 
    {
        // Duplicate of the lists.
        head = new Node<>(null, null); 
        tail = new Node<>(null, null); 
        head.next = tail;
        tail.prev = head;
    }
    // Add a node at the list's beginning.
    public void addNode(Node<Key, Value> node) 
    {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    // Remove a specific node from the list
    public void removeNode(Node<Key, Value> node) 
    {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    // Eliminate the tail node, which is the least used node.
    public Node<Key, Value> removeLast() 
    {
        if (tail.prev == head) {
            return null; // List is empty
        }
        Node<Key, Value> lastNode = tail.prev;
        removeNode(lastNode);
        return lastNode;
    }
    // Check if the list is empty
    public boolean isEmpty() {
        return head.next == tail;
    }
}
// LFU Cache implementation
public class LFUCache<Key, Value> 
{
    private final int capacity; // The cache's maximum capacity
    private final Map<Key, Node<Key, Value>> nodeMap; // Maps keys to nodes
    private final TreeMap<Integer, DoublyLinkedList<Key, Value>> freqMap; // Converts frequencies into node lists
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.nodeMap = new HashMap<>();
        this.freqMap = new TreeMap<>();
    }
    // Retrieve a cached value
    public Value get(Key k) {
        if (!nodeMap.containsKey(k)) 
        {
            return null; // Key not found
        }
        Node<Key, Value> node = nodeMap.get(k);
        updateFrequency(node); // Update frequency for LFU
        return node.v;
    }
    public void put(Key k, Value v) {
        if (capacity <= 0) {
            return; // No capacity to store data
        }
        if (nodeMap.containsKey(k)) {
            // Value and frequency should be updated
            Node<Key, Value> node = nodeMap.get(k);
            node.v = v;
            updateFrequency(node);
        } else {
            if (nodeMap.size() >= capacity) {
                // Remove the least-used node
                evictNode();
            }
            // Adding the new node
            Node<Key, Value> newNode = new Node<>(k, v);
            node map.put(k, newNode);
            freqMap.computeIfAbsent(1, unused -> new DoublyLinkedList<>()).addNode(newNode);
        }
    }
    // Update the frequency of a node
    private void updateFrequency(Node<Key, Value> node) 
    {
        int oldFreq = node.freq; // Current frequency
        DoublyLinkedList<Key, Value> oldList = freqMap.get(oldFreq);
        oldList.removeNode(node);
        if (oldList.isEmpty()) {
            freqMap.remove(oldFreq); // Remove frequency if no nodes left
        }
        node.freq++; // Increment frequency
        freqMap.computeIfAbsent(node.freq, unused -> new DoublyLinkedList<>()).addNode(node);
    }
    // Evict least frequently used node
    private void evictNode() {
        int lowestFreq = freqMap.firstKey(); // Least frequency
        DoublyLinkedList<Key, Value> list = freqMap.get(lowestFreq);
        Node<Key, Value> nodeToEvict = list.removeLast(); // Lowest frequency, least recently used
        if (list.isEmpty()) 
        {
            freqMap.remove(lowestFreq);
        }
        nodeMap.remove(nodeToEvict.k); 
    }
}
class LFUCacheExample {
    public static void main(String[] args) {
        LFUCache<Integer, String> lfu = new LFUCache<>(3);
        lfu.put(1, "One"); 
        lfu.put(2, "Two"); 
        System.out.println("The Get 1: " + lfu.get(1));
        lfu.put(3, "Three"); 
        lfu.put(4, "Four"); 
        System.out.println("The Get 2: " + lfu.get(2)); 
        System.out.println("The Get 3: " + lfu.get(3)); 
        System.out.println("The Get 4: " + lfu.get(4)); 
        lfu.put(5, "Five"); 
        System.out.println("The Get 5: " + lfu.get(5));
    }
}   

输出

 
The Get 1: One
The Get 2: null
The Get 3: Three
The Get 4: Four
The Get 5: Five

复杂度分析

每个操作的时间复杂度为 O(log F)，其中 F 是唯一频率的数量（通常远小于 C），空间复杂度为 O(C)，其中 C 是缓存容量。

下一个主题Java 中将数组传递给函数

How to Implement a Cache Eviction Policy using TreeMap in Java?

LRU 的设计

方法：使用 TreeMap

算法

实施

方法：使用 TreeMap 和双向链表

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

How to Implement a Cache Eviction Policy using TreeMap in Java?

LRU 的设计

方法：使用 TreeMap

算法

实施

方法：使用 TreeMap 和双向链表

实施

相关帖子

Java 对象模型

Character Array in Java

Java 中的 ArithmeticException

Java 中的 Fall Through

Java Program to Check if Two Strings are Cyclic Permutations of Each Other

Java 中 IntSummaryStatistics getMin() 方法及示例

Java 中 main() 方法的有效变体

How to Create Singleton Class in Java

Java 中的量词

Java Program to Illustrate Use of Binary Literals

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器