FIFO (First In, First Out)

L'algorithme FIFO repose sur le principe du premier entré, premier sorti. Les éléments sont stockés dans l'ordre d'arrivée. Dès que la capacité maximale est atteinte, l'élément le plus ancien est supprimé pour faire place au nouveau.

import java.util.LinkedList;

public class FIFO {
    private final LinkedList<Integer> queue = new LinkedList<>();
    private final int capacity;

    public FIFO(int capacity) {
        this.capacity = capacity;
    }

    public void put(int key) {
        queue.addFirst(key);
        if (queue.size() > capacity) {
            queue.removeLast();
        }
        display();
    }

    public boolean get(int key) {
        boolean found = queue.contains(key);
        if (found) {
            System.out.println("Élément trouvé : " + key);
        } else {
            System.out.println("Non trouvé : " + key);
        }
        display();
        return found;
    }

    private void display() {
        System.out.println("État du cache : " + queue);
    }

    public static void main(String[] args) {
        FIFO fifo = new FIFO(3);
        System.out.println("Ajout de 1, 2, 3 :");
        fifo.put(1);
        fifo.put(2);
        fifo.put(3);
        System.out.println("Ajout de 4 :");
        fifo.put(4); // 1 est retiré
        System.out.println("Recherche de 2 :");
        fifo.get(2);
        System.out.println("Ajout de 5 :");
        fifo.put(5); // 2 est retiré
    }
}

LRU (Least Recantly Used)

L'algorithme LRU élimine l'élément qui n'a pas été utilisé depuis le plus longtemps. Chaque accès à un élément le déplace vers le début de la liste. Le dernier élément est donc toujours le moins récemment utilisé.

import java.util.LinkedList;

public class LRU {
    private final LinkedList<Integer> recentList = new LinkedList<>();
    private final int capacity;

    public LRU(int capacity) {
        this.capacity = capacity;
    }

    public void put(int key) {
        if (recentList.contains(key)) {
            recentList.remove((Integer) key);
        }
        recentList.addFirst(key);
        if (recentList.size() > capacity) {
            recentList.removeLast();
        }
        display();
    }

    public boolean get(int key) {
        if (recentList.contains(key)) {
            recentList.remove((Integer) key);
            recentList.addFirst(key);
            System.out.println("Trouvé : " + key);
            display();
            return true;
        }
        System.out.println("Non trouvé : " + key);
        display();
        return false;
    }

    private void display() {
        System.out.println("Cache LRU : " + recentList);
    }

    public static void main(String[] args) {
        LRU lru = new LRU(3);
        lru.put(1);
        lru.put(2);
        lru.put(3);
        lru.get(2); // 2 passe en tête
        lru.put(4); // 1 est retiré car le moins récent
        lru.put(5); // 3 est retiré
    }
}

LFU (Least Frequently Used)

LFU se base sur la fréquence d'accès. Chaque élément possède un compteur d'utilisation. En cas de saturation, l'élément avec le compteur le plus bas est supprimé. En cas d'égalité, on peut utiliser le timestamp pour trancher.

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

class CacheEntry implements Comparable<CacheEntry> {
    int key, frequency;
    long lastUsed;

    public CacheEntry(int key) {
        this.key = key;
        this.frequency = 1;
        this.lastUsed = System.currentTimeMillis();
    }

    public void access() {
        this.frequency++;
        this.lastUsed = System.currentTimeMillis();
    }

    @Override
    public int compareTo(CacheEntry other) {
        int freqCompare = Integer.compare(this.frequency, other.frequency);
        return freqCompare != 0 ? freqCompare : Long.compare(this.lastUsed, other.lastUsed);
    }
}

public class LFU {
    private final int capacity;
    private final Map<Integer, Integer> data;
    private final Map<Integer, CacheEntry> frequencyMap;

    public LFU(int capacity) {
        this.capacity = capacity;
        this.data = new HashMap<>();
        this.frequencyMap = new ConcurrentHashMap<>();
    }

    public void put(int key, int value) {
        if (data.containsKey(key)) {
            data.put(key, value);
            frequencyMap.get(key).access();
        } else {
            if (data.size() == capacity) {
                evict();
            }
            data.put(key, value);
            frequencyMap.put(key, new CacheEntry(key));
        }
        printState();
    }

    public Integer get(int key) {
        if (!data.containsKey(key)) {
            System.out.println("Clé non trouvée : " + key);
            printState();
            return null;
        }
        CacheEntry entry = frequencyMap.get(key);
        entry.access();
        System.out.println("Clé trouvée : " + key);
        printState();
        return data.get(key);
    }

    private void evict() {
        CacheEntry victim = frequencyMap.values().stream().min(CacheEntry::compareTo).orElse(null);
        if (victim != null) {
            data.remove(victim.key);
            frequencyMap.remove(victim.key);
            System.out.println("Éviction de : " + victim.key);
        }
    }

    private void printState() {
        System.out.println("Données : " + data);
        System.out.println("Fréquences : " + frequencyMap.values());
    }

    public static void main(String[] args) {
        LFU lfu = new LFU(3);
        lfu.put(1, 1);
        lfu.put(2, 2);
        lfu.put(3, 3);
        lfu.get(1);
        lfu.get(2);
        lfu.put(4, 4); // Évince 3 (fréquence 1)
        lfu.get(2);
        lfu.get(4);
        lfu.put(5, 5); // Évince 1 (fréquence 2 mais plus ancienne)
    }
}