How to implement LRU caching algorithm using java

How to use Java to implement the LRU caching algorithm

Introduction:
In the field of computer science, caching is a commonly used optimization technology to improve data reading and writing speed. LRU (Least Recently Used) is a common cache replacement strategy that determines whether to remove data from the cache based on the time when the data was recently accessed. This article will introduce how to implement the LRU cache algorithm using Java language and provide detailed code examples.

1. Principle of LRU cache algorithm
   LRU cache algorithm is a time-based cache replacement strategy. When the cache is full, if new data needs to be inserted, the LRU algorithm will select the least recently used data for replacement.
2. Data structure to implement the LRU cache algorithm
   In order to implement the LRU cache algorithm, we need to use a doubly linked list and a hash table. A doubly linked list is used to maintain the access sequence of data. The most recently accessed data is at the head of the linked list, and the data that has not been accessed for the longest time is at the tail of the linked list. Hash tables are used to quickly find the location of data in a linked list.
3. Code example to implement LRU caching algorithm
   The following is a simple Java code example of LRU caching algorithm.

First, we define a doubly linked list node class.

class Node {
    int key;
    int value;
    Node prev;
    Node next;
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

Then, we define a LRUCache class to implement the LRU cache algorithm.

import java.util.HashMap;

class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> map;
    private Node head;
    private Node tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        
        // 创建虚拟头节点和尾节点
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            removeNode(node);
            addToHead(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            removeNode(node);
            addToHead(node);
        } else {
            if (map.size() == capacity) {
                map.remove(tail.prev.key);
                removeNode(tail.prev);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        }
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
}

4. Usage example
   The following is an example of using the LRUCache class.

public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 输出 1
        
        cache.put(3, 3);
        System.out.println(cache.get(2)); // 输出 -1
        
        cache.put(4, 4);
        System.out.println(cache.get(1)); // 输出 -1
        System.out.println(cache.get(3)); // 输出 3
        System.out.println(cache.get(4)); // 输出 4
    }
}

Result output:
1
-1
-1
3
4

Summary:
This article describes how Use Java language to implement the LRU cache algorithm. By using doubly linked list and hash table data structures, we can implement the basic functions of the LRU cache algorithm, and detailed code examples are provided. Readers can modify and expand it according to actual needs to meet different application scenarios.

The above is the detailed content of How to implement LRU caching algorithm using java. For more information, please follow other related articles on the PHP Chinese website!