LinkedHashMap est une structure de données couramment utilisée en Java. Le cache LruCache dans Android utilise LinkedHashMap en interne. L'algorithme LRU (Least Recently Used) vise à éliminer les objets de cache les moins récemment utilisés lorsque le cache est plein.
Algorithme de cache LruCache
LruCache utilise l'algorithme LRU. L'idée principale est que lorsque le cache est plein, les objets de cache les moins récemment utilisés sont éliminés en priorité.
Implémentation de LruCache
LruCache est implémenté en utilisant LinkedHashMap en arrière-plan. Il fournit les méthodes get et put pour ajouter et récupérer des objets.
Différences entre LinkedHashMap et HashMap
Points communs :
- Ajout et récupération de données sous forme de paires clé-valeur.
- Utilisation d'un tableau en interne pour stocker les données.
Différences :
- HashMap est non ordonné, tandis que LinkedHashMap est ordonné (par ordre d'insertion et par ordre d'accès).
- LinkedHashMap stocke des nœuds dans le tableau, mais ces nœuds contiennent deux pointeurs pour gérer une liste doublement chaînée, garantissant ainsi l'ordre d'insertion ou d'accès.
Utilisation de LinkedHashMap
Démo de l'ordre d'insertion de LinkedHashMap
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Iterator;
public class LinkedHashMapInsertionOrderDemo {
public static void main(String[] args) {
// Par défaut, l'ordre d'insertion est enregistré
Map<String, String> map = new LinkedHashMap<>();
map.put("name", "tom");
map.put("age", "34");
map.put("address", "beijing");
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
// Parcours
while (iterator.hasNext()) {
Map.Entry<String, String> entry = iterator.next();
String key = entry.getKey();
String value = entry.getValue();
System.out.println("Key = " + key + ", Value = " + value);
}
}
}
Sortie :
Key = name, Value = tom
Key = age, Value = 34
Key = address, Value = beijing
La sortie montre que les éléments ont été parcourus dans l'ordre où ils ont été insérés. LinkedHashMap enregistre par défaut l'ordre d'insertion.
Comparons avec le parcours de HashMap :
import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;
public class HashMapTraversalDemo {
public static void main(String[] args) {
// Insertion des mêmes valeurs qu'auparavant
Map<String, String> map = new HashMap<>();
map.put("name", "tom");
map.put("age", "34");
map.put("address", "beijing");
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
// Parcours
while (iterator.hasNext()) {
Map.Entry<String, String> entry = iterator.next();
String key = entry.getKey();
String value = entry.getValue();
System.out.println("Key = " + key + ", Value = " + value);
}
}
}
Sortie :
Key = address, Value = beijing
Key = name, Value = tom
Key = age, Value = 34
On constate que le parcours de HashMap n'est pas ordonné et n'a pas de relation avec l'ordre d'insertion.
Démo de l'ordre d'accès de LinkedHashMap
LinkedHashMap peut également enregistrer l'ordre d'accès. Les éléments récemment consultés sont placés en tête de la liste.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Iterator;
public class LinkedHashMapAccessOrderDemo {
public static void main(String[] args) {
/**
* Premier paramètre : taille du tableau
* Deuxième paramètre : facteur de charge (similaire à HashMap, l'expansion commence lorsque le nombre d'éléments ajoutés atteint 16 * 0.75)
* Troisième paramètre : true : enregistre l'ordre d'accès
* false : enregistre l'ordre d'insertion (comportement par défaut)
*/
Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
// Insertion des valeurs suivantes
map.put("name", "tom");
map.put("age", "34");
map.put("address", "beijing");
// Pour démontrer l'ordre d'accès, consultons un élément (ici, juste pour l'impression)
System.out.println("Élément accédé : " + map.get("age"));
// Après l'accès, parcourons à nouveau pour observer l'ordre de sortie
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
// Parcours
while (iterator.hasNext()) {
Map.Entry<String, String> entry = iterator.next();
String key = entry.getKey();
String value = entry.getValue();
System.out.println("Key = " + key + ", Value = " + value);
}
}
}
Sortie :
Élément accédé : 34
Key = name, Value = tom
Key = address, Value = beijing
Key = age, Value = 34
Après l'insertion, nous avons accédé à "age". Lors du parcours, comme l'ordre d'accès est enregistré, LinkedHashMap déplace l'élément le plus récemment utilisé vers la fin. Ainsi, bien que "age" ait été inséré en deuxième position, il apparaît en dernier lors du parcours.
LruCache utilise cette propriété de LinkedHashMap : les éléments les plus récemment utilisés sont placés à la fin. Les éléments moins récemment utilisés se retrouvent naturellement au début. Lors de l'élimination en cas de cache plein, ce sont les éléments du début qui sont supprimés. Les nouveaux éléments sont ajoutés à la fin.
Pirncipes de LinkedHashMap
LinkedHashMap combine HashMap et une liste chaînée. Il utilise un tableau en interne pour stocker les éléments et une liste chaînée pour maintenir l'ordre d'insertion.
Représentation visuelle
(Une image illustrant la structure interne de LinkedHashMap, montrant le tableau, les nœuds avec les pointeurs next, before et after, ainsi que la liste doublement chaînée gérée par le header, serait placée ici si elle était disponible.)
Implémentation personnalisée : QLinkedHashMap
Nous allons implémenter une structure similaire nommée QLinkedHashMap.
Structure du nœud : QEntry
static class QEntry<K, V> {
public K key; // Clé
public V value; // Valeur
public int hash; // Hash de la clé
public QEntry<K, V> next; // Pour gérer les collisions de hash (liste chaînée simple)
public QEntry<K, V> before; // Nœud précédent dans la liste doublement chaînée
public QEntry<K, V> after; // Nœud suivant dans la liste doublement chaînée
QEntry(K key, V value, int hash, QEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
// Supprime le nœud actuel de la liste
private void remove() {
this.before.after = after;
this.after.before = before;
}
// Insère le nœud actuel avant existingEntry
private void addBefore(QEntry<K, V> existingEntry) {
this.after = existingEntry;
this.before = existingEntry.before;
this.after.before = this;
this.before.after = this;
}
// Appelé lors de l'accès au nœud, gère l'ordre d'accès/insertion
void recordAccess(QLinkedHashMap<K, V> m) {
QLinkedHashMap<K, V> lm = (QLinkedHashMap<K, V>) m;
if (lm.accessOrder) {
remove();
addBefore(lm.header); // Ajoute à la fin de la liste doublement chaînée
}
}
}
QLinkedHashMap : classe princpiale
La liste chaînée utilisée est une liste doublement chaînée circulaire. Le nœud header pointe vers le dernier nœud via before et vers lui-même via after en cas de liste vide.
import java.util.Iterator;
public class QLinkedHashMap<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private QEntry[] table; // Tableau sous-jacent
private int size; // Nombre d'éléments
private boolean accessOrder; // true pour ordre d'accès, false pour ordre d'insertion
private QEntry<K, V> header; // Tête de la liste doublement chaînée circulaire
public QLinkedHashMap() {
table = new QEntry[DEFAULT_INITIAL_CAPACITY];
size = 0;
accessOrder = false; // Par défaut, ordre d'insertion
init();
}
/**
* Constructeur avec capacité et ordre d'accès spécifiés.
* @param capacity Capacité initiale du tableau.
* @param accessOrder true pour l'ordre d'accès, false pour l'ordre d'insertion.
*/
public QLinkedHashMap(int capacity, boolean accessOrder) {
table = new QEntry[capacity];
size = 0;
this.accessOrder = accessOrder;
init();
}
// Initialise la liste doublement chaînée circulaire
private void init() {
header = new QEntry<>(null, null, -1, null);
header.after = header;
header.before = header;
}
// Ajoute une paire clé-valeur
public V put(K key, V value) {
if (key == null) throw new IllegalArgumentException("La clé ne peut pas être nulle");
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
// Vérifie si la clé existe déjà
QEntry<K, V> e = table[index];
while (e != null) {
if (e.hash == hash && (key == e.key || key.equals(e.key))) {
V oldValue = e.value;
e.value = value;
// Enregistre l'accès si l'ordre d'accès est activé
e.recordAccess(this);
return oldValue;
}
e = e.next;
}
// Ajoute un nouveau nœud
QEntry<K, V> next = table[index];
QEntry<K, V> newEntry = new QEntry(key, value, hash, next);
table[index] = newEntry;
// Ajoute le nouveau nœud à la fin de la liste doublement chaînée
newEntry.addBefore(header);
size++;
// L'implémentation de l'expansion n'est pas incluse ici.
return null;
}
// Récupère la valeur associée à une clé
public V get(K key) {
if (key == null) throw new IllegalArgumentException("La clé ne peut pas être nulle");
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
QEntry<K, V> e = table[index];
while (e != null) {
if (hash == e.hash && (key == e.key || key.equals(e.key))) {
// Enregistre l'accès lors de la récupération
e.recordAccess(this);
return e.value;
}
e = e.next;
}
return null; // Clé non trouvée
}
// Retourne un itérateur pour parcourir la map
public QIterator iterator() {
return new QIterator(header);
}
// Calcule l'index dans le tableau
static int indexFor(int h, int length) {
// h & (length - 1) est plus performant si length est une puissance de 2
return Math.abs(h) % length;
}
// Fonction de hachage (similaire à HashMap)
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// Itérateur pour parcourir la liste doublement chaînée
public class QIterator {
QEntry<K,V> header;
QEntry<K,V> p; // Pointeur courant
public QIterator(QEntry header){
this.header = header;
this.p = header.after; // Commence après le header
}
// Vérifie s'il y a un prochain élément
public boolean hasNext() {
return p != header; // Tant que le pointeur n'est pas revenu au header
}
// Retourne le prochain élément
public QEntry next() {
QEntry r = p;
p = p.after; // Avance le pointeur
return r;
}
}
// Définition interne du nœud
static class QEntry<K, V> {
public K key;
public V value;
public int hash;
public QEntry<K, V> next; // Pour les collisions de hash
public QEntry<K, V> before; // Nœud précédent
public QEntry<K, V> after; // Nœud suivant
QEntry(K key, V value, int hash, QEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
// Supprime le nœud actuel
private void remove() {
this.before.after = after;
this.after.before = before;
}
// Insère le nœud actuel avant existingEntry
private void addBefore(QEntry<K, V> existingEntry) {
this.after = existingEntry;
this.before = existingEntry.before;
this.after.before = this;
this.before.after = this;
}
// Gère l'ordre d'accès
void recordAccess(QLinkedHashMap<K, V> m) {
QLinkedHashMap<K, V> lm = (QLinkedHashMap<K, V>) m;
if (lm.accessOrder) {
remove();
addBefore(lm.header); // Déplace vers la fin (avant le header)
}
}
}
}
Tests de QLinkedHashMap
Test de l'ordre d'insertion
public class QLinkedHashMapInsertionTest {
public static void main(String[] args) {
// Création avec l'ordre d'insertion par défaut
QLinkedHashMap<String, String> map = new QLinkedHashMap<>();
map.put("name", "tom");
map.put("age", "32");
map.put("address", "beijing");
// Vérification de l'ordre d'insertion
QLinkedHashMap.QIterator iterator = map.iterator();
while (iterator.hasNext()) {
QLinkedHashMap.QEntry e = iterator.next();
System.out.println("key=" + e.key + " value=" + e.value);
}
}
}
Sortie :
key=name value=tom
key=age value=32
key=address value=beijing
La sortie confirme l'ordre d'insertion.
Test de l'ordre d'accès
public class QLinkedHashMapAccessTest {
public static void main(String[] args) {
// Création avec l'ordre d'accès activé
QLinkedHashMap<String, String> map = new QLinkedHashMap<>(16, true);
map.put("name", "tom");
map.put("age", "32");
map.put("address", "beijing");
// Accès à l'élément "age"
map.get("age");
// Vérification de l'ordre d'accès ("age" devrait être le dernier)
QLinkedHashMap.QIterator iterator = map.iterator();
while (iterator.hasNext()) {
QLinkedHashMap.QEntry e = iterator.next();
System.out.println("key=" + e.key + " value=" + e.value);
}
}
}
Sortie :
key=name value=tom
key=address value=beijing
key=age value=32
La sortie démontre que l'élément accédé ("age") a été déplacé à la fin, confirmant l'implémentation de l'ordre d'accès.
Bien que les fonctionnalités d'expansion et de suppression ne soient pas incluses, cette implémentation illustre les principes fondamentaux de LinkedHashMap.