Data Structures
LRU Cache:Hash Map Plus Doubly Linked List as One Machine
Least-recently-used eviction is O(1) only when a hash map points at nodes of a doubly linked list. How the two layouts share the work, and LinkedHashMap as the JDK shortcut.
Read More