56 - Unit Test multi-threaded LRU cache
@backstreetbrogrammer
--------------------------------------------------------------------------------
Unit Test multi-threaded LRU cache
--------------------------------------------------------------------------------
We will use thread pools with multiple threads to put entries into LRU Cache and assert the values at the end confirming that the cache is thread safe.
Generally, an `ExecutorService` and a `CountDownLatch` can be used for writing unit tests of any testing of multithreaded code / logic / data structure.
The Least Recently Used (LRU) cache is a cache eviction algorithm that organizes elements in order of use. In LRU, as the name suggests, the element that hasn't been used for the longest time will be evicted from the cache.
LRU cache algorithm
1. Inserting (key,value) pair `put(K,V)`:
Create a new linked list node with key, value and insert into head of linked list.
Insert key -: node mapping into hash table.
2. Get value by key `get(K)`:
Lookup node in hash table and return node value.
Then update most recently used item by moving the node to front (head) of linked list.
Hash table does NOT need to be updated.
3. Finding least recently used:
Least recently used item will be found at the end of the linked list.
4. Eviction when cache is full:
Remove tail of linked list.
Get key from linked list node and remove key from hash table.
Github: https://github.com/backstreetbrogramm...
Top Java Coding Interview Problems Playlist: • Top Java Coding Interview Problems
Apache Spark for Java Developers Playlist: • Apache Spark for Java Developers
Upgrade to Java 21 Playlist: • Upgrade to Java 21
Java Serialization Playlist: • Java Serialization
Dynamic Programming Playlist: • Dynamic Programming
#java #javadevelopers #javaprogramming #javacodinginterview