Crate ringmap

RingMap is a hash table where the iteration order of the key-value pairs is independent of the hash values of the keys. Entries are stored in a ring buffer (VecDeque), allowing efficient manipulation of both the front and back ends.

RingSet is a corresponding hash set using the same implementation and with similar properties.

Highlights

RingMap and RingSet are nearly drop-in compatible with the std HashMap and HashSet, but they also have some features of note:

• The ordering semantics (see their documentation for details)
• Sorting methods and the .pop_back() and .pop_front() methods.
• The Equivalent trait, which offers more flexible equality definitions between borrowed and owned versions of keys.
• The MutableKeys trait, which gives opt-in mutable access to map keys, and MutableValues for sets.

Feature Flags

To reduce the amount of compiled code in the crate by default, certain features are gated behind feature flags. These allow you to opt in to (or out of) functionality. Below is a list of the features available in this crate.

• std: Enables features which require the Rust standard library. For more information see the section on no_std.
• rayon: Enables parallel iteration and other parallel methods.
• serde: Adds implementations for Serialize and Deserialize to RingMap and RingSet. Alternative implementations for (de)serializing RingMap as an ordered sequence are available in the map::serde_seq module.
• borsh: Adds implementations for BorshSerialize and BorshDeserialize to RingMap and RingSet.
• arbitrary: Adds implementations for the arbitrary::Arbitrary trait to RingMap and RingSet.
• quickcheck: Adds implementations for the quickcheck::Arbitrary trait to RingMap and RingSet.

Note: only the std feature is enabled by default.

Alternate Hashers

RingMap and RingSet have a default hasher type S = RandomState, just like the standard HashMap and HashSet, which is resistant to HashDoS attacks but not the most performant. Type aliases can make it easier to use alternate hashers:

use fnv::FnvBuildHasher;
use ringmap::{RingMap, RingSet};

type FnvRingMap<K, V> = RingMap<K, V, FnvBuildHasher>;
type FnvRingSet<T> = RingSet<T, FnvBuildHasher>;

let std: RingSet<i32> = (0..100).collect();
let fnv: FnvRingSet<i32> = (0..100).collect();
assert_eq!(std, fnv);

Rust Version

This version of ringmap requires Rust 1.68 or later.

The ringmap 0.1 release series will use a carefully considered version upgrade policy, where in a later 0.x version, we will raise the minimum required Rust version.

No Standard Library Targets

This crate supports being built without std, requiring alloc instead. This is chosen by disabling the default “std” cargo feature, by adding default-features = false to your dependency specification.

• Creating maps and sets using new and with_capacity is unavailable without std. Use methods RingMap::default, with_hasher, with_capacity_and_hasher instead. A no-std compatible hasher will be needed as well, for example from the crate twox-hash.
• Macros ringmap! and ringset! are unavailable without std. Use the macros ringmap_with_default! and ringset_with_default! instead.

Re-exports

pub use crate::map::RingMap;

pub use crate::set::RingSet;

Modules

map

RingMap is a hash table where the iteration order of the key-value pairs is independent of the hash values of the keys.

set

A hash set implemented using RingMap

Macros

ringmapstd

Create an RingMap from a list of key-value pairs

ringmap_with_default

Create an RingMap from a list of key-value pairs and a BuildHasherDefault-wrapped custom hasher.

ringsetstd

Create an RingSet from a list of values

ringset_with_default

Create an RingSet from a list of values and a BuildHasherDefault-wrapped custom hasher.

Structs

TryReserveError

The error type for try_reserve methods.

Enums

GetDisjointMutError

The error type returned by get_disjoint_indices_mut.

Traits

Equivalent

Key equivalence trait.