java实现LRU算法，附代码

谁借莪１个温暖的怀抱￠ 2024-03-23 20:09 89阅读 0赞

### **LRU算法简介：** ###

原理是根据页面的最近使用情况来决定哪些页面应该被置换出去，以便为新的页面腾出空间，是一种常见的页面置换算法，用于操作系统中的页面缓存管理。

### **代码部分：** ###

#### **整体结构** ####

![113590b93b88461cac50c059d638c12e.png][]

#### LRUCache.java ####

import java.util.*;
    
    
    class LRUCache<K, V> {
        private final int capacity;
        private final Map<K, Node<K, V>> cache;
        private final Node<K, V> head;
        private final Node<K, V> tail;
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            cache = new HashMap<>();
            head = new Node<>(null, null);
            tail = new Node<>(null, null);
            head.next = tail;
            tail.prev = head;
        }
    
        public V get(K key) {
            Node<K, V> node = cache.get(key);
    
            if (node == null) {
                // 缓存中不存在该键，返回null
                return null;
            }
    
            // 移动访问过的节点到链表头部，表示最近被使用过
            moveToHead(node);
            return node.value;
        }
    
        public void put(K key, V value) {
            Node<K, V> node = cache.get(key);
    
            if (node == null) {
                // 缓存中不存在该键，需要插入新节点
    
                if (cache.size() >= capacity) {
                    // 缓存已满，移除最久未使用的节点（尾节点的前一个节点）
    
                    Node<K, V> evictNode = tail.prev;
                    removeNode(evictNode);
                    cache.remove(evictNode.key);
                }
    
                // 创建新节点并放入缓存
                node = new Node<>(key, value);
                cache.put(key, node);
            } else {
                // 缓存中存在该键，更新节点的值，并将其移动到链表头部
                node.value = value;
                moveToHead(node);
            }
    
            // 将节点插入链表头部
            addToHead(node);
        }
    
        private void moveToHead(Node<K, V> node) {
            // 从链表中移除节点
            removeNode(node);
            // 将节点插入链表头部
            addToHead(node);
        }
    
        private void removeNode(Node<K, V> node) {
            // 从链表中移除节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
        private void addToHead(Node<K, V> node) {
            // 将节点插入链表头部
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
    
        private static class Node<K, V> {
            private final K key;
            private V value;
            private Node<K, V> prev;
            private Node<K, V> next;
    
            Node(K key, V value) {
                this.key = key;
                this.value = value;
            }
        }

#### Main.java ####

public class Main {
        public static void main(String[] args) {
            LRUCache<Integer, String> cache = new LRUCache<>(3);
            cache.put(1, "one");
            cache.put(2, "two");
            cache.put(3, "three");
            System.out.println(cache.get(1)); // 输出: one
            cache.put(4, "four");
            System.out.println(cache.get(2)); // 输出: null
            System.out.println(cache.get(1));
            System.out.println(cache.get(3));
            System.out.println(cache.get(4));
    
        }
    }

#### **运行结果** ####

![d491acd72dce45b099912cf93848a2ad.png][]

#### 过程： ####

首先创建LRUCache对象，容量为3。接着，将key为1,2,3的键值对数据以头插方式插入链表。当输出key为1的数据时，相当于访问，所以key为1的数据提前到链表头部，变成了1->3->2，插入key为4的数据时，挤出2，变为4->1->3。

[113590b93b88461cac50c059d638c12e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dcf2e61a8219477f87729f8b5180fb17.png
[d491acd72dce45b099912cf93848a2ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/91954b81826f4e219b757643c2926f3b.png