Struct rpds::map::hash_trie_map::HashTrieMap
source · pub struct HashTrieMap<K, V, P = RcK, H: BuildHasher = RandomState>where
P: SharedPointerKind,{ /* private fields */ }
Expand description
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§
source§impl<K, V> HashTrieMap<K, V>
impl<K, V> HashTrieMap<K, V>
pub fn new() -> HashTrieMap<K, V>
pub fn new_with_degree(degree: u8) -> HashTrieMap<K, V>
source§impl<K, V> HashTrieMap<K, V, ArcTK>
impl<K, V> HashTrieMap<K, V, ArcTK>
pub fn new_sync() -> HashTrieMapSync<K, V>
pub fn new_sync_with_degree(degree: u8) -> HashTrieMapSync<K, V>
source§impl<K, V, P, H> HashTrieMap<K, V, P, H>
impl<K, V, P, H> HashTrieMap<K, V, P, H>
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>
pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
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>
pub fn remove_mut<Q>(&mut self, key: &Q) -> bool
pub fn contains_key<Q>(&self, key: &Q) -> bool
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>
Trait Implementations§
source§impl<K, V, P, H> Clone for HashTrieMap<K, V, P, H>
impl<K, V, P, H> Clone for HashTrieMap<K, V, P, H>
source§fn clone(&self) -> HashTrieMap<K, V, P, H>
fn clone(&self) -> HashTrieMap<K, V, P, H>
Returns a copy of the value. Read more
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from
source
. Read moresource§impl<K: Debug, V: Debug, P, H: Debug + BuildHasher> Debug for HashTrieMap<K, V, P, H>where
P: SharedPointerKind + Debug,
impl<K: Debug, V: Debug, P, H: Debug + BuildHasher> Debug for HashTrieMap<K, V, P, H>where
P: SharedPointerKind + Debug,
source§impl<K, V, P, H> Default for HashTrieMap<K, V, P, H>
impl<K, V, P, H> Default for HashTrieMap<K, V, P, H>
source§fn default() -> HashTrieMap<K, V, P, H>
fn default() -> HashTrieMap<K, V, P, H>
Returns the “default value” for a type. Read more
source§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,
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,
source§fn deserialize<D: Deserializer<'de>>(
deserializer: D
) -> Result<HashTrieMap<K, V, P, H>, D::Error>
fn deserialize<D: Deserializer<'de>>( deserializer: D ) -> Result<HashTrieMap<K, V, P, H>, D::Error>
Deserialize this value from the given Serde deserializer. Read more
source§impl<K, V, P, H> Display for HashTrieMap<K, V, P, H>
impl<K, V, P, H> Display for HashTrieMap<K, V, P, H>
source§impl<K, V, P, H> FromIterator<(K, V)> for HashTrieMap<K, V, P, H>
impl<K, V, P, H> FromIterator<(K, V)> for HashTrieMap<K, V, P, H>
source§fn from_iter<I: IntoIterator<Item = (K, V)>>(
into_iter: I
) -> HashTrieMap<K, V, P, H>
fn from_iter<I: IntoIterator<Item = (K, V)>>( into_iter: I ) -> HashTrieMap<K, V, P, H>
Creates a value from an iterator. Read more
source§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,
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,
source§impl<'a, K, V, P, H> IntoIterator for &'a HashTrieMap<K, V, P, H>
impl<'a, K, V, P, H> IntoIterator for &'a HashTrieMap<K, V, P, H>
source§impl<K, V: PartialEq, P, PO, H> PartialEq<HashTrieMap<K, V, PO, H>> for HashTrieMap<K, V, P, H>
impl<K, V: PartialEq, P, PO, H> PartialEq<HashTrieMap<K, V, PO, H>> for HashTrieMap<K, V, P, H>
source§fn eq(&self, other: &HashTrieMap<K, V, PO, H>) -> bool
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 ==
.source§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,
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,
impl<K, V: Eq, P, H> Eq for HashTrieMap<K, V, P, H>
Auto Trait Implementations§
impl<K, V, P, H> RefUnwindSafe for HashTrieMap<K, V, P, H>
impl<K, V, P, H> Send for HashTrieMap<K, V, P, H>
impl<K, V, P, H> Sync for HashTrieMap<K, V, P, H>
impl<K, V, P, H> Unpin for HashTrieMap<K, V, P, H>where
H: Unpin,
impl<K, V, P, H> UnwindSafe for HashTrieMap<K, V, P, H>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more