Struct HashMap 

pub struct HashMap<K, V, H = BuildHasherDefault<DefaultHasher>, A: Allocator = Global> { /* private fields */ }

A HashMap implementation which uses a modified form of RobinHood/Hopscotch probing. This implementation is efficient, roughly 2x the performance of the default hash map when using a the same fast hasher, and a lot more when using the default hasher. It has also been benchmarked to be as fast/ faster than other hashmaps which are known to be very efficient. The implementation is also fully safe.

Limitations

This hash map does not store keys, so if that is required, then another map would be better. This does, however, save space when the key is large.

Currently, moving the table does not use a custom allocator, which would further improve the implementation.

The number of elements in the map must be a power of two.

Threading

This version is not thread-safe. [LeapMap] is a thread-safe version of the map.

Implementations

impl<'a, K, V, H, A: Allocator> HashMap<K, V, H, A>

pub fn capacity(&self) -> usize

Gets the capacity of the hash map.

impl<K, V> HashMap<K, V, BuildHasherDefault<DefaultHasher>, Global>

where K: Eq + Hash + Clone, V: Value,

pub fn new() -> HashMap<K, V, BuildHasherDefault<DefaultHasher>, Global>

Creates the hash map with space for the default number of elements, which will use the global allocator for allocation of the map data.

pub fn with_capacity( capacity: usize, ) -> HashMap<K, V, BuildHasherDefault<DefaultHasher>, Global>

Creates the hash map with space for capacity elements, which will use the global allocator for allocation of the map data.

impl<K, V, H> HashMap<K, V, H, Global>

where K: Eq + Hash + Clone, V: Value, H: BuildHasher + Default,

pub fn with_capacity_and_hasher( capacity: usize, builder: H, ) -> HashMap<K, V, H, Global>

Creates the hash map with space for capacity elements, using the builder to create the hasher, which will use the global allocator for allocation of the map data.

impl<'a, K, V, H, A> HashMap<K, V, H, A>

where K: Eq + Hash + Clone + 'a, V: Value + 'a, H: BuildHasher + Default, A: Allocator,

pub fn new_in(allocator: A) -> HashMap<K, V, H, A>

Creates the hash map with space for the default number of elements, using the provided allocator to allocate data for the map.

pub fn with_capacity_and_hasher_in( capacity: usize, builder: H, allocator: A, ) -> HashMap<K, V, H, A>

Creates the hash map with space for the capacity number of elements using the provided builder to build the hasher, and allocator for allocating the map data.

pub fn hash_usize<Q>(&self, key: &Q) -> usize

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

Returns the hashed value for the key as usize.

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

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated and the old value is returned.

Examples

let mut map = leapfrog::HashMap::new();
assert_eq!(map.insert(37, 12), None);
assert_eq!(map.insert(37, 14), Some(12));

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

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

Returns an optional reference type to the value corresponding to the key.

Examples

let mut map = leapfrog::HashMap::new();
map.insert(0, 12);
if let Some(value) = map.get(&0) {
    assert_eq!(*value, 12);
}
assert!(map.get(&2).is_none());

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

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

Returns a mutable reference type to the value corresponding to the key.

Examples

let mut map = leapfrog::HashMap::new();
map.insert(1, 12);
if let Some(value) = map.get_mut(&1) {
    *value = 14;
}
assert_eq!(*map.get(&1).unwrap(), 14);
assert!(map.get(&2).is_none());

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

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

Returns the key-value pair corresponding to the supplied key.

The supplied key may be any borrower form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Examples

let mut map = leapfrog::HashMap::new();
map.insert(1, 12);
assert_eq!(map.get_key_value(&1), Some((&1, &12)));
assert!(map.get(&2).is_none());

pub fn entry(&mut self, key: K) -> Entry<'_, K, V, H, A>

Gets the given key’s corresponding entry in the map for in-place manipulation.

Examples

let mut map = leapfrog::HashMap::<i32, i32>::new();

map.insert(1, 10);
map.insert(2, 20);

for i in 1..5 {
    let value = map.entry(i).or_insert(i * 10);
    *value += 1;
}

assert_eq!(map.get(&1), Some(&11));
assert_eq!(map.get(&2), Some(&21));
assert_eq!(map.get(&3), Some(&31));
assert_eq!(map.get(&4), Some(&41));

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

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

Returns true if the map contains the specified key.

Examples

let mut map = leapfrog::HashMap::new();
map.insert(1, 47u64);
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

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

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

Removes the key from the map, returning the value at the key if the key was present in the map.

Examples

let mut map = leapfrog::HashMap::new();
map.insert(2, 17);
assert_eq!(map.remove(&2), Some(17));
assert_eq!(map.remove(&2), None);

pub fn iter(&'a self) -> Iter<'a, K, V, H, A>

Creates an iterator over a HashMap which yields immutable key-value reference pairs.

Examples

use leapfrog::HashMap;

let mut map = HashMap::new();
map.insert(12, 27);
assert_eq!(map.iter().count(), 1);

pub fn iter_mut(&'a mut self) -> IterMut<'a, K, V, H, A>

Creates an iterator over a HashMap which yields mutable key-value reference pairs.

Examples

use leapfrog::HashMap;

let mut map = HashMap::new();
map.insert(12, 27);
map.iter_mut().for_each(|(_k, v)| *v += 1);
assert_eq!(map.get(&12), Some(&28));
assert_eq!(map.iter_mut().count(), 1);

pub fn len(&self) -> usize

Returns the length of the map.

Examples

let mut map = leapfrog::HashMap::new();
map.insert(2, 17);
assert_eq!(map.len(), 1);
map.insert(4, 17);
assert_eq!(map.len(), 2);
map.remove(&2);
assert_eq!(map.len(), 1);
map.remove(&4);
assert_eq!(map.len(), 0);
map.remove(&4);
assert_eq!(map.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Trait Implementations

impl<'a, K, V, H, A> Clone for HashMap<K, V, H, A>

where K: Eq + Hash + Clone + 'a, V: Value + 'a, H: BuildHasher + Default, A: Allocator + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V> Default for HashMap<K, V, BuildHasherDefault<DefaultHasher>, Global>

where K: Eq + Hash + Clone, V: Value,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, V, H> Deserialize<'de> for HashMap<K, V, H, Global>

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

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V, H, A: Allocator> Drop for HashMap<K, V, H, A>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V, H, A> IntoIterator for &'a HashMap<K, V, H, A>

where K: Eq + Hash + Clone, V: Value, H: BuildHasher + Default + 'a, A: Allocator + 'a,

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, H, A> IntoIterator for HashMap<K, V, H, A>

where K: Eq + Hash + Clone, V: Value, H: BuildHasher + Default, A: Allocator,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = OwnedIter<K, V, H, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, H, A> Serialize for HashMap<K, V, H, A>

where K: Serialize + Eq + Hash + Clone, V: Serialize + Value, H: BuildHasher + Clone + Default, A: Allocator,

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

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<K, V, H, A> Send for HashMap<K, V, H, A>

where H: BuildHasher + Send, A: Allocator + Send,