Struct hashbrown::hash_table::HashTable
source · pub struct HashTable<T, A = Global>where
A: Allocator,{ /* private fields */ }
Expand description
Low-level hash table with explicit hashing.
The primary use case for this type over HashMap
or HashSet
is to
support types that do not implement the Hash
and Eq
traits, but
instead require additional data not contained in the key itself to compute a
hash and compare two elements for equality.
Examples of when this can be useful include:
- An
IndexMap
implementation where indices into aVec
are stored as elements in aHashTable<usize>
. Hashing and comparing the elements requires indexing the associatedVec
to get the actual value referred to by the index. - Avoiding re-computing a hash when it is already known.
- Mutating the key of an element in a way that doesn’t affect its hash.
To achieve this, HashTable
methods that search for an element in the table
require a hash value and equality function to be explicitly passed in as
arguments. The method will then iterate over the elements with the given
hash and call the equality function on each of them, until a match is found.
In most cases, a HashTable
will not be exposed directly in an API. It will
instead be wrapped in a helper type which handles the work of calculating
hash values and comparing elements.
Due to its low-level nature, this type provides fewer guarantees than
HashMap
and HashSet
. Specifically, the API allows you to shoot
yourself in the foot by having multiple elements with identical keys in the
table. The table itself will still function correctly and lookups will
arbitrarily return one of the matching elements. However you should avoid
doing this because it changes the runtime of hash table operations from
O(1)
to O(k)
where k
is the number of duplicate entries.
Implementations§
source§impl<T> HashTable<T, Global>
impl<T> HashTable<T, Global>
sourcepub const fn new() -> Self
pub const fn new() -> Self
Creates an empty HashTable
.
The hash table is initially created with a capacity of 0, so it will not allocate until it is first inserted into.
§Examples
use hashbrown::HashTable;
let mut table: HashTable<&str> = HashTable::new();
assert_eq!(table.len(), 0);
assert_eq!(table.capacity(), 0);
sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Creates an empty HashTable
with the specified capacity.
The hash table will be able to hold at least capacity
elements without
reallocating. If capacity
is 0, the hash table will not allocate.
§Examples
use hashbrown::HashTable;
let mut table: HashTable<&str> = HashTable::with_capacity(10);
assert_eq!(table.len(), 0);
assert!(table.capacity() >= 10);
source§impl<T, A> HashTable<T, A>where
A: Allocator,
impl<T, A> HashTable<T, A>where
A: Allocator,
sourcepub const fn new_in(alloc: A) -> Self
pub const fn new_in(alloc: A) -> Self
Creates an empty HashTable
using the given allocator.
The hash table is initially created with a capacity of 0, so it will not allocate until it is first inserted into.
§Examples
use bumpalo::Bump;
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let bump = Bump::new();
let mut table = HashTable::new_in(&bump);
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
// The created HashTable holds none elements
assert_eq!(table.len(), 0);
// The created HashTable also doesn't allocate memory
assert_eq!(table.capacity(), 0);
// Now we insert element inside created HashTable
table.insert_unique(hasher(&"One"), "One", hasher);
// We can see that the HashTable holds 1 element
assert_eq!(table.len(), 1);
// And it also allocates some capacity
assert!(table.capacity() > 1);
sourcepub fn with_capacity_in(capacity: usize, alloc: A) -> Self
pub fn with_capacity_in(capacity: usize, alloc: A) -> Self
Creates an empty HashTable
with the specified capacity using the given allocator.
The hash table will be able to hold at least capacity
elements without
reallocating. If capacity
is 0, the hash table will not allocate.
§Examples
use bumpalo::Bump;
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let bump = Bump::new();
let mut table = HashTable::with_capacity_in(5, &bump);
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
// The created HashTable holds none elements
assert_eq!(table.len(), 0);
// But it can hold at least 5 elements without reallocating
let empty_map_capacity = table.capacity();
assert!(empty_map_capacity >= 5);
// Now we insert some 5 elements inside created HashTable
table.insert_unique(hasher(&"One"), "One", hasher);
table.insert_unique(hasher(&"Two"), "Two", hasher);
table.insert_unique(hasher(&"Three"), "Three", hasher);
table.insert_unique(hasher(&"Four"), "Four", hasher);
table.insert_unique(hasher(&"Five"), "Five", hasher);
// We can see that the HashTable holds 5 elements
assert_eq!(table.len(), 5);
// But its capacity isn't changed
assert_eq!(table.capacity(), empty_map_capacity)
sourcepub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>
pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>
Returns a reference to an entry in the table with the given hash and which satisfies the equality function passed.
This method will call eq
for all entries with the given hash, but may
also call it for entries with a different hash. eq
should only return
true for the desired entry, at which point the search is stopped.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), 1, hasher);
table.insert_unique(hasher(&2), 2, hasher);
table.insert_unique(hasher(&3), 3, hasher);
assert_eq!(table.find(hasher(&2), |&val| val == 2), Some(&2));
assert_eq!(table.find(hasher(&4), |&val| val == 4), None);
sourcepub fn find_mut(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
) -> Option<&mut T>
pub fn find_mut( &mut self, hash: u64, eq: impl FnMut(&T) -> bool, ) -> Option<&mut T>
Returns a mutable reference to an entry in the table with the given hash and which satisfies the equality function passed.
This method will call eq
for all entries with the given hash, but may
also call it for entries with a different hash. eq
should only return
true for the desired entry, at which point the search is stopped.
When mutating an entry, you should ensure that it still retains the same hash value as when it was inserted, otherwise lookups of that entry may fail to find it.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), (1, "a"), |val| hasher(&val.0));
if let Some(val) = table.find_mut(hasher(&1), |val| val.0 == 1) {
val.1 = "b";
}
assert_eq!(table.find(hasher(&1), |val| val.0 == 1), Some(&(1, "b")));
assert_eq!(table.find(hasher(&2), |val| val.0 == 2), None);
sourcepub fn find_entry(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
) -> Result<OccupiedEntry<'_, T, A>, AbsentEntry<'_, T, A>>
pub fn find_entry( &mut self, hash: u64, eq: impl FnMut(&T) -> bool, ) -> Result<OccupiedEntry<'_, T, A>, AbsentEntry<'_, T, A>>
Returns an OccupiedEntry
for an entry in the table with the given hash
and which satisfies the equality function passed.
This can be used to remove the entry from the table. Call
HashTable::entry
instead if you wish to insert an entry if the
lookup fails.
This method will call eq
for all entries with the given hash, but may
also call it for entries with a different hash. eq
should only return
true for the desired entry, at which point the search is stopped.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), (1, "a"), |val| hasher(&val.0));
if let Ok(entry) = table.find_entry(hasher(&1), |val| val.0 == 1) {
entry.remove();
}
assert_eq!(table.find(hasher(&1), |val| val.0 == 1), None);
sourcepub fn entry(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
hasher: impl Fn(&T) -> u64,
) -> Entry<'_, T, A>
pub fn entry( &mut self, hash: u64, eq: impl FnMut(&T) -> bool, hasher: impl Fn(&T) -> u64, ) -> Entry<'_, T, A>
Returns an Entry
for an entry in the table with the given hash
and which satisfies the equality function passed.
This can be used to remove the entry from the table, or insert a new entry with the given hash if one doesn’t already exist.
This method will call eq
for all entries with the given hash, but may
also call it for entries with a different hash. eq
should only return
true for the desired entry, at which point the search is stopped.
This method may grow the table in preparation for an insertion. Call
HashTable::find_entry
if this is undesirable.
hasher
is called if entries need to be moved or copied to a new table.
This must return the same hash value that each entry was inserted with.
§Examples
use hashbrown::hash_table::Entry;
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), (1, "a"), |val| hasher(&val.0));
if let Entry::Occupied(entry) = table.entry(hasher(&1), |val| val.0 == 1, |val| hasher(&val.0))
{
entry.remove();
}
if let Entry::Vacant(entry) = table.entry(hasher(&2), |val| val.0 == 2, |val| hasher(&val.0)) {
entry.insert((2, "b"));
}
assert_eq!(table.find(hasher(&1), |val| val.0 == 1), None);
assert_eq!(table.find(hasher(&2), |val| val.0 == 2), Some(&(2, "b")));
sourcepub fn insert_unique(
&mut self,
hash: u64,
value: T,
hasher: impl Fn(&T) -> u64,
) -> OccupiedEntry<'_, T, A>
pub fn insert_unique( &mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64, ) -> OccupiedEntry<'_, T, A>
Inserts an element into the HashTable
with the given hash value, but
without checking whether an equivalent element already exists within the
table.
hasher
is called if entries need to be moved or copied to a new table.
This must return the same hash value that each entry was inserted with.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut v = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
v.insert_unique(hasher(&1), 1, hasher);
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the table, removing all values.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut v = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
v.insert_unique(hasher(&1), 1, hasher);
v.clear();
assert!(v.is_empty());
sourcepub fn shrink_to_fit(&mut self, hasher: impl Fn(&T) -> u64)
pub fn shrink_to_fit(&mut self, hasher: impl Fn(&T) -> u64)
Shrinks the capacity of the table as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.
hasher
is called if entries need to be moved or copied to a new table.
This must return the same hash value that each entry was inserted with.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::with_capacity(100);
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), 1, hasher);
table.insert_unique(hasher(&2), 2, hasher);
assert!(table.capacity() >= 100);
table.shrink_to_fit(hasher);
assert!(table.capacity() >= 2);
sourcepub fn shrink_to(&mut self, min_capacity: usize, hasher: impl Fn(&T) -> u64)
pub fn shrink_to(&mut self, min_capacity: usize, hasher: impl Fn(&T) -> u64)
Shrinks the capacity of the table with a lower limit. It will drop down no lower than the supplied limit while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.
hasher
is called if entries need to be moved or copied to a new table.
This must return the same hash value that each entry was inserted with.
Panics if the current capacity is smaller than the supplied minimum capacity.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::with_capacity(100);
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), 1, hasher);
table.insert_unique(hasher(&2), 2, hasher);
assert!(table.capacity() >= 100);
table.shrink_to(10, hasher);
assert!(table.capacity() >= 10);
table.shrink_to(0, hasher);
assert!(table.capacity() >= 2);
sourcepub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64)
pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64)
Reserves capacity for at least additional
more elements to be inserted
in the HashTable
. The collection may reserve more space to avoid
frequent reallocations.
hasher
is called if entries need to be moved or copied to a new table.
This must return the same hash value that each entry was inserted with.
§Panics
Panics if the new capacity exceeds isize::MAX
bytes and abort
the program
in case of allocation error. Use try_reserve
instead
if you want to handle memory allocation failure.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table: HashTable<i32> = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.reserve(10, hasher);
assert!(table.capacity() >= 10);
sourcepub fn try_reserve(
&mut self,
additional: usize,
hasher: impl Fn(&T) -> u64,
) -> Result<(), TryReserveError>
pub fn try_reserve( &mut self, additional: usize, hasher: impl Fn(&T) -> u64, ) -> Result<(), TryReserveError>
Tries to reserve capacity for at least additional
more elements to be inserted
in the given HashTable
. The collection may reserve more space to avoid
frequent reallocations.
hasher
is called if entries need to be moved or copied to a new table.
This must return the same hash value that each entry was inserted with.
§Errors
If the capacity overflows, or the allocator reports a failure, then an error is returned.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table: HashTable<i32> = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table
.try_reserve(10, hasher)
.expect("why is the test harness OOMing on 10 bytes?");
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
Returns the number of elements the table can hold without reallocating.
§Examples
use hashbrown::HashTable;
let table: HashTable<i32> = HashTable::with_capacity(100);
assert!(table.capacity() >= 100);
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of elements in the table.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
let mut v = HashTable::new();
assert_eq!(v.len(), 0);
v.insert_unique(hasher(&1), 1, hasher);
assert_eq!(v.len(), 1);
sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true
if the set contains no elements.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
let mut v = HashTable::new();
assert!(v.is_empty());
v.insert_unique(hasher(&1), 1, hasher);
assert!(!v.is_empty());
sourcepub fn iter(&self) -> Iter<'_, T> ⓘ
pub fn iter(&self) -> Iter<'_, T> ⓘ
An iterator visiting all elements in arbitrary order.
The iterator element type is &'a T
.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&"a"), "b", hasher);
table.insert_unique(hasher(&"b"), "b", hasher);
// Will print in an arbitrary order.
for x in table.iter() {
println!("{}", x);
}
sourcepub fn iter_mut(&mut self) -> IterMut<'_, T> ⓘ
pub fn iter_mut(&mut self) -> IterMut<'_, T> ⓘ
An iterator visiting all elements in arbitrary order,
with mutable references to the elements.
The iterator element type is &'a mut T
.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), 1, hasher);
table.insert_unique(hasher(&2), 2, hasher);
table.insert_unique(hasher(&3), 3, hasher);
// Update all values
for val in table.iter_mut() {
*val *= 2;
}
assert_eq!(table.len(), 3);
let mut vec: Vec<i32> = Vec::new();
for val in &table {
println!("val: {}", val);
vec.push(*val);
}
// The `Iter` iterator produces items in arbitrary order, so the
// items must be sorted to test them against a sorted array.
vec.sort_unstable();
assert_eq!(vec, [2, 4, 6]);
assert_eq!(table.len(), 3);
sourcepub fn iter_hash(&self, hash: u64) -> IterHash<'_, T> ⓘ
pub fn iter_hash(&self, hash: u64) -> IterHash<'_, T> ⓘ
An iterator visiting all elements which may match a hash.
The iterator element type is &'a T
.
This iterator may return elements from the table that have a hash value different than the one provided. You should always validate the returned values before using them.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&"a"), "a", hasher);
table.insert_unique(hasher(&"a"), "b", hasher);
table.insert_unique(hasher(&"b"), "c", hasher);
// Will print "a" and "b" (and possibly "c") in an arbitrary order.
for x in table.iter_hash(hasher(&"a")) {
println!("{}", x);
}
sourcepub fn iter_hash_mut(&mut self, hash: u64) -> IterHashMut<'_, T> ⓘ
pub fn iter_hash_mut(&mut self, hash: u64) -> IterHashMut<'_, T> ⓘ
A mutable iterator visiting all elements which may match a hash.
The iterator element type is &'a mut T
.
This iterator may return elements from the table that have a hash value different than the one provided. You should always validate the returned values before using them.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
table.insert_unique(hasher(&1), 2, hasher);
table.insert_unique(hasher(&1), 3, hasher);
table.insert_unique(hasher(&2), 5, hasher);
// Update matching values
for val in table.iter_hash_mut(hasher(&1)) {
*val *= 2;
}
assert_eq!(table.len(), 3);
let mut vec: Vec<i32> = Vec::new();
for val in &table {
println!("val: {}", val);
vec.push(*val);
}
// The values will contain 4 and 6 and may contain either 5 or 10.
assert!(vec.contains(&4));
assert!(vec.contains(&6));
assert_eq!(table.len(), 3);
sourcepub fn retain(&mut self, f: impl FnMut(&mut T) -> bool)
pub fn retain(&mut self, f: impl FnMut(&mut T) -> bool)
Retains only the elements specified by the predicate.
In other words, remove all elements e
such that f(&e)
returns false
.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
for x in 1..=6 {
table.insert_unique(hasher(&x), x, hasher);
}
table.retain(|&mut x| x % 2 == 0);
assert_eq!(table.len(), 3);
sourcepub fn drain(&mut self) -> Drain<'_, T, A> ⓘ
pub fn drain(&mut self) -> Drain<'_, T, A> ⓘ
Clears the set, returning all elements in an iterator.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
for x in 1..=3 {
table.insert_unique(hasher(&x), x, hasher);
}
assert!(!table.is_empty());
// print 1, 2, 3 in an arbitrary order
for i in table.drain() {
println!("{}", i);
}
assert!(table.is_empty());
sourcepub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A> ⓘ
pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A> ⓘ
Drains elements which are true under the given predicate, and returns an iterator over the removed items.
In other words, move all elements e
such that f(&e)
returns true
out
into another iterator.
If the returned ExtractIf
is not exhausted, e.g. because it is dropped without iterating
or the iteration short-circuits, then the remaining elements will be retained.
Use retain()
with a negated predicate if you do not need the returned iterator.
§Examples
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut table = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
for x in 0..8 {
table.insert_unique(hasher(&x), x, hasher);
}
let drained: Vec<i32> = table.extract_if(|&mut v| v % 2 == 0).collect();
let mut evens = drained.into_iter().collect::<Vec<_>>();
let mut odds = table.into_iter().collect::<Vec<_>>();
evens.sort();
odds.sort();
assert_eq!(evens, vec![0, 2, 4, 6]);
assert_eq!(odds, vec![1, 3, 5, 7]);
sourcepub fn get_many_mut<const N: usize>(
&mut self,
hashes: [u64; N],
eq: impl FnMut(usize, &T) -> bool,
) -> [Option<&mut T>; N]
pub fn get_many_mut<const N: usize>( &mut self, hashes: [u64; N], eq: impl FnMut(usize, &T) -> bool, ) -> [Option<&mut T>; N]
Attempts to get mutable references to N
values in the map at once.
The eq
argument should be a closure such that eq(i, k)
returns true if k
is equal to
the i
th key to be looked up.
Returns an array of length N
with the results of each query. For soundness, at most one
mutable reference will be returned to any value. None
will be used if the key is missing.
§Panics
Panics if any keys are overlapping.
§Examples
use hashbrown::hash_table::Entry;
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut libraries: HashTable<(&str, u32)> = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
for (k, v) in [
("Bodleian Library", 1602),
("Athenæum", 1807),
("Herzogin-Anna-Amalia-Bibliothek", 1691),
("Library of Congress", 1800),
] {
libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k));
}
let keys = ["Athenæum", "Library of Congress"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(
got,
[Some(&mut ("Athenæum", 1807)), Some(&mut ("Library of Congress", 1800))],
);
// Missing keys result in None
let keys = ["Athenæum", "New York Public Library"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(got, [Some(&mut ("Athenæum", 1807)), None]);
let mut libraries: HashTable<(&str, u32)> = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
for (k, v) in [
("Athenæum", 1807),
("Library of Congress", 1800),
] {
libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k));
}
// Duplicate keys result in a panic!
let keys = ["Athenæum", "Athenæum"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
sourcepub unsafe fn get_many_unchecked_mut<const N: usize>(
&mut self,
hashes: [u64; N],
eq: impl FnMut(usize, &T) -> bool,
) -> [Option<&mut T>; N]
pub unsafe fn get_many_unchecked_mut<const N: usize>( &mut self, hashes: [u64; N], eq: impl FnMut(usize, &T) -> bool, ) -> [Option<&mut T>; N]
Attempts to get mutable references to N
values in the map at once, without validating that
the values are unique.
The eq
argument should be a closure such that eq(i, k)
returns true if k
is equal to
the i
th key to be looked up.
Returns an array of length N
with the results of each query. None
will be returned if
any of the keys are missing.
For a safe alternative see get_many_mut
.
§Safety
Calling this method with overlapping keys is undefined behavior even if the resulting references are not used.
§Examples
use hashbrown::hash_table::Entry;
use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;
let mut libraries: HashTable<(&str, u32)> = HashTable::new();
let hasher = DefaultHashBuilder::default();
let hasher = |val: &_| hasher.hash_one(val);
for (k, v) in [
("Bodleian Library", 1602),
("Athenæum", 1807),
("Herzogin-Anna-Amalia-Bibliothek", 1691),
("Library of Congress", 1800),
] {
libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k));
}
let keys = ["Athenæum", "Library of Congress"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(
got,
[Some(&mut ("Athenæum", 1807)), Some(&mut ("Library of Congress", 1800))],
);
// Missing keys result in None
let keys = ["Athenæum", "New York Public Library"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(got, [Some(&mut ("Athenæum", 1807)), None]);
sourcepub fn allocation_size(&self) -> usize
pub fn allocation_size(&self) -> usize
Returns the total amount of memory allocated internally by the hash table, in bytes.
The returned number is informational only. It is intended to be primarily used for memory profiling.
Trait Implementations§
source§impl<'a, T, A> IntoIterator for &'a HashTable<T, A>where
A: Allocator,
impl<'a, T, A> IntoIterator for &'a HashTable<T, A>where
A: Allocator,
source§impl<'a, T, A> IntoIterator for &'a mut HashTable<T, A>where
A: Allocator,
impl<'a, T, A> IntoIterator for &'a mut HashTable<T, A>where
A: Allocator,
Auto Trait Implementations§
impl<T, A> Freeze for HashTable<T, A>where
A: Freeze,
impl<T, A> RefUnwindSafe for HashTable<T, A>where
A: RefUnwindSafe,
T: RefUnwindSafe,
impl<T, A> Send for HashTable<T, A>
impl<T, A> Sync for HashTable<T, A>
impl<T, A> Unpin for HashTable<T, A>
impl<T, A> UnwindSafe for HashTable<T, A>where
A: UnwindSafe,
T: UnwindSafe,
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
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)