JavaでLRUキャッシュの実装

はじめに

現代のソフトウェア開発において、データのアクセス速度はシステム全体のパフォーマンスを左右する重要な要素です。特に、大量のデータを処理するアプリケーションでは、頻繁に使用されるデータを効率的に管理するためにキャッシュが欠かせません。

キャッシュとは、データを一時的に保存し、高速にアクセスできるようにする仕組みです。例えば、Webアプリケーションでは頻繁にアクセスされるデータをメモリ上に保持することで、データベースの負荷を軽減できます。

しかし、メモリには限りがあるため、どのデータを保持し、どのデータを削除するかを決定するアルゴリズムが必要です。

LRUキャッシュの仕組み

本記事では、キャッシュ管理の中でも LRU（Least Recently Used）キャッシュ に焦点を当てます。

LRUキャッシュは、メモリの使用量を制限しつつ、必要なデータへのアクセスを高速化するアルゴリズムで、最近使用されたデータを優先的に維持し、古いデータを削除することで、メモリを効率的に管理します。

本記事では、LRUキャッシュの仕組みを解説するとともに、Javaを用いた実装方法を詳しく紹介します。

LRUキャッシュの活用シーン

LRUキャッシュは、以下のような場面で活用されます：

• Webアプリケーションのデータキャッシュ
  • 頻繁にアクセスされるデータ（例: ユーザープロフィールやランキングデータ）をメモリ上に保持し、データベースの負荷を軽減する
• APIのレスポンス高速化
  • 外部APIからのデータ取得結果をキャッシュし、リクエスト数を削減
• OSのページ置換アルゴリズム
  • メモリ管理の一環として、最近使用されたページを優先し、不要なページを削除する
• CPUキャッシュ管理
  • LRUアルゴリズムを用いて、L1/L2キャッシュ内のデータを効率的に更新

ハッシュマップと双方向リストの組み合わせ

効率的なLRUキャッシュを実装するには、次の2つのデータ構造を組み合わせます。

• ハッシュマップ（HashMap）
  • キーとノード（データ）のペアを保持し、O(1) の時間で検索を実現
• 双方向リスト（LinkedList）
  • データの順序を保持し、最も最近使用されたデータをリストの先頭に移動
  • キャッシュがいっぱいになった際に末尾のデータを削除することで、削除処理をO(1)で実行可能

時間計算量

• get(key): O(1)（ハッシュマップで検索し、ノードをリストの先頭に移動）
• put(key, value): O(1)（新しいノードをリストの先頭に追加、または既存のノードを更新して先頭に移動。キャッシュの容量を超えた場合、最も古いデータ（LRU）を削除）

JavaでのLRUキャッシュの実装

以下は、JavaでのLRUキャッシュの実装例です。

import java.util.*;

class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> cache;
    private final DoublyLinkedList<K, V> list;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.list = new DoublyLinkedList<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        Node<K, V> node = cache.get(key);
        list.moveToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            Node<K, V> node = cache.get(key);
            node.value = value;
            list.moveToHead(node);
        } else {
            if (cache.size() >= capacity) {
                K removedKey = list.removeTail();
                cache.remove(removedKey);
            }
            Node<K, V> newNode = new Node<>(key, value);
            cache.put(key, newNode);
            list.addToHead(newNode);
        }
    }
}

class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev, next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class DoublyLinkedList<K, V> {
    private Node<K, V> head, tail;

    public DoublyLinkedList() {
        head = new Node<>(null, null);
        tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public void addToHead(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    public K removeTail() {
        Node<K, V> node = tail.prev;
        removeNode(node);
        return node.key;
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

まとめ

• LRUキャッシュは、最近使われたデータを維持し、古いデータを削除する
• ハッシュマップと双方向リストを組み合わせることで、データの取得と更新が O(1) で可能になる
• Javaの HashMap と LinkedList を活用して、効率的なキャッシュ管理を実装できる

これにより、アプリケーションのキャッシュ管理が最適化され、パフォーマンスが向上します。