Struct rpds::map::hash_trie_map::HashTrieMap

pub struct HashTrieMap<K, V, H: BuildHasher = RandomState> { /* fields omitted */ }

A persistent map with structural sharing. This implementation uses a hash array mapped trie and supports fast insert(), remove(), and get().

Complexity

Let n be the number of elements in the map.

Temporal complexity

Operation	Best case	Average	Worst case
new()	Θ(1)	Θ(1)	Θ(1)
insert()	Θ(1)	Θ(1)	Θ(n)
remove()	Θ(1)	Θ(1)	Θ(n)
get()	Θ(1)	Θ(1)	Θ(n)
contains_key()	Θ(1)	Θ(1)	Θ(n)
size()	Θ(1)	Θ(1)	Θ(1)
clone()	Θ(1)	Θ(1)	Θ(1)
iterator creation	Θ(1)	Θ(1)	Θ(1)
iterator step	Θ(1)	Θ(1)	Θ(1)
iterator full	Θ(n)	Θ(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.

Methods

impl<K, V> HashTrieMap<K, V, RandomState> where
    K: Eq + Hash, 

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

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

impl<K, V, H: BuildHasher> HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Clone, 

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

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

pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

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

pub fn remove<Q: ?Sized>(&self, key: &Q) -> HashTrieMap<K, V, H> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Hash + Eq, 

pub fn size(&self) -> usize

pub fn is_empty(&self) -> bool

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

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

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

Trait Implementations

impl<K, V, H> Serialize for HashTrieMap<K, V, H> where
    K: Eq + Hash + Serialize,
    V: Serialize,
    H: BuildHasher + Clone + Default, 

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

Serialize this value into the given Serde serializer.

impl<'de, K, V, H> Deserialize<'de> for HashTrieMap<K, V, H> where
    K: Eq + Hash + Deserialize<'de>,
    V: Deserialize<'de>,
    H: BuildHasher + Clone + Default, 

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

Deserialize this value from the given Serde deserializer.

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

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'a, K, Q: ?Sized, V, H: BuildHasher> Index<&'a Q> for HashTrieMap<K, V, H> where
    K: Eq + Hash + Borrow<Q>,
    Q: Hash + Eq,
    H: Clone, 

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<K, V, H: BuildHasher> Clone for HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Clone, 

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, H: BuildHasher> Default for HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Default + Clone, 

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

Returns the "default value" for a type.

impl<K: Eq, V: PartialEq, H: BuildHasher> PartialEq for HashTrieMap<K, V, H> where
    K: Hash,
    H: Clone, 

fn eq(&self, other: &HashTrieMap<K, V, 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 !=.

impl<K: Eq, V: Eq, H: BuildHasher> Eq for HashTrieMap<K, V, H> where
    K: Hash,
    H: Clone, 

impl<K, V, H: BuildHasher> Display for HashTrieMap<K, V, H> where
    K: Eq + Hash + Display,
    V: Display,
    H: Clone, 

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

Formats the value using the given formatter.

impl<'a, K, V, H: BuildHasher> IntoIterator for &'a HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Default + Clone, 

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

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

impl<K, V, H> FromIterator<(K, V)> for HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: BuildHasher + Clone + Default, 

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

Creates a value from an iterator.