linked-hash-set

linked_hash_set is a small, focused Rust crate that provides LinkedHashSet<T>, a hashed set implemented on top of linked_hash_map::LinkedHashMap (mirroring how the standard library builds HashSet from HashMap, but with a value of ()). Its defining trait is predictable iteration order: elements come back out in the order they were inserted, not in arbitrary hash-bucket order.

Because it threads a doubly-linked list through its entries, LinkedHashSet supports operations a plain HashSet cannot: front()/back() to peek at the oldest/newest element, pop_front()/pop_back() to remove from either end, and refresh() to move an existing element to the back without changing its identity. It also implements the full complement of set algebra — union, intersection, difference, symmetric difference, subset/superset/disjoint checks — plus Extend, FromIterator, and optional serde (de)serialization behind a feature flag.

The crate is deliberately minimal: one core type, no macros, no unsafe code beyond what linked_hash_map itself uses, and a single runtime dependency. It targets the common case where developers reach for IndexSet or a HashSet + Vec combination just to get ordered iteration, offering a narrower, purpose-built alternative with O(1) removal that doesn’t disturb the order of remaining elements.

What You Get

• LinkedHashSet<T, S> — a hash set that iterates in insertion order, generic over the hasher like std HashSet
• Front/back access and removal: front(), back(), pop_front(), pop_back()
• refresh() to move an existing element to the back of the iteration order without removing/reinserting it
• insert_if_absent() to insert only when missing, without disturbing order for existing elements
• Full set algebra: union, intersection, difference, symmetric_difference, is_subset, is_superset, is_disjoint
• Optional serde feature (via serde_core) for serializing/deserializing the set while preserving order
• Extend, FromIterator, and DoubleEndedIterator implementations for ergonomic construction and iteration

Common Use Cases

• Deduplicating a stream of items (e.g. log lines, event IDs) while preserving first-seen order for display or replay
• Maintaining an LRU-like access-order set using refresh() to bump recently touched items to the back
• Building ordered caches or eviction queues where pop_front() removes the oldest entry in O(1)
• Implementing set operations (union/intersection/difference) on collections where output order must match input order, e.g. for deterministic test output or reproducible builds
• Replacing a HashSet<T> + parallel Vec<T> combination that some codebases hand-roll just to track insertion order

Under The Hood

Architecture The crate has a single-module core (src/lib.rs, ~1,900 lines) that defines LinkedHashSet<T, S> as a thin newtype wrapper around linked_hash_map::LinkedHashMap<T, (), S>, deliberately mirroring how the Rust standard library derives HashSet from HashMap internally. Nearly every method — insert, remove, contains, len, iteration — is a direct delegation to the underlying LinkedHashMap, with set-specific behavior (union, intersection, difference, symmetric difference, subset/superset/disjoint checks) implemented as standalone iterator adaptor structs (Union, Intersection, Difference, SymmetricDifference) that chain or filter the map’s key iterators. An optional src/serde.rs module, gated behind the serde feature, adds Serialize/Deserialize impls that round-trip through a Vec-like sequence to preserve insertion order. Because ordering and storage are both owned by LinkedHashMap, LinkedHashSet itself carries no additional invariants to maintain beyond correct delegation — changing the underlying map’s ordering guarantees would directly change the set’s.

Tech Stack The crate targets Rust edition 2024 and has exactly one runtime dependency, linked-hash-map (pinned to 0.5.6), plus an optional serde_core dependency (1.0.228) enabled via the serde Cargo feature. Dev-dependencies are limited to serde_test for round-trip serialization tests. There is no build script, no unsafe code of its own, and no platform-specific code — it compiles anywhere linked-hash-map does. Packaging follows standard crates.io conventions with a README.md embedded as the crate-level doc comment.

Code Quality Tests are colocated in src/lib.rs using #[cfg(test)] mod tests with roughly two dozen #[test] functions covering insertion order, capacity, set algebra, front/back operations, and (under the serde feature) serialization round-trips. Error handling is minimal by design — nearly every public method returns bool or Option<T> rather than Result, consistent with std HashSet’s API surface, so there’s little error-path complexity to assess. Naming and method signatures closely track the standard library’s HashSet, which keeps the API familiar and self-documenting; doc comments with runnable examples are present on nearly every public method. There is no CI configuration file in the cloned repository snapshot, though the crate is published and versioned regularly on crates.io.

What Makes It Unique The distinguishing design choice is implementing an ordered hash set as a wrapper over an ordered hash map rather than as a fresh data structure, which lets it inherit LinkedHashMap’s O(1) removal without disturbing the order of remaining elements — a property indexmap::IndexSet explicitly trades away (its removals are O(1) only via swap-remove, which reorders elements, or O(n) via shift-remove). This makes LinkedHashSet a better fit than IndexSet specifically when both ordered iteration and order-preserving removal matter simultaneously, at the cost of the cache locality indexmap’s contiguous storage provides. It is a narrow, single-purpose crate rather than a novel algorithm — its value is in filling a specific, precise gap in Rust’s collection ecosystem.