LRU Cache — wat is het, verdringingsalgoritme en hoe het werkt

Wat is LRU Cache?

LRU Cache (Least Recently Used Cache) — een gegevensstructuur met een vaste grootte die een beperkt aantal elementen opslaat en automatisch de elementen verwijdert die het minst zijn benaderd. Wanneer een toepassing een element opvraagt, wordt het naar het „verse” deel van de cache verplaatst en elementen die lang niet zijn gebruikt, verschuiven naar het einde en worden verwijderd wanneer de limiet wordt bereikt.

De naam „Least Recently Used” beschrijft het verdringingsbeleid: het element dat het langst niet is gebruikt van alle opgeslagen elementen wordt verwijderd. Dit is gebaseerd op de veronderstelling van locality of reference — recent opgevraagde gegevens zullen met grote waarschijnlijkheid opnieuw nodig zijn. Daarom wordt LRU beschouwd als een van de meest effectieve caching-strategieën voor de meeste toepassingen.

De klassieke implementatie van LRU Cache vereist twee gegevensstructuren: een hashtabel voor O(1)-toegang tot elk element via een sleutel en een dubbel gelinkte lijst om de gebruiksvolgorde bij te houden. De hashtabel slaat verwijzingen naar de knooppunten van de lijst op en de lijst handhaaft de volgorde van het nieuwste element (kop) tot het oudste (staart).

Basisbewerkingen van LRU Cache

De bewerking get(key) controleert de aanwezigheid van de sleutel in de hashtabel. Als het element wordt gevonden, wordt het naar de kop van de lijst verplaatst (wordt het nieuwste) en wordt de waarde geretourneerd. Als het niet wordt gevonden — wordt null geretourneerd of wordt een uitzondering gegenereerd. De bewerking put(key, value) voegt een nieuw element in: als de sleutel al bestaat — wordt de waarde bijgewerkt en het element naar de kop verplaatst. Als de cache vol is, wordt voor het invoegen het staartelement van de lijst verwijderd. Alle bewerkingen worden uitgevoerd in constante tijd O(1).

Hoe werkt LRU Cache

Het LRU Cache-algoritme is gebaseerd op twee principes: een toegangsteller in tijdsvolgorde en het verdringingsmechanisme bij overloop. Elk element wordt opgeslagen in een knooppunt van de dubbel gelinkte lijst en de verwijzingen naar deze knooppunten — in de hashtabel. Bij elke toegang tot een element wordt het losgekoppeld van zijn huidige positie en aan het begin van de lijst ingevoegd.

Wanneer de cachegrootte de maximale waarde (maxSize) bereikt en er een verzoek komt om een nieuw element in te voegen, verwijdert het algoritme het staartelement van de dubbel gelinkte lijst — dit is het element dat het langst niet is gebruikt. Na verwijdering komt er ruimte vrij voor het nieuwe element, dat aan de kop van de lijst wordt ingevoegd. De hashtabel wordt bijgewerkt: de oude sleutel wordt verwijderd, de nieuwe wordt toegevoegd.

Een kenmerk van LRU is de ongevoeligheid voor toegangspatronen met cyclische herhaling. Als een toepassing periodiek een grotere gegevensset benadert dan de cachegrootte, kan LRU last hebben van thrashing — frequente vervanging van elementen waarbij elk nieuw verzoek het vorige verdringt. In dergelijke scenario's kunnen LFU (Least Frequently Used) of adaptieve algoritmen effectiever zijn.

Cachegrootte en statistieken

De keuze van de LRU Cache-grootte is een compromis tussen geheugengebruik en hit-ratio (het percentage succesvolle toegangen). Typische waarden voor mobiele toepassingen: 10–20% van het beschikbare geheugen voor de afbeeldingencache en 50–200 items voor de cache van netwerkantwoorden. Een hit-ratio van 80–95% wordt beschouwd als een goede indicator waarbij de cache de geheugenkosten rechtvaardigt. Voor monitoring worden de tellers hitCount en missCount gebruikt, beschikbaar in de LruCache-implementatie in Android.

Implementatie van LRU Cache: HashMap + Doubly Linked List

De canonieke implementatie van LRU Cache gebruikt een combinatie van een hashtabel en een dubbel gelinkte lijst. De hashtabel biedt toegang tot elk knooppunt via een sleutel in O(1) en de dubbel gelinkte lijst — het verplaatsen van een knooppunt naar de kop en het verwijderen van de staart in O(1). Het is belangrijk dat de lijst precies dubbel gelinkt is: dit maakt het mogelijk een knooppunt uit het midden van de lijst los te koppelen zonder alle elementen te doorlopen.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

In de implementatie slaat elk knooppunt (Node) de waarde en verwijzingen naar het vorige en volgende knooppunt op. Sentinel-knooppunten head en tail vereenvoudigen randgevallen — null-controles bij invoegen en verwijderen zijn niet nodig. De methode get verplaatst het gevonden knooppunt naar de kop en put verwijdert bij overloop het staartelement. Een aparte methode removeKeyByValue vindt de sleutel in de hashtabel via een verwijzing naar het knooppunt en verwijdert deze.

Ingebouwde LruCache-implementatie in Android

De Android SDK biedt de kant-en-klasse klasse LruCache in het pakket android.util, die het LRU-algoritme implementeert met LinkedHashMap in access-order-modus. De klasse is thread-safe, ondersteunt hit/miss-telling en biedt ook de callback entryRemoved voor het vrijmaken van bronnen bij het verdringen van een element. De cachegrootte wordt ingesteld in willekeurige eenheden (bytes, aantal elementen) — het is voldoende om de methode sizeOf te overschrijven.

LRU Cache vs FIFO en LIFO

Alle drie de algoritmen — LRU, FIFO en LIFO — lossen dezelfde taak op: het beperken van geheugengebruik door elementen te verdringen bij overloop. Ze gebruiken echter fundamenteel verschillende criteria voor het selecteren van een slachtoffer, wat hun effectiviteit in verschillende scenario's bepaalt.

FIFO verdringt het oudste element op basis van toevoegingstijd, ongeacht hoe vaak het is benaderd. Dit kan inefficiënt zijn als het oude element nog steeds relevant is. LRU vermijdt dit nadeel door rekening te houden met het toegangspatroon. LIFO verdringt het nieuw toegevoegde element — nuttig voor undo-scenario's, maar ongeschikt voor caching omdat nieuwe gegevens vaak meer nodig zijn dan oude. LRU wordt beschouwd als de optimale balans tussen implementatiecomplexiteit en hit-ratio voor de meeste toepassingen.

LRU Cache-codevoorbeelden

Laten we het gebruik van de ingebouwde klasse LruCache uit de Android SDK voor het cachen van geladen afbeeldingen bekijken. Het voorbeeld toont de initialisatie van de cache op 1/8 van het beschikbare geheugen van de toepassing, wat de standaard Google-aanbeveling is voor de afbeeldingencache.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

De methode sizeOf retourneert de grootte van het element in dezelfde eenheden als waarin cacheSize is ingesteld. Hier wordt de grootte van Bitmap in kilobytes gebruikt (rowBytes × height / 1024). Wanneer de som van sizeOf van alle elementen cacheSize overschrijdt, verdringt LruCache automatisch de meest recent niet gebruikte Bitmaps. De callback entryRemoved kan worden gebruikt om bitmap.recycle() aan te roepen — geheugen vrijmaken vóór verdringing.

Implementatie van LRU Cache in Swift

iOS heeft geen ingebouwde LRU Cache-klasse, maar deze kan eenvoudig worden geïmplementeerd via NSCache (dat een vergelijkbaar, maar niet-gedocumenteerd verdringingsbeleid gebruikt) of via een eigen implementatie op basis van Dictionary + Doubly Linked List, zoals hieronder getoond.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

In deze Swift-implementatie is Node een interne klasse met de velden value, next en prev. De methode moveToHead koppelt het knooppunt los van zijn huidige positie en voegt het in aan het begin van de lijst. Bij overloop wordt tail verwijderd — het meest recent niet gebruikte element. Voor de productieversie wordt aanbevolen om thread-veiligheid toe te voegen via NSLock of een DispatchQueue.