Design an In-Memory Cache with Eviction

Design the object model and public APIs for an in-memory cache library that application code embeds directly (think of the small cache a web service keeps in front of a slow store, all inside one process). The cache holds a bounded number of entries keyed by an arbitrary type; when it fills up, an eviction policy decides which entry to drop so a new one can be admitted. Reads and writes must stay fast even as the cache turns over constantly.

Operating context. One in-process cache instance shared by many worker threads of a single service. It is generic over key and value types. The caller configures a maximum entry count and, optionally, a per-entry time-to-live after which an entry is treated as absent. The eviction policy is chosen at construction from a small family (least-recently-used, least-frequently-used, first-in-first-out) and could later be extended with new policies. The cache also exposes running counters (hits, misses, evictions, current size) so operators can measure its behaviour. No disk, no network, no cross-process coherence.

Out of scope. Distributed / multi-node cache coherence, persistence or write-back to a backing store, serialization of keys and values, cache stampede coordination with the origin, and the concrete backing store itself. Focus on the in-process object model, not any transport, storage, or deployment concern.

What to produce. The class hierarchy (the cache facade, the entry and its bookkeeping, the eviction policy abstraction, the clock and stats collaborators), the public API each type exposes, and the state transitions of an entry (admitted, live, expired, evicted). Be explicit about: how get and put stay O(1) average with the chosen data structures; how the eviction policy plugs in without the core get/put paths knowing which policy is active; how time-to-live expiry interacts with eviction; and how concurrent get/put/evict from many threads stay consistent without serialising every call behind one global lock.