如何使用Java實作LRU快取演算法
引言:
在電腦科學領域,快取是一種常用的最佳化技術,用於提高資料讀取和寫入的速度。 LRU(Least Recently Used)是一種常見的快取替換策略,它根據資料最近被存取的時間來決定是否從快取中移除資料。本文將介紹如何使用Java語言實作LRU快取演算法,並提供詳細的程式碼範例。
首先,我們定義一個雙向鍊錶節點類別。
class Node { int key; int value; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; } }
然後,我們定義一個LRUCache類別來實作LRU快取演算法。
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 } }
結果輸出:
1
-1
-1
#3
4
總結:
本文介紹如何使用Java語言實作LRU快取演算法。透過使用雙向鍊錶和雜湊表資料結構,我們可以實現LRU快取演算法的基本功能,並提供了詳細的程式碼範例。讀者可以根據實際需求進行修改和擴展,以滿足不同的應用場景。
以上是如何使用java實作LRU快取演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!