EMZETT.LRU cache
In short: An LRU cache (“least recently used”) stores only a limited number of entries and evicts the entry unused for the longest time when space runs out.
In more detail: The idea: what was used recently will probably be needed again soon. For fast operations, you combine a hash table (O(1) access) with a doubly linked list (order of use).
In Depth
- Read: Find the entry via the hash table and move it to the front (“most recently used”) of the list.
- Write: A new entry goes to the front. If capacity is exceeded, the end of the list is removed.
- Alternatives: LFU (least frequently used), FIFO (oldest), random eviction.
- Use: Browser cache, database buffer, operating system page cache,
lru_cachein Python. - Pitfall: A single large scan can flush the whole cache (“cache pollution”).