Repository: TheAlgorithms/Java
Pull request #6337 (2025-07-03 20:02:55)

Add cache with FIFO replacement policy
### Description
This PR adds a reusable FIFOCache implementation with the following features:
- Fixed size FIFO eviction policy using `LinkedHashMap`
- Time to live (TTL)
- Thread-safe operations using ReentrantLock
- Pluggable EvictionStrategy to control expired entry cleanup
- Eviction listener callback support for observing removals
- Hit and miss statistics tracking
-  Builder for flexible configuration

<!-- For completed items, change [ ] to [x] -->
### Checklist
- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6337?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `94.55782%` with `8 lines` in your changes missing coverage. Please review.
> Project coverage is 74.49%. Comparing base [(`712ada5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/712ada5102be82b4807b0737ad70cfc0bca37935?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`dccf3c1`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/dccf3c1a5c86c0cd834b81dfbe079e4f5bb64477?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6337?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...thealgorithms/datastructures/caches/FIFOCache.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6337?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fcaches%2FFIFOCache.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9jYWNoZXMvRklGT0NhY2hlLmphdmE=) | 94.55% | [2 Missing and 6 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6337?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6337      +/-   ##
============================================
+ Coverage     74.33%   74.49%   +0.15%     
- Complexity     5392     5424      +32     
============================================
  Files           679      680       +1     
  Lines         18820    18967     +147     
  Branches       3646     3670      +24     
============================================
+ Hits          13990    14129     +139     
- Misses         4274     4276       +2     
- Partials        556      562       +6     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6337?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary> :rocket: New features to boost your workflow: </summary>

- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/caches/FIFOCache.java b/src/main/java/com/thealgorithms/datastructures/caches/FIFOCache.java
new file mode 100644
index 00000000..fa048434
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/caches/FIFOCache.java
@@ -0,0 +1,549 @@
+package com.thealgorithms.datastructures.caches;
+
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.BiConsumer;
+
+/**
+ * A thread-safe generic cache implementation using the First-In-First-Out eviction policy.
+ * <p>
+ * The cache holds a fixed number of entries, defined by its capacity. When the cache is full and a
+ * new entry is added, the oldest entry in the cache is selected and evicted to make space.
+ * <p>
+ * Optionally, entries can have a time-to-live (TTL) in milliseconds. If a TTL is set, entries will
+ * automatically expire and be removed upon access or insertion attempts.
+ * <p>
+ * Features:
+ * <ul>
+ *     <li>Removes oldest entry when capacity is exceeded</li>
+ *     <li>Optional TTL (time-to-live in milliseconds) per entry or default TTL for all entries</li>
+ *     <li>Thread-safe access using locking</li>
+ *     <li>Hit and miss counters for cache statistics</li>
+ *     <li>Eviction listener callback support</li>
+ * </ul>
+ *
+ * @param <K> the type of keys maintained by this cache
+ * @param <V> the type of mapped values
+ * See <a href="https://en.wikipedia.org/wiki/Cache_replacement_policies#First_in_first_out_(FIFO)">FIFO</a>
+ * @author Kevin Babu (<a href="https://www.github.com/KevinMwita7">GitHub</a>)
+ */
+public final class FIFOCache<K, V> {
+
+    private final int capacity;
+    private final long defaultTTL;
+    private final Map<K, CacheEntry<V>> cache;
+    private final Lock lock;
+
+    private long hits = 0;
+    private long misses = 0;
+    private final BiConsumer<K, V> evictionListener;
+    private final EvictionStrategy<K, V> evictionStrategy;
+
+    /**
+     * Internal structure to store value + expiry timestamp.
+     *
+     * @param <V> the type of the value being cached
+     */
+    private static class CacheEntry<V> {
+        V value;
+        long expiryTime;
+
+        /**
+         * Constructs a new {@code CacheEntry} with the specified value and time-to-live (TTL).
+         * If TTL is 0, the entry is kept indefinitely, that is, unless it is the first value,
+         * then it will be removed according to the FIFO principle
+         *
+         * @param value     the value to cache
+         * @param ttlMillis the time-to-live in milliseconds
+         */
+        CacheEntry(V value, long ttlMillis) {
+            this.value = value;
+            if (ttlMillis == 0) {
+                this.expiryTime = Long.MAX_VALUE;
+            } else {
+                this.expiryTime = System.currentTimeMillis() + ttlMillis;
+            }
+        }
+
+        /**
+         * Checks if the cache entry has expired.
+         *
+         * @return {@code true} if the current time is past the expiration time; {@code false} otherwise
+         */
+        boolean isExpired() {
+            return System.currentTimeMillis() > expiryTime;
+        }
+    }
+
+    /**
+     * Constructs a new {@code FIFOCache} instance using the provided {@link Builder}.
+     *
+     * <p>This constructor initializes the cache with the specified capacity and default TTL,
+     * sets up internal data structures (a {@code LinkedHashMap} for cache entries and configures eviction.
+     *
+     * @param builder the {@code Builder} object containing configuration parameters
+     */
+    private FIFOCache(Builder<K, V> builder) {
+        this.capacity = builder.capacity;
+        this.defaultTTL = builder.defaultTTL;
+        this.cache = new LinkedHashMap<>();
+        this.lock = new ReentrantLock();
+        this.evictionListener = builder.evictionListener;
+        this.evictionStrategy = builder.evictionStrategy;
+    }
+
+    /**
+     * Retrieves the value associated with the specified key from the cache.
+     *
+     * <p>If the key is not present or the corresponding entry has expired, this method
+     * returns {@code null}. If an expired entry is found, it will be removed and the
+     * eviction listener (if any) will be notified. Cache hit-and-miss statistics are
+     * also updated accordingly.
+     *
+     * @param key the key whose associated value is to be returned; must not be {@code null}
+     * @return the cached value associated with the key, or {@code null} if not present or expired
+     * @throws IllegalArgumentException if {@code key} is {@code null}
+     */
+    public V get(K key) {
+        if (key == null) {
+            throw new IllegalArgumentException("Key must not be null");
+        }
+
+        lock.lock();
+        try {
+            evictionStrategy.onAccess(this);
+
+            CacheEntry<V> entry = cache.get(key);
+            if (entry == null || entry.isExpired()) {
+                if (entry != null) {
+                    cache.remove(key);
+                    notifyEviction(key, entry.value);
+                }
+                misses++;
+                return null;
+            }
+            hits++;
+            return entry.value;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Adds a key-value pair to the cache using the default time-to-live (TTL).
+     *
+     * <p>The key may overwrite an existing entry. The actual insertion is delegated
+     * to the overloaded {@link #put(K, V, long)} method.
+     *
+     * @param key   the key to cache the value under
+     * @param value the value to be cached
+     */
+    public void put(K key, V value) {
+        put(key, value, defaultTTL);
+    }
+
+    /**
+     * Adds a key-value pair to the cache with a specified time-to-live (TTL).
+     *
+     * <p>If the key already exists, its value is removed, re-inserted at tail and its TTL is reset.
+     * If the key does not exist and the cache is full, the oldest entry is evicted to make space.
+     * Expired entries are also cleaned up prior to any eviction. The eviction listener
+     * is notified when an entry gets evicted.
+     *
+     * @param key        the key to associate with the cached value; must not be {@code null}
+     * @param value      the value to be cached; must not be {@code null}
+     * @param ttlMillis  the time-to-live for this entry in milliseconds; must be >= 0
+     * @throws IllegalArgumentException if {@code key} or {@code value} is {@code null}, or if {@code ttlMillis} is negative
+     */
+    public void put(K key, V value, long ttlMillis) {
+        if (key == null || value == null) {
+            throw new IllegalArgumentException("Key and value must not be null");
+        }
+        if (ttlMillis < 0) {
+            throw new IllegalArgumentException("TTL must be >= 0");
+        }
+
+        lock.lock();
+        try {
+            // If key already exists, remove it
+            CacheEntry<V> oldEntry = cache.remove(key);
+            if (oldEntry != null && !oldEntry.isExpired()) {
+                notifyEviction(key, oldEntry.value);
+            }
+
+            // Evict expired entries to make space for new entry
+            evictExpired();
+
+            // If no expired entry was removed, remove the oldest
+            if (cache.size() >= capacity) {
+                Iterator<Map.Entry<K, CacheEntry<V>>> it = cache.entrySet().iterator();
+                if (it.hasNext()) {
+                    Map.Entry<K, CacheEntry<V>> eldest = it.next();
+                    it.remove();
+                    notifyEviction(eldest.getKey(), eldest.getValue().value);
+                }
+            }
+
+            // Insert new entry at tail
+            cache.put(key, new CacheEntry<>(value, ttlMillis));
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Removes all expired entries from the cache.
+     *
+     * <p>This method iterates through the list of cached keys and checks each associated
+     * entry for expiration. Expired entries are removed the cache map. For each eviction,
+     * the eviction listener is notified.
+     */
+    private int evictExpired() {
+        int count = 0;
+        Iterator<Map.Entry<K, CacheEntry<V>>> it = cache.entrySet().iterator();
+
+        while (it.hasNext()) {
+            Map.Entry<K, CacheEntry<V>> entry = it.next();
+            if (entry != null && entry.getValue().isExpired()) {
+                it.remove();
+                notifyEviction(entry.getKey(), entry.getValue().value);
+                count++;
+            }
+        }
+
+        return count;
+    }
+
+    /**
+     * Removes the specified key and its associated entry from the cache.
+     *
+     * @param key the key to remove from the cache;
+     * @return the value associated with the key;  or {@code null} if no such key exists
+     */
+    public V removeKey(K key) {
+        if (key == null) {
+            throw new IllegalArgumentException("Key cannot be null");
+        }
+        CacheEntry<V> entry = cache.remove(key);
+
+        // No such key in cache
+        if (entry == null) {
+            return null;
+        }
+
+        notifyEviction(key, entry.value);
+        return entry.value;
+    }
+
+    /**
+     * Notifies the eviction listener, if one is registered, that a key-value pair has been evicted.
+     *
+     * <p>If the {@code evictionListener} is not {@code null}, it is invoked with the provided key
+     * and value. Any exceptions thrown by the listener are caught and logged to standard error,
+     * preventing them from disrupting cache operations.
+     *
+     * @param key   the key that was evicted
+     * @param value the value that was associated with the evicted key
+     */
+    private void notifyEviction(K key, V value) {
+        if (evictionListener != null) {
+            try {
+                evictionListener.accept(key, value);
+            } catch (Exception e) {
+                System.err.println("Eviction listener failed: " + e.getMessage());
+            }
+        }
+    }
+
+    /**
+     * Returns the number of successful cache lookups (hits).
+     *
+     * @return the number of cache hits
+     */
+    public long getHits() {
+        lock.lock();
+        try {
+            return hits;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Returns the number of failed cache lookups (misses), including expired entries.
+     *
+     * @return the number of cache misses
+     */
+    public long getMisses() {
+        lock.lock();
+        try {
+            return misses;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Returns the current number of entries in the cache, excluding expired ones.
+     *
+     * @return the current cache size
+     */
+    public int size() {
+        lock.lock();
+        try {
+            evictionStrategy.onAccess(this);
+
+            int count = 0;
+            for (CacheEntry<V> entry : cache.values()) {
+                if (!entry.isExpired()) {
+                    ++count;
+                }
+            }
+            return count;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Removes all entries from the cache, regardless of their expiration status.
+     *
+     * <p>This method clears the internal cache map entirely, resets the hit-and-miss counters,
+     * and notifies the eviction listener (if any) for each removed entry.
+     * Note that expired entries are treated the same as active ones for the purpose of clearing.
+     *
+     * <p>This operation acquires the internal lock to ensure thread safety.
+     */
+    public void clear() {
+        lock.lock();
+        try {
+            for (Map.Entry<K, CacheEntry<V>> entry : cache.entrySet()) {
+                notifyEviction(entry.getKey(), entry.getValue().value);
+            }
+            cache.clear();
+            hits = 0;
+            misses = 0;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Returns a set of all keys currently stored in the cache that have not expired.
+     *
+     * <p>This method iterates through the cache and collects the keys of all non-expired entries.
+     * Expired entries are ignored but not removed. If you want to ensure expired entries are cleaned up,
+     * consider invoking {@link EvictionStrategy#onAccess(FIFOCache)} or calling {@link #evictExpired()} manually.
+     *
+     * <p>This operation acquires the internal lock to ensure thread safety.
+     *
+     * @return a set containing all non-expired keys currently in the cache
+     */
+    public Set<K> getAllKeys() {
+        lock.lock();
+        try {
+            Set<K> keys = new LinkedHashSet<>();
+
+            for (Map.Entry<K, CacheEntry<V>> entry : cache.entrySet()) {
+                if (!entry.getValue().isExpired()) {
+                    keys.add(entry.getKey());
+                }
+            }
+
+            return keys;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * Returns the current {@link EvictionStrategy} used by this cache instance.
+
+     * @return the eviction strategy currently assigned to this cache
+     */
+    public EvictionStrategy<K, V> getEvictionStrategy() {
+        return evictionStrategy;
+    }
+
+    /**
+     * Returns a string representation of the cache, including metadata and current non-expired entries.
+     *
+     * <p>The returned string includes the cache's capacity, current size (excluding expired entries),
+     * hit-and-miss counts, and a map of all non-expired key-value pairs. This method acquires a lock
+     * to ensure thread-safe access.
+     *
+     * @return a string summarizing the state of the cache
+     */
+    @Override
+    public String toString() {
+        lock.lock();
+        try {
+            Map<K, V> visible = new LinkedHashMap<>();
+            for (Map.Entry<K, CacheEntry<V>> entry : cache.entrySet()) {
+                if (!entry.getValue().isExpired()) {
+                    visible.put(entry.getKey(), entry.getValue().value);
+                }
+            }
+            return String.format("Cache(capacity=%d, size=%d, hits=%d, misses=%d, entries=%s)", capacity, visible.size(), hits, misses, visible);
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * A strategy interface for controlling when expired entries are evicted from the cache.
+     *
+     * <p>Implementations decide whether and when to trigger {@link FIFOCache#evictExpired()} based
+     * on cache usage patterns. This allows for flexible eviction behaviour such as periodic cleanup,
+     * or no automatic cleanup.
+     *
+     * @param <K> the type of keys maintained by the cache
+     * @param <V> the type of cached values
+     */
+    public interface EvictionStrategy<K, V> {
+        /**
+         * Called on each cache access (e.g., {@link FIFOCache#get(Object)}) to optionally trigger eviction.
+         *
+         * @param cache the cache instance on which this strategy is applied
+         * @return the number of expired entries evicted during this access
+         */
+        int onAccess(FIFOCache<K, V> cache);
+    }
+
+    /**
+     * An eviction strategy that performs eviction of expired entries on each call.
+     *
+     * @param <K> the type of keys
+     * @param <V> the type of values
+     */
+    public static class ImmediateEvictionStrategy<K, V> implements EvictionStrategy<K, V> {
+        @Override
+        public int onAccess(FIFOCache<K, V> cache) {
+            return cache.evictExpired();
+        }
+    }
+
+    /**
+     * An eviction strategy that triggers eviction on every fixed number of accesses.
+     *
+     * <p>This deterministic strategy ensures cleanup occurs at predictable intervals,
+     * ideal for moderately active caches where memory usage is a concern.
+     *
+     * @param <K> the type of keys
+     * @param <V> the type of values
+     */
+    public static class PeriodicEvictionStrategy<K, V> implements EvictionStrategy<K, V> {
+        private final int interval;
+        private final AtomicInteger counter = new AtomicInteger();
+
+        /**
+         * Constructs a periodic eviction strategy.
+         *
+         * @param interval the number of accesses between evictions; must be > 0
+         * @throws IllegalArgumentException if {@code interval} is less than or equal to 0
+         */
+        public PeriodicEvictionStrategy(int interval) {
+            if (interval <= 0) {
+                throw new IllegalArgumentException("Interval must be > 0");
+            }
+            this.interval = interval;
+        }
+
+        @Override
+        public int onAccess(FIFOCache<K, V> cache) {
+            if (counter.incrementAndGet() % interval == 0) {
+                return cache.evictExpired();
+            }
+
+            return 0;
+        }
+    }
+
+    /**
+     * A builder for constructing a {@link FIFOCache} instance with customizable settings.
+     *
+     * <p>Allows configuring capacity, default TTL, eviction listener, and a pluggable eviction
+     * strategy. Call {@link #build()} to create the configured cache instance.
+     *
+     * @param <K> the type of keys maintained by the cache
+     * @param <V> the type of values stored in the cache
+     */
+    public static class Builder<K, V> {
+        private final int capacity;
+        private long defaultTTL = 0;
+        private BiConsumer<K, V> evictionListener;
+        private EvictionStrategy<K, V> evictionStrategy = new FIFOCache.ImmediateEvictionStrategy<>();
+        /**
+         * Creates a new {@code Builder} with the specified cache capacity.
+         *
+         * @param capacity the maximum number of entries the cache can hold; must be > 0
+         * @throws IllegalArgumentException if {@code capacity} is less than or equal to 0
+         */
+        public Builder(int capacity) {
+            if (capacity <= 0) {
+                throw new IllegalArgumentException("Capacity must be > 0");
+            }
+            this.capacity = capacity;
+        }
+
+        /**
+         * Sets the default time-to-live (TTL) in milliseconds for cache entries.
+         *
+         * @param ttlMillis the TTL duration in milliseconds; must be >= 0
+         * @return this builder instance for chaining
+         * @throws IllegalArgumentException if {@code ttlMillis} is negative
+         */
+        public Builder<K, V> defaultTTL(long ttlMillis) {
+            if (ttlMillis < 0) {
+                throw new IllegalArgumentException("Default TTL must be >= 0");
+            }
+            this.defaultTTL = ttlMillis;
+            return this;
+        }
+
+        /**
+         * Sets an eviction listener to be notified when entries are evicted from the cache.
+         *
+         * @param listener a {@link BiConsumer} that accepts evicted keys and values; must not be {@code null}
+         * @return this builder instance for chaining
+         * @throws IllegalArgumentException if {@code listener} is {@code null}
+         */
+        public Builder<K, V> evictionListener(BiConsumer<K, V> listener) {
+            if (listener == null) {
+                throw new IllegalArgumentException("Listener must not be null");
+            }
+            this.evictionListener = listener;
+            return this;
+        }
+
+        /**
+         * Builds and returns a new {@link FIFOCache} instance with the configured parameters.
+         *
+         * @return a fully configured {@code FIFOCache} instance
+         */
+        public FIFOCache<K, V> build() {
+            return new FIFOCache<>(this);
+        }
+
+        /**
+         * Sets the eviction strategy used to determine when to clean up expired entries.
+         *
+         * @param strategy an {@link EvictionStrategy} implementation; must not be {@code null}
+         * @return this builder instance
+         * @throws IllegalArgumentException if {@code strategy} is {@code null}
+         */
+        public Builder<K, V> evictionStrategy(EvictionStrategy<K, V> strategy) {
+            if (strategy == null) {
+                throw new IllegalArgumentException("Eviction strategy must not be null");
+            }
+            this.evictionStrategy = strategy;
+            return this;
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/caches/FIFOCacheTest.java b/src/test/java/com/thealgorithms/datastructures/caches/FIFOCacheTest.java
new file mode 100644
index 00000000..5f250e6c
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/caches/FIFOCacheTest.java
@@ -0,0 +1,330 @@
+package com.thealgorithms.datastructures.caches;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicInteger;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.api.function.Executable;
+
+class FIFOCacheTest {
+    private FIFOCache<String, String> cache;
+    private Set<String> evictedKeys;
+    private List<String> evictedValues;
+
+    @BeforeEach
+    void setUp() {
+        evictedKeys = new HashSet<>();
+        evictedValues = new ArrayList<>();
+
+        cache = new FIFOCache.Builder<String, String>(3)
+                    .defaultTTL(1000)
+                    .evictionListener((k, v) -> {
+                        evictedKeys.add(k);
+                        evictedValues.add(v);
+                    })
+                    .build();
+    }
+
+    @Test
+    void testPutAndGet() {
+        cache.put("a", "apple");
+        Assertions.assertEquals("apple", cache.get("a"));
+    }
+
+    @Test
+    void testOverwriteValue() {
+        cache.put("a", "apple");
+        cache.put("a", "avocado");
+        Assertions.assertEquals("avocado", cache.get("a"));
+    }
+
+    @Test
+    void testExpiration() throws InterruptedException {
+        cache.put("temp", "value", 100);
+        Thread.sleep(200);
+        Assertions.assertNull(cache.get("temp"));
+        Assertions.assertTrue(evictedKeys.contains("temp"));
+    }
+
+    @Test
+    void testEvictionOnCapacity() {
+        cache.put("a", "alpha");
+        cache.put("b", "bravo");
+        cache.put("c", "charlie");
+        cache.put("d", "delta");
+
+        int size = cache.size();
+        Assertions.assertEquals(3, size);
+        Assertions.assertEquals(1, evictedKeys.size());
+        Assertions.assertEquals(1, evictedValues.size());
+    }
+
+    @Test
+    void testEvictionListener() {
+        cache.put("x", "one");
+        cache.put("y", "two");
+        cache.put("z", "three");
+        cache.put("w", "four");
+
+        Assertions.assertFalse(evictedKeys.isEmpty());
+        Assertions.assertFalse(evictedValues.isEmpty());
+    }
+
+    @Test
+    void testHitsAndMisses() {
+        cache.put("a", "apple");
+        Assertions.assertEquals("apple", cache.get("a"));
+        Assertions.assertNull(cache.get("b"));
+        Assertions.assertEquals(1, cache.getHits());
+        Assertions.assertEquals(1, cache.getMisses());
+    }
+
+    @Test
+    void testSizeExcludesExpired() throws InterruptedException {
+        cache.put("a", "a", 100);
+        cache.put("b", "b", 100);
+        cache.put("c", "c", 100);
+        Thread.sleep(150);
+        Assertions.assertEquals(0, cache.size());
+    }
+
+    @Test
+    void testSizeIncludesFresh() {
+        cache.put("a", "a", 1000);
+        cache.put("b", "b", 1000);
+        cache.put("c", "c", 1000);
+        Assertions.assertEquals(3, cache.size());
+    }
+
+    @Test
+    void testToStringDoesNotExposeExpired() throws InterruptedException {
+        cache.put("live", "alive");
+        cache.put("dead", "gone", 100);
+        Thread.sleep(150);
+        String result = cache.toString();
+        Assertions.assertTrue(result.contains("live"));
+        Assertions.assertFalse(result.contains("dead"));
+    }
+
+    @Test
+    void testNullKeyGetThrows() {
+        Assertions.assertThrows(IllegalArgumentException.class, () -> cache.get(null));
+    }
+
+    @Test
+    void testPutNullKeyThrows() {
+        Assertions.assertThrows(IllegalArgumentException.class, () -> cache.put(null, "v"));
+    }
+
+    @Test
+    void testPutNullValueThrows() {
+        Assertions.assertThrows(IllegalArgumentException.class, () -> cache.put("k", null));
+    }
+
+    @Test
+    void testPutNegativeTTLThrows() {
+        Assertions.assertThrows(IllegalArgumentException.class, () -> cache.put("k", "v", -1));
+    }
+
+    @Test
+    void testBuilderNegativeCapacityThrows() {
+        Assertions.assertThrows(IllegalArgumentException.class, () -> new FIFOCache.Builder<>(0));
+    }
+
+    @Test
+    void testBuilderNullEvictionListenerThrows() {
+        FIFOCache.Builder<String, String> builder = new FIFOCache.Builder<>(1);
+        Assertions.assertThrows(IllegalArgumentException.class, () -> builder.evictionListener(null));
+    }
+
+    @Test
+    void testEvictionListenerExceptionDoesNotCrash() {
+        FIFOCache<String, String> listenerCache = new FIFOCache.Builder<String, String>(1).evictionListener((k, v) -> { throw new RuntimeException("Exception"); }).build();
+
+        listenerCache.put("a", "a");
+        listenerCache.put("b", "b");
+        Assertions.assertDoesNotThrow(() -> listenerCache.get("a"));
+    }
+
+    @Test
+    void testTtlZeroThrowsIllegalArgumentException() {
+        Executable exec = () -> new FIFOCache.Builder<String, String>(3).defaultTTL(-1).build();
+        Assertions.assertThrows(IllegalArgumentException.class, exec);
+    }
+
+    @Test
+    void testPeriodicEvictionStrategyEvictsAtInterval() throws InterruptedException {
+        FIFOCache<String, String> periodicCache = new FIFOCache.Builder<String, String>(10).defaultTTL(50).evictionStrategy(new FIFOCache.PeriodicEvictionStrategy<>(3)).build();
+
+        periodicCache.put("x", "1");
+        Thread.sleep(100);
+        int ev1 = periodicCache.getEvictionStrategy().onAccess(periodicCache);
+        int ev2 = periodicCache.getEvictionStrategy().onAccess(periodicCache);
+        int ev3 = periodicCache.getEvictionStrategy().onAccess(periodicCache);
+
+        Assertions.assertEquals(0, ev1);
+        Assertions.assertEquals(0, ev2);
+        Assertions.assertEquals(1, ev3, "Eviction should happen on the 3rd access");
+        Assertions.assertEquals(0, periodicCache.size());
+    }
+
+    @Test
+    void testPeriodicEvictionStrategyThrowsExceptionIfIntervalLessThanOrEqual0() {
+        Executable executable = () -> new FIFOCache.Builder<String, String>(10).defaultTTL(50).evictionStrategy(new FIFOCache.PeriodicEvictionStrategy<>(0)).build();
+
+        Assertions.assertThrows(IllegalArgumentException.class, executable);
+    }
+
+    @Test
+    void testImmediateEvictionStrategyStrategyEvictsOnEachCall() throws InterruptedException {
+        FIFOCache<String, String> immediateEvictionStrategy = new FIFOCache.Builder<String, String>(10).defaultTTL(50).evictionStrategy(new FIFOCache.ImmediateEvictionStrategy<>()).build();
+
+        immediateEvictionStrategy.put("x", "1");
+        Thread.sleep(100);
+        int evicted = immediateEvictionStrategy.getEvictionStrategy().onAccess(immediateEvictionStrategy);
+
+        Assertions.assertEquals(1, evicted);
+    }
+
+    @Test
+    void testBuilderThrowsExceptionIfEvictionStrategyNull() {
+        Executable executable = () -> new FIFOCache.Builder<String, String>(10).defaultTTL(50).evictionStrategy(null).build();
+
+        Assertions.assertThrows(IllegalArgumentException.class, executable);
+    }
+
+    @Test
+    void testReturnsCorrectStrategyInstance() {
+        FIFOCache.EvictionStrategy<String, String> strategy = new FIFOCache.ImmediateEvictionStrategy<>();
+
+        FIFOCache<String, String> newCache = new FIFOCache.Builder<String, String>(10).defaultTTL(1000).evictionStrategy(strategy).build();
+
+        Assertions.assertSame(strategy, newCache.getEvictionStrategy(), "Returned strategy should be the same instance");
+    }
+
+    @Test
+    void testDefaultStrategyIsImmediateEvictionStrategy() {
+        FIFOCache<String, String> newCache = new FIFOCache.Builder<String, String>(5).defaultTTL(1000).build();
+
+        Assertions.assertTrue(newCache.getEvictionStrategy() instanceof FIFOCache.ImmediateEvictionStrategy<String, String>, "Default strategy should be ImmediateEvictionStrategyStrategy");
+    }
+
+    @Test
+    void testGetEvictionStrategyIsNotNull() {
+        FIFOCache<String, String> newCache = new FIFOCache.Builder<String, String>(5).build();
+
+        Assertions.assertNotNull(newCache.getEvictionStrategy(), "Eviction strategy should never be null");
+    }
+
+    @Test
+    void testRemoveKeyRemovesExistingKey() {
+        cache.put("A", "Alpha");
+        cache.put("B", "Beta");
+
+        Assertions.assertEquals("Alpha", cache.get("A"));
+        Assertions.assertEquals("Beta", cache.get("B"));
+
+        String removed = cache.removeKey("A");
+        Assertions.assertEquals("Alpha", removed);
+
+        Assertions.assertNull(cache.get("A"));
+        Assertions.assertEquals(1, cache.size());
+    }
+
+    @Test
+    void testRemoveKeyReturnsNullIfKeyNotPresent() {
+        cache.put("X", "X-ray");
+
+        Assertions.assertNull(cache.removeKey("NonExistent"));
+        Assertions.assertEquals(1, cache.size());
+    }
+
+    @Test
+    void testRemoveKeyHandlesExpiredEntry() throws InterruptedException {
+        FIFOCache<String, String> expiringCache = new FIFOCache.Builder<String, String>(2).defaultTTL(100).evictionStrategy(new FIFOCache.ImmediateEvictionStrategy<>()).build();
+
+        expiringCache.put("T", "Temporary");
+
+        Thread.sleep(200);
+
+        String removed = expiringCache.removeKey("T");
+        Assertions.assertEquals("Temporary", removed);
+        Assertions.assertNull(expiringCache.get("T"));
+    }
+
+    @Test
+    void testRemoveKeyThrowsIfKeyIsNull() {
+        Assertions.assertThrows(IllegalArgumentException.class, () -> cache.removeKey(null));
+    }
+
+    @Test
+    void testRemoveKeyTriggersEvictionListener() {
+        AtomicInteger evictedCount = new AtomicInteger();
+
+        FIFOCache<String, String> localCache = new FIFOCache.Builder<String, String>(2).evictionListener((key, value) -> evictedCount.incrementAndGet()).build();
+
+        localCache.put("A", "Apple");
+        localCache.put("B", "Banana");
+
+        localCache.removeKey("A");
+
+        Assertions.assertEquals(1, evictedCount.get(), "Eviction listener should have been called once");
+    }
+
+    @Test
+    void testRemoveKeyDoestNotAffectOtherKeys() {
+        cache.put("A", "Alpha");
+        cache.put("B", "Beta");
+        cache.put("C", "Gamma");
+
+        cache.removeKey("B");
+
+        Assertions.assertEquals("Alpha", cache.get("A"));
+        Assertions.assertNull(cache.get("B"));
+        Assertions.assertEquals("Gamma", cache.get("C"));
+    }
+
+    @Test
+    void testEvictionListenerExceptionDoesNotPropagate() {
+        FIFOCache<String, String> localCache = new FIFOCache.Builder<String, String>(1).evictionListener((key, value) -> { throw new RuntimeException(); }).build();
+
+        localCache.put("A", "Apple");
+
+        Assertions.assertDoesNotThrow(() -> localCache.put("B", "Beta"));
+    }
+
+    @Test
+    void testGetKeysReturnsAllFreshKeys() {
+        cache.put("A", "Alpha");
+        cache.put("B", "Beta");
+        cache.put("G", "Gamma");
+
+        Set<String> expectedKeys = Set.of("A", "B", "G");
+        Assertions.assertEquals(expectedKeys, cache.getAllKeys());
+    }
+
+    @Test
+    void testGetKeysIgnoresExpiredKeys() throws InterruptedException {
+        cache.put("A", "Alpha");
+        cache.put("B", "Beta");
+        cache.put("G", "Gamma", 100);
+
+        Set<String> expectedKeys = Set.of("A", "B");
+        Thread.sleep(200);
+        Assertions.assertEquals(expectedKeys, cache.getAllKeys());
+    }
+
+    @Test
+    void testClearRemovesAllEntries() {
+        cache.put("A", "Alpha");
+        cache.put("B", "Beta");
+        cache.put("G", "Gamma");
+
+        cache.clear();
+        Assertions.assertEquals(0, cache.size());
+    }
+}