cache

A Least Recently Used cache removes the least recently used element when the cache is full. Inserting a new value count as using, and the inserted value count as the most recently used element. It can be implemented by combining a hash map with a double-linked list. It's better to think of the double-linked list as being used to implement the policy and the hash map is here for lookup speed up.

• Whenever a key is being queried, check if the hash map contains the key.
  • If not, then report not found.
  • If yes, then remove the associated element from the linked list and put it to the front of the list. Return the key's associated value.
• Whenever a new element is being cached, check if the element is already in the cache by checking the hash map.
  • If not, check if a slot is available.
    • If available, put the element to the front of the linked list, and insert a new entry associating the key to that element in the hash map.
    • If not available, remove one element from the back of the linked list and delete the associated entry in the hash map; then proceed as if there's been an available slot.
  • If yes, then remove it from the linked list, modify the value and put it to the front of the list.

Lookup is O(1) assuming hash map O(1) lookup (double-linked list move-to-front action is O(1)). Insertion is O(1) assuming hash map O(1) insertion (double-linked list remove-from-back & push-at-front action is O(1)).

---

2025.8.21

Back