A basic Java implementation of a Least-Recently-Used (LRU) Cache. The cache stores key-value pairs and works with Java generic <K, V> objects. Also included basic functionality tests.
HashMap<K, Node>Node: abstraction representing the node of a doubly-linked list, containingV
The doubly-linked list was implemented using the Node class. Usage of a Java Deque/LinkedList would achieve equivalent functionality and runtime.
Note: Java provides a LinkedHashMap, which could be used as described below to implement a LRU cache without the need to implement the above data structures but this was avoided in my implementation, for learning purposes.
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) // set accessOrder=true to mimic LRU
Both get and set run in O(1) time. This stems from the usage of the HashMap to retrieve the Node storing the value in O(1) time (in case of get) and the doubly-linked list, which allows the reordering of nodes in O(1) time (to update Node positions for get calls and LRU deletion).
- Implement multiple cache layers
- Thread-safe/concurrency support
A basic Java implementation of a Least-Frequently-Used (LFU) Cache using 2 maps storing the value and frequency for a particular key and a mapping between frequencies and keys with those frequencies. It also supports O(1) get and set operations.