IOException.de

Caches dienen in der Informatik als Methode, Zugriffe auf bestimmte Daten zu beschleunigen, in dem diese vorgelagert/gepuffert werden. Sie sind in verschiedensten Bereichen zu finden, unter anderem auf Prozessoren, in Festplatten, aber auch in Technologien wie dem Web. Verschiedene Verdrängungsstrategien ermöglichen es, die beschränkte Kapazität eines Caches zu berücksichtigen, so dass nur wichtige Werte im Cache gelagert werden. Least Recently Used (LRU), ist eine solche Strategie, die häufig angewandt wird. Sie sortiert die Werte im Cache nach der letzten Nutzung. Wird auf ein Element über einen längeren Zeitraum nicht mehr zugegriffen, so wird es aus dem Cache verdrängt.

In Java lässt sich ein solcher LRU-Cache besonders einfach implementieren, da die Klasse java.util.LinkedHashMap bereits die wesentlichen Mechanismen unterstützt. Eine HashMap ist eine Hash-Tabelle, die Zugriffe auf Werte über ihre Schlüssel regelt. Zusätzlich verkettet die LinkedHashMap aber die Werte noch in einer Liste, womit auch eine Traversierung in Einfügereihenfolge ermöglicht wird. Mithilfe eines Flags in einem der Konstruktoren kann dieses Verhalten geändert werden, so dass bei jedem Zugriff das angesprochene Element neu in diese Liste eingereiht wird. Damit verwaltet die Liste die Zugriffe und ist Basis für die LRU-Strategie.

Die Methode removeEldestEntry() der LinkedHashMap wird bei jedem Schreibezugriff auf die Map, also nach Einfügeoperationen über put() oder putAll() automatisch aufgerufen und bietet die Möglichkeit, durch Überschreiben der Methode die Verdrängungsstrategie zu implementieren. Diese Methode gibt ein boolean zurück, ob der älteste Eintrag gelöscht werden soll. Es ist auch möglich, innerhalb der Methode selbst die Liste zu manipulieren, dann sollte allerdings die Methode immer false zurückgeben. Für den LRU-Cache reicht es aus, die Größe der Map mit dem gewünschten Maximum zu vergleichen. Ist der Inhalt der Map zu groß, so soll das letzte Element gelöscht werden.

Im Folgenden nun der Code dazu. Zu beachten ist noch, dass es sich um eine threadsichere Klasse handelt, da die Map explizit synchronisiert wird.

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * A thread-safe LRU cache implementation based on internal LinkedHashMap.
 * 
 * @author Benjamin Erb
 *
 * @param <K> Entry Key Type
 * @param <V> Entry Value Type
 */
public class LRUCache<K, V>
{
	public static final int DEFAULT_MAX_SIZE = 1000;

	private final Map<K, V> internalMap;

	public LRUCache()
	{
		this(DEFAULT_MAX_SIZE);
	}

	public LRUCache(final int maxSize)
	{
		this.internalMap = (Map<K, V>) Collections.synchronizedMap(new LinkedHashMap<K, V>(maxSize + 1, .75F, true)
		{
			private static final long serialVersionUID = 5369285290965670135L;

			@Override
			protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
			{
				return size() > maxSize;
			}
		});
	}

	public V put(K key, V value)
	{
		return internalMap.put(key, value);
	}

	public V get(K key)
	{
		return internalMap.get(key);
	}

}