LRU_HASH es una estructura de datos híbrida diseñada para implementar una política de desalojo de caché 'Least Recently Used' (LRU) de forma eficiente. Combina una tabla hash (hash map) y una lista doblemente enlazada (doubly linked list). La tabla hash se utiliza para almacenar las claves de los elementos y sus referencias a los nodos de la lista enlazada, permitiendo un acceso rápido (O(1) en promedio) a cualquier elemento por su clave. La lista doblemente enlazada mantiene los elementos en orden de uso reciente, donde los elementos más recientemente accedidos o insertados se mueven al 'frente' (cabeza) de la lista, y los menos recientemente usados se encuentran al 'final' (cola). Cuando la caché alcanza su capacidad máxima y se necesita insertar un nuevo elemento, el elemento en la cola de la lista (el LRU) es desalojado.
La implementación de LRU_HASH es fundamental en numerosos sistemas de software de alto rendimiento. Por ejemplo, los sistemas operativos utilizan cachés LRU para la gestión de páginas de memoria virtual y cachés de archivos (filesystem caches) para optimizar el acceso a disco. Bases de datos como MySQL (InnoDB buffer pool) y PostgreSQL (shared buffer cache) emplean variantes de LRU para gestionar sus bloques de datos en memoria. Servidores web y proxies como Nginx y Varnish Cache utilizan cachés LRU para almacenar contenido estático y dinámico, reduciendo la latencia y la carga en los servidores de origen. También es común en cachés de aplicaciones distribuidas como Redis (cuando se configura con una política LRU) y en la gestión de cachés de CPU a nivel de hardware.
Para un arquitecto de sistemas, LRU_HASH es una herramienta esencial para optimizar el rendimiento y la escalabilidad. Su valor estratégico radica en su capacidad para reducir la latencia de acceso a datos y la carga en recursos más lentos (como discos o redes) al mantener los datos más relevantes en memoria. Sin embargo, su implementación implica trade-offs: requiere memoria adicional para la estructura de la lista enlazada y la tabla hash, y el rendimiento puede degradarse si la función hash no es eficiente o si hay una alta contención de bloqueos en entornos concurrentes. La elección del tamaño de la caché es crítica; una caché demasiado pequeña resultará en 'cache misses' frecuentes, mientras que una demasiado grande consumirá excesiva memoria. Los arquitectos deben considerar cuidadosamente la relación entre la frecuencia de acceso, el tamaño de los elementos, la capacidad de memoria disponible y la política de desalojo más adecuada para cada caso de uso, a menudo explorando variantes como LRU-K o 2Q para escenarios más complejos.