So implementieren Sie den LRU-Caching-Algorithmus mit Java
Einführung:
Im Bereich der Informatik ist Caching eine häufig verwendete Optimierungstechnik, um die Geschwindigkeit des Lesens und Schreibens von Daten zu erhöhen. LRU (Least Recent Used) ist eine gängige Cache-Ersetzungsstrategie, die basierend auf dem Zeitpunkt des letzten Zugriffs auf die Daten bestimmt, ob Daten aus dem Cache entfernt werden sollen. In diesem Artikel wird die Implementierung des LRU-Cache-Algorithmus mithilfe der Java-Sprache vorgestellt und detaillierte Codebeispiele bereitgestellt.
Zuerst definieren wir eine doppelt verknüpfte Listenknotenklasse.
class Node { int key; int value; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; } }
Dann definieren wir eine LRUCache-Klasse, um den LRU-Cache-Algorithmus zu implementieren.
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; } }
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 } }
Ergebnisausgabe:
1
-1
-1
3
4
Zusammenfassung:
In diesem Artikel wird erläutert, wie Sie die Java-Sprache zum Implementieren des LRU-Cache-Algorithmus verwenden. Durch die Verwendung doppelt verknüpfter Listen- und Hash-Tabellen-Datenstrukturen können wir die Grundfunktionen des LRU-Cache-Algorithmus implementieren und detaillierte Codebeispiele bereitstellen. Leser können es entsprechend den tatsächlichen Anforderungen ändern und erweitern, um verschiedenen Anwendungsszenarien gerecht zu werden.
Das obige ist der detaillierte Inhalt vonSo implementieren Sie den LRU-Caching-Algorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!