Home Java javaTutorial How to implement LRU caching algorithm using java

How to implement LRU caching algorithm using java

Sep 19, 2023 am 08:59 AM
java lru caching algorithm

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;
    }
}
Copy after login

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;
    }
}
Copy after login
  1. 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
    }
}
Copy after login

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Square Root in Java Square Root in Java Aug 30, 2024 pm 04:26 PM

Square Root in Java

Perfect Number in Java Perfect Number in Java Aug 30, 2024 pm 04:28 PM

Perfect Number in Java

Random Number Generator in Java Random Number Generator in Java Aug 30, 2024 pm 04:27 PM

Random Number Generator in Java

Armstrong Number in Java Armstrong Number in Java Aug 30, 2024 pm 04:26 PM

Armstrong Number in Java

Weka in Java Weka in Java Aug 30, 2024 pm 04:28 PM

Weka in Java

Smith Number in Java Smith Number in Java Aug 30, 2024 pm 04:28 PM

Smith Number in Java

Java Spring Interview Questions Java Spring Interview Questions Aug 30, 2024 pm 04:29 PM

Java Spring Interview Questions

Break or return from Java 8 stream forEach? Break or return from Java 8 stream forEach? Feb 07, 2025 pm 12:09 PM

Break or return from Java 8 stream forEach?

See all articles