Cache Implementations

Relevant source files

• src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java
• src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java
• src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java
• src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java
• src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java
• src/test/java/com/thealgorithms/datastructures/caches/LRUCacheTest.java
• src/test/java/com/thealgorithms/datastructures/caches/MRUCacheTest.java
• src/test/java/com/thealgorithms/datastructures/crdt/LWWElementSetTest.java

This page documents the various cache implementation data structures available in the repository. Caches are optimized temporary storage mechanisms that improve performance by keeping frequently or recently accessed data readily available. This documentation covers the different cache eviction policies implemented in the codebase and explains their internal workings, usage patterns, and performance characteristics.

Overview of Caching Mechanisms

The repository implements three primary cache strategies, each with different eviction policies:

1. LFU (Least Frequently Used): Evicts items that are used least frequently.
2. LRU (Least Recently Used): Evicts items that haven't been accessed for the longest time.
3. MRU (Most Recently Used): Evicts the most recently used items first.

Additionally, related probabilistic and distributed data structures are documented:

• Bloom Filter: Space-efficient probabilistic data structure for membership testing.
• LWW Element Set: Conflict-free replicated data type (CRDT) that uses timestamps to manage concurrent operations.

Cache Architecture Diagram

Sources: src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java26 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java42 src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java19 src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java23

Cache Eviction Policies

When a cache reaches its capacity, it must remove (evict) existing entries to make room for new ones. The strategy used to decide which entries to remove is called the eviction policy.

The following table compares the different eviction strategies implemented in the repository:

Cache Type	Eviction Policy	Best Use Cases	Implementation
LFU Cache	Removes the least frequently accessed items first	When access frequency matters more than recency	Uses a frequency counter and a doubly-linked list
LRU Cache	Removes the least recently accessed items first	General purpose caching with temporal locality	Uses a doubly-linked list to track access order
MRU Cache	Removes the most recently accessed items first	When older items are more likely to be accessed again	Similar to LRU but with inverse eviction logic

Sources: src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java7-11 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java7-12 src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java7-11

LFU Cache (Least Frequently Used)

The LFU Cache evicts the least frequently used items when it reaches capacity. Each item has a frequency counter that increases when the item is accessed. When the cache is full and a new item needs to be added, the item with the lowest frequency count is evicted src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java101-103

Internal Structure

Sources: src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java33-52 src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java54-57

Implementation Details

The LFUCache class provides O(1) time complexity for both get and put operations by using a HashMap for quick access and a doubly linked list for maintaining frequency order src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java13-15

• get(K key): Retrieves the value, increments the node's frequency, and repositions it in the list src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java89-98
• put(K key, V value): Updates existing keys or inserts new ones. If full, it evicts this.head.key (the least frequently used item) src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java108-124
• addNodeWithUpdatedFrequency(Node node): Re-inserts a node into the doubly linked list such that the list remains ordered by frequency, with the head being the least frequently used src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java132-159

Sources: src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java89-184

LRU Cache (Least Recently Used)

The LRU Cache evicts the least recently used items when it reaches capacity. Each time an item is accessed, it's moved to the "most recently used" position (the tail) src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java25-26

Internal Structure

Sources: src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java42-48 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java186-234

Implementation Details

The LRUCache uses a HashMap for O(1) lookups and a doubly-linked list for tracking access order src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java23-24

• get(K key): If the key exists, it calls moveNodeToLast(entry) and returns the value src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java107-114
• put(K key, V value): If the cache is at capacity (data.size() == cap), it calls evict() to remove the head entry before adding the new one src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java148-167
• evict(): Removes the head node, which represents the least recently used item src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java77-86

Sources: src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java77-184

MRU Cache (Most Recently Used)

The MRU Cache evicts the most recently accessed items first. This strategy is useful in scenarios where the most recently used data is the least likely to be needed again in the immediate future src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java9-11

Implementation Details

The MRUCache structure is identical to the LRUCache but modifies the evict() logic.

• evict(): In MRUCache, this method removes the tail node, which represents the most recently used item src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java76-87
• put(K key, V value): When capacity is reached, the most recent entry is evicted before the new entry is added to the tail src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java112-130

Sources: src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java76-87 src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java112-130

LWW Element Set (Last-Write-Wins)

The LWWElementSet is a state-based Conflict-free Replicated Data Type (CRDT) designed for distributed environments. It uses timestamps to resolve conflicts between concurrent additions and removals src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java8-13

Logic and Conflict Resolution

• add(T key): Adds the element to addSet with Instant.now() src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java44-46
• remove(T key): Adds the element to removeSet with Instant.now() src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java54-56
• lookup(T key): An element is present if it is in the addSet and either not in the removeSet or its add timestamp is strictly after the remove timestamp src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java68-73
• merge(LWWElementSet other): Combines two sets by taking the union of their add/remove sets and keeping the latest timestamp for each key via resolveConflict src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java83-90

Sources: src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java23-104

Performance Summary

Operation	LFU Cache	LRU Cache	MRU Cache	LWW Set
Lookup (get)	O(1) src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java13	O(1) src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java11	O(1)	O(1)
Insertion (put)	O(1) src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java13	O(1) src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java11	O(1)	O(1)
Eviction	O(n) (list search)*	O(1) (head)	O(1) (tail)	N/A

* Note: While LFUCache claims O(1), the current implementation of addNodeWithUpdatedFrequency iterates through the list to find the correct frequency position, which can be O(n) in the worst case src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java132-159

Sources: src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java13-15 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java11-12 src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java68-73