Struct rpds::map::hash_trie_map::HashTrieMap

pub struct HashTrieMap<K, V, P = RcK, H: BuildHasher = RandomState>
where
    P: SharedPointerKind,
{ /* private fields */ }

A persistent map with structural sharing. This implementation uses a hash array mapped trie.

Complexity

Let n be the number of elements in the map.

Temporal complexity

Operation	Average	Worst case
new()	Θ(1)	Θ(1)
insert()	Θ(1)	Θ(n)
remove()	Θ(1)	Θ(n)
get()	Θ(1)	Θ(n)
contains_key()	Θ(1)	Θ(n)
size()	Θ(1)	Θ(1)
clone()	Θ(1)	Θ(1)
iterator creation	Θ(1)	Θ(1)
iterator step	Θ(1)	Θ(1)
iterator full	Θ(n)	Θ(n)

Implementation details

This implementation uses a hash array mapped trie. Details can be found in Ideal Hash Trees.

See the Node documentation for details.

Implementations

impl<K, V> HashTrieMap<K, V>

where K: Eq + Hash,

pub fn new() -> HashTrieMap<K, V>

pub fn new_with_degree(degree: u8) -> HashTrieMap<K, V>

impl<K, V> HashTrieMap<K, V, ArcTK>

where K: Eq + Hash,

pub fn new_sync() -> HashTrieMapSync<K, V>

pub fn new_sync_with_degree(degree: u8) -> HashTrieMapSync<K, V>

impl<K, V, P, H> HashTrieMap<K, V, P, H>

where K: Eq + Hash, H: Clone + BuildHasher, P: SharedPointerKind,

pub fn new_with_hasher_and_ptr_kind( hasher_builder: H ) -> HashTrieMap<K, V, P, H>

pub fn new_with_hasher_and_degree_and_ptr_kind( hasher_builder: H, degree: u8 ) -> HashTrieMap<K, V, P, H>

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

pub fn insert(&self, key: K, value: V) -> HashTrieMap<K, V, P, H>

pub fn insert_mut(&mut self, key: K, value: V)

pub fn remove<Q>(&self, key: &Q) -> HashTrieMap<K, V, P, H>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

pub fn remove_mut<Q>(&mut self, key: &Q) -> bool

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

pub fn size(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn iter(&self) -> Iter<'_, K, V, P>

pub fn keys(&self) -> IterKeys<'_, K, V, P>

pub fn values(&self) -> IterValues<'_, K, V, P>

impl<K, V, P, H> HashTrieMap<K, V, P, H>

where K: Eq + Hash + Clone, V: Clone, H: Clone + BuildHasher, P: SharedPointerKind,

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Trait Implementations

impl<K, V, P, H> Clone for HashTrieMap<K, V, P, H>

where K: Eq + Hash, H: Clone + BuildHasher, P: SharedPointerKind,

fn clone(&self) -> HashTrieMap<K, V, P, H>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug, P, H: Debug + BuildHasher> Debug for HashTrieMap<K, V, P, H>

where P: SharedPointerKind + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V, P, H> Default for HashTrieMap<K, V, P, H>

where K: Eq + Hash, H: Default + Clone + BuildHasher, P: SharedPointerKind,

fn default() -> HashTrieMap<K, V, P, H>

Returns the “default value” for a type.

impl<'de, K, V, P, H> Deserialize<'de> for HashTrieMap<K, V, P, H>

where K: Eq + Hash + Deserialize<'de>, V: Deserialize<'de>, H: BuildHasher + Clone + Default, P: SharedPointerKind,

fn deserialize<D: Deserializer<'de>>( deserializer: D ) -> Result<HashTrieMap<K, V, P, H>, D::Error>

Deserialize this value from the given Serde deserializer.

impl<K, V, P, H> Display for HashTrieMap<K, V, P, H>

where K: Eq + Hash + Display, V: Display, H: Clone + BuildHasher, P: SharedPointerKind,

fn fmt(&self, fmt: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V, P, H> FromIterator<(K, V)> for HashTrieMap<K, V, P, H>

where K: Eq + Hash, H: BuildHasher + Clone + Default, P: SharedPointerKind,

fn from_iter<I: IntoIterator<Item = (K, V)>>( into_iter: I ) -> HashTrieMap<K, V, P, H>

Creates a value from an iterator.

impl<'a, K, Q, V, P, H> Index<&'a Q> for HashTrieMap<K, V, P, H>

where K: Eq + Hash + Borrow<Q>, Q: Hash + Eq + ?Sized, H: Clone + BuildHasher, P: SharedPointerKind,

type Output = V

The returned type after indexing.

fn index(&self, key: &Q) -> &V

Performs the indexing (container[index]) operation.

impl<'a, K, V, P, H> IntoIterator for &'a HashTrieMap<K, V, P, H>

where K: Eq + Hash, H: Default + Clone + BuildHasher, P: SharedPointerKind,

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Map<IterPtr<'a, K, V, P>, fn(_: &'a SharedPointer<Entry<K, V>, P>) -> (&'a K, &'a V)>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, K, V, P>

Creates an iterator from a value.

impl<K, V: PartialEq, P, PO, H> PartialEq<HashTrieMap<K, V, PO, H>> for HashTrieMap<K, V, P, H>

where K: Hash + Eq, H: Clone + BuildHasher, P: SharedPointerKind, PO: SharedPointerKind,

fn eq(&self, other: &HashTrieMap<K, V, PO, H>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V, P, H> Serialize for HashTrieMap<K, V, P, H>

where K: Eq + Hash + Serialize, V: Serialize, H: BuildHasher + Clone + Default, P: SharedPointerKind,

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.

impl<K, V: Eq, P, H> Eq for HashTrieMap<K, V, P, H>

where K: Hash + Eq, H: Clone + BuildHasher, P: SharedPointerKind,