lru-cache

lru-cache is a small Rust crate providing LruCache<K, V, S>, a fixed-capacity key-value cache that automatically evicts the least-recently-used entry whenever an insert pushes it past its configured capacity. It is implemented as a thin, generic wrapper around the linked-hash-map crate, which tracks access order using an intrusive doubly-linked list threaded through a hash map, giving amortized constant-time inserts, lookups, and removals while preserving usage order for eviction and iteration.

The crate originated in the contain-rs organization’s effort to provide standard-library-quality container types for Rust and has been stable since 2015. It is explicitly in maintenance mode today: the maintainers only accept changes that keep it compiling against current Rust or fix documentation, so it is best suited for projects that already depend on its exact API rather than new greenfield use, where actively maintained alternatives like lru or hashlink are generally preferable.

What You Get

• A generic LruCache<K, V, S> struct usable with any Eq + Hash key type and any BuildHasher, defaulting to Rust’s RandomState.
• Constant-time insert, get_mut, remove, and contains_key operations, backed by the linked-hash-map crate’s ordered hash map.
• Automatic least-recently-used eviction on insert once len() exceeds capacity(), plus explicit remove_lru() and runtime set_capacity() resizing.
• Order-preserving iterators (iter, iter_mut, IntoIterator) that walk entries from least- to most-recently-used without disturbing that order.
• An optional heapsize_impl Cargo feature that adds a HeapSizeOf implementation for measuring the cache’s in-memory footprint via the heapsize crate.

Common Use Cases

• Bounding memory for an in-process cache of computed or fetched values under unbounded key cardinality.
• Symbol or AST interning tables in parsers and compilers that only need to retain a recently-used working set.
• Sliding-window deduplication of recently-seen identifiers, using LRU eviction as a natural fixed-size window.
• Maintaining legacy Rust code from the contain-rs era that already depends on this crate’s exact API.

Under The Hood

Architecture The entire crate lives in a single src/lib.rs module built around one generic struct, LruCache<K, V, S>, which wraps a linked_hash_map::LinkedHashMap<K, V, S> and a max_size field; capacity enforcement is applied inline inside insert and set_capacity by popping the map’s front entry (map.pop_front()) whenever length exceeds capacity, since LinkedHashMap already moves an entry to the back on access. Three thin iterator wrapper types (Iter, IterMut, IntoIter) simply forward to the underlying map’s own iterators, and an optional src/heapsize.rs module, gated behind the heapsize_impl feature, adds a HeapSizeOf implementation by delegating to the map’s own heap-size accounting. Because virtually all LRU-ordering behavior is delegated to linked-hash-map, the crate’s own logic surface is small and easy to audit, but it also means the crate’s correctness and performance characteristics are entirely inherited from that single dependency.

Tech Stack This is a pure, dependency-light Rust data-structure crate with no I/O, async runtime, or framework surface: its sole required dependency is linked-hash-map (^0.5.3), with heapsize (^0.4) as an optional feature dependency for memory-footprint instrumentation. It targets stable Rust via Cargo and ships no binaries, only a library target intended to be embedded in other Rust projects; CI is defined via a GitHub Actions workflow (build, test, Miri under strict provenance, cargo fmt --check, and cargo clippy) alongside a now-superseded legacy Travis config.

Code Quality A #[cfg(test)] mod tests block inside lib.rs covers insertion, updates, contains_key, LRU eviction order, remove_lru, capacity resizing, Debug formatting, explicit removal, clear, and ordered iteration — reasonable breadth for the crate’s small public API. The GitHub Actions workflow runs the test suite under Miri for undefined-behavior detection and enforces rustfmt/clippy cleanliness, and every public method carries a doc comment with a runnable doctest example. Error handling is idiomatic for the domain: fallible operations return Option rather than defining custom error types, and generic bounds (K: Eq + Hash, Q: Borrow<K> + Hash + Eq, S: BuildHasher) enforce correctness at compile time. The main quality caveat is currency, not craftsmanship: the crate is explicitly in maintainer-declared maintenance mode, its last commit dates to 2022, and its 10 open issues are not being actively triaged.

What Makes It Unique There is little that is technically novel here: it is a conventional wrapper of a linked-hash-map into an LRU eviction policy, a pattern implemented by many crates across many languages. Its main distinguishing trait is historical — as one of the original contain-rs container crates from 2015, it predates and has been substantively superseded by more actively maintained alternatives such as lru (intrusive linked list, no map-delegation overhead) and hashlink. Its continued relevance today is almost entirely as a stable, frozen dependency for older codebases that adopted it before those alternatives existed, rather than as a recommended choice for new code.