Java を使用して LRU キャッシュ アルゴリズムを実装する方法
はじめに:
コンピューター サイエンスの分野では、キャッシュはデータを改善するために一般的に使用される最適化テクノロジです。読み取りと書き込みの速度。 LRU (最も最近使用されていない) は、データが最近アクセスされた時刻に基づいてキャッシュからデータを削除するかどうかを決定する一般的なキャッシュ置換戦略です。この記事では、Java 言語を使用して LRU キャッシュ アルゴリズムを実装する方法を紹介し、詳細なコード例を示します。
まず、二重リンク リスト ノード クラスを定義します。
class Node { int key; int value; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; } }
次に、LRU キャッシュ アルゴリズムを実装するための LRUCache クラスを定義します。
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 中国語 Web サイトの他の関連記事を参照してください。