[−][src]Struct cht::map::HashMap
A lockfree concurrent hash map implemented with open addressing and linear probing.
The default hashing algorithm is Fx Hash, a generally fast insecure
hashing algorithm. If your application requires resistance to denial of
service attacks such as HashDoS, consider using RandomState
instead.
The hashing algorithm to be used can be chosen on a per-HashMap
basis
using the with_hasher
and with_capacity_and_hasher
methods.
Key types must implement Hash
and Eq
. Additionally, if you are going
to be removing elements from this HashMap
, the key type must also
implement Clone
, as HashMap
uses tombstones for deletion. Any
operations that return a value require the value type to implement
Clone
, as elements may be in use by other threads and as such cannot be
moved from.
HashMap
is inspired by Jeff Phreshing's hash tables implemented in
Junction, described in this blog post. In short, HashMap
supports
fully concurrent lookups, insertions, and removals.
Methods
impl<K: Hash + Eq, V> HashMap<K, V>
[src]
pub fn new() -> HashMap<K, V, FxBuildHasher>
[src]
Creates an empty HashMap
.
The hash map is created with a capacity of 0 and will not allocate any
space for elements until the first insertion. However, the hash builder
S
will be allocated on the heap.
pub fn with_capacity(capacity: usize) -> HashMap<K, V, FxBuildHasher>
[src]
Creates an empty HashMap
with space for at least capacity
elements
without reallocating.
If capacity == 0
, the hash map will not allocate any space for
elements, but it will allocate space for the hash builder.
impl<K: Hash + Eq, V, S: BuildHasher> HashMap<K, V, S>
[src]
pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S>
[src]
Creates an empty HashMap
that will use hash_builder
to hash keys.
The created map will have a capacity of 0 and as such will not have any
space for elements allocated until the first insertion. However, the
hash builder S
will be allocated on the heap.
pub fn with_capacity_and_hasher(
capacity: usize,
hash_builder: S
) -> HashMap<K, V, S>
[src]
capacity: usize,
hash_builder: S
) -> HashMap<K, V, S>
Creates an empty HashMap
that will hold at least capacity
elements
without reallocating and that uses hash_builder
to hash keys.
If capacity == 0
, the hash map will not allocate any space for
elements. However, the hash map will always allocate its hash builder
S
on the heap.
pub fn len(&self) -> usize
[src]
Returns the number of elements that are confirmed to have been inserted into this map.
Because HashMap
can be updated concurrently, this function reflects
the number of insert operations that have returned to the user.
In-progress insertions are not counted.
pub fn is_empty(&self) -> bool
[src]
Returns true if this HashMap
contains no confirmed inserted elements.
In-progress insertions into this HashMap
are not considered.
pub fn capacity(&self) -> usize
[src]
Returns the number of elements this HashMap
can hold without
reallocating.
If invoked while this hash map is growing, it is possible for
len
to return a greater value than this function does.
This is because new elements are being inserted into the next array of
buckets, but the HashMap
's bucket pointer has not been swung up the
list yet.
pub fn get<Q: ?Sized + Hash + Eq>(&self, key: &Q) -> Option<V> where
K: Borrow<Q>,
V: Clone,
[src]
K: Borrow<Q>,
V: Clone,
Returns a copy of the value corresponding to key
.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
. In addition, V
must implement Clone
, as
the value may be concurrently removed at any moment, so the best we can
do is return a copy of it.
If your V
does not implement Clone
, you will have to use
get_and
instead.
pub fn get_key_value<Q: ?Sized + Hash + Eq>(&self, key: &Q) -> Option<(K, V)> where
K: Borrow<Q> + Clone,
V: Clone,
[src]
K: Borrow<Q> + Clone,
V: Clone,
Returns a copy of the key and value corresponding to key
.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
. In addition, K
and V
must implement
Clone
, as the bucket may be concurrently removed at any moment, so
the best we can do is return a copy of it.
If your K
or V
do not implement Clone
, you will have to use
get_key_value_and
instead.
pub fn get_and<Q: ?Sized + Hash + Eq, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
[src]
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
Invokes func
with a reference to the value corresponding to key
.
func
will only be invoked if there is a value associated with key
contained within this hash map.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
.
pub fn get_key_value_and<Q: ?Sized + Hash + Eq, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
[src]
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
Invokes func
with a reference to the key and value corresponding to
key
.
func
will only be invoked if there is a value associated with key
contained within this hash map.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
.
pub fn insert(&self, key: K, value: V) -> Option<V> where
V: Clone,
[src]
V: Clone,
Inserts a key-value pair into the hash map, then returns a copy of the
previous value associated with key
.
If the key was not previously present in this hash map, None
is
returned.
V
must implement Clone
for this function, as it is possible that
other threads may still hold references to the value previously
associated with key
. As such, the associated value cannot be moved
from.
pub fn insert_entry(&self, key: K, value: V) -> Option<(K, V)> where
K: Clone,
V: Clone,
[src]
K: Clone,
V: Clone,
Inserts a key-value pair into the hash map, then returns a copy of the previous key-value pair.
If the key was not previously present in this hash map, None
is
returned.
K
and V
must implement Clone
for this function, as it is
possible that other threads may still hold references to the key-value
pair previously associated with key
.
pub fn insert_and<F: FnOnce(&V) -> T, T>(
&self,
key: K,
value: V,
func: F
) -> Option<T>
[src]
&self,
key: K,
value: V,
func: F
) -> Option<T>
Inserts a key-value pair into the hash map, then invokes func
with the
previously-associated value.
If the key was not previously present in this hash map, None
is
returned and func
is not invoked.
pub fn insert_entry_and<F: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
value: V,
func: F
) -> Option<T>
[src]
&self,
key: K,
value: V,
func: F
) -> Option<T>
Inserts a key-value pair into the hash map, then invokes func
with the
new key and previously-associated value.
If the key was not previously present in this hash map, None
is
returned and func
is not invoked.
impl<K: Hash + Eq + Clone, V, S: BuildHasher> HashMap<K, V, S>
[src]
pub fn remove<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<V> where
K: Borrow<Q>,
V: Clone,
[src]
K: Borrow<Q>,
V: Clone,
Removes the value associated with key
from the hash map, returning a
copy of that value if there was one contained in this hash map.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
. K
and V
must implement Clone
for this
function, as K
must be cloned for the tombstone bucket and the
previously-associated value cannot be moved from, as other threads
may still hold references to it.
pub fn remove_entry<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<(K, V)> where
K: Borrow<Q>,
V: Clone,
[src]
K: Borrow<Q>,
V: Clone,
Removes the value associated with key
from the hash map, returning a
copy of that key-value pair it was contained in this hash map.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
. K
and V
must implement Clone
for this
function. K
must be cloned twice: once for the tombstone bucket
and once for the return value; the previously-associated value cannot be
moved from, as other threads may still hold references to it.
pub fn remove_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
[src]
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
Removes the value associated with key
from the hash map, then returns
the result of invoking func
with the previously-associated value.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
. K
must implement Clone
for this
function, as K
must be cloned to create a tombstone bucket.
pub fn remove_entry_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
[src]
&self,
key: &Q,
func: F
) -> Option<T> where
K: Borrow<Q>,
Removes the value associated with key
from the hash map, then returns
the result of invoking func
with the key and previously-associated
value.
Q
can be any borrowed form of K
, but Hash
and Eq
on Q
must match that of K
. K
must implement Clone
for this
function, as K
must be cloned to create a tombstone bucket.
Trait Implementations
impl<K: Eq + Hash, V, S: BuildHasher> Drop for HashMap<K, V, S>
[src]
impl<K: Default + Hash + Eq, V: Default, S: Default + BuildHasher> Default for HashMap<K, V, S>
[src]
Auto Trait Implementations
impl<K, V, S> Sync for HashMap<K, V, S> where
K: Send + Sync,
S: Send + Sync,
V: Send + Sync,
K: Send + Sync,
S: Send + Sync,
V: Send + Sync,
impl<K, V, S> Unpin for HashMap<K, V, S> where
K: Unpin,
V: Unpin,
K: Unpin,
V: Unpin,
impl<K, V, S> Send for HashMap<K, V, S> where
K: Send + Sync,
S: Send + Sync,
V: Send + Sync,
K: Send + Sync,
S: Send + Sync,
V: Send + Sync,
impl<K, V, S> UnwindSafe for HashMap<K, V, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, S> RefUnwindSafe for HashMap<K, V, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
Blanket Implementations
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,