staba viendo este problema de implementación de caché LRU donde, después de que el tamaño del caché está lleno, el elemento utilizado menos recientemente aparece y se reemplaza por el nuevo elemento.

Tengo dos implementaciones en mente:

1). Cree dos mapas que se vean algo como esto

std::map<timestamp, k> time_to_key
std::map<key, std::pair<timestamp, V>> LRUCache

Para insertar un nuevo elemento, podemos poner la marca de tiempo y el valor actual en la LRUCache. Mientras que cuando el tamaño del caché está lleno, podemos desalojar el elemento menos reciente al encontrar la marca de tiempo más pequeña presente enhor_allav y eliminando la clave correspondiente de LRUCache. Insertar un nuevo elemento es O (1), actualizar la marca de tiempo es O (n) (porque necesitamos buscar lak correspondiente a la marca de tiempo enhor_allav.

2). Tenga una lista vinculada en la que el caché utilizado menos recientemente esté presente en la cabecera y el nuevo elemento se agregue en la cola. Cuando llega un elemento que ya está presente en la memoria caché, el nodo correspondiente a la clave de ese elemento se mueve al final de la lista. Insertar un nuevo elemento es O (1), actualizar la marca de tiempo nuevamente es O (n) (porque necesitamos movernos al final de la lista), y eliminar un elemento es O (1).

Ahora tengo las siguientes preguntas:

Cuál de estas implementaciones es mejor para un LRUCache.

Hay alguna otra forma de implementar la caché LRU.

En Java, ¿debería usar HashMap para implementar LRUCache

He visto preguntas como implementar un caché LRU genérico y también he visto preguntas como implementar un caché LRU. ¿La memoria caché genérica LRU es diferente de la memoria caché LRU?

¡¡¡Gracias por adelantado!!

EDITAR

Otra forma (la forma más fácil) de implementar LRUCache en Java es mediante LinkedHashMap y anulando la función booleana removeEldestEntry (Map.entry eldest).