Struct HashTable

pub struct HashTable<T, A = Global>
where
    A: Allocator, { /* private fields */ }

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:

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

impl<T> HashTable<T, Global>

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);

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);

impl<T, A> HashTable<T, A> where A: Allocator,

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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)
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn allocator(&self) -> &A

Returns a reference to the underlying allocator.

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn find_bucket_index(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<usize>

Returns the bucket index in the table for an entry with the given hash and which satisfies the equality function passed.

This can be used to store a borrow-free "reference" to the entry, later using [get_bucket][Self::get_bucket], [get_bucket_mut][Self::get_bucket_mut], or [get_bucket_entry][Self::get_bucket_entry] to access it again without hash probing.

The index is only meaningful as long as the table is not resized and no entries are added or removed. After such changes, it may end up pointing to a different entry or none at all.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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, 1), |val| hasher(&val.0));
table.insert_unique(hasher(&2), (2, 2), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 3), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
assert_eq!(table.get_bucket(index), Some(&(2, 2)));

// Mutation would invalidate any normal reference
for (_key, value) in &mut table {
    *value *= 11;
}

// The index still reaches the same key with the updated value
assert_eq!(table.get_bucket(index), Some(&(2, 22)));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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")));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn get_bucket_entry(&mut self, index: usize) -> Result<OccupiedEntry<'_, T, A>, AbsentEntry<'_, T, A>>

Returns an OccupiedEntry for the given bucket index in the table, or AbsentEntry if it is unoccupied or out of bounds.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();

assert!(table.get_bucket_entry(usize::MAX).is_err());

let occupied_entry = table.get_bucket_entry(index).unwrap();
assert_eq!(occupied_entry.get(), &(2, 'b'));
assert_eq!(occupied_entry.remove().0, (2, 'b'));

assert!(table.find(hasher(&2), |val| val.0 == 2).is_none());
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

unsafe fn get_bucket_entry_unchecked(&mut self, index: usize) -> OccupiedEntry<'_, T, A>

Returns an OccupiedEntry for the given bucket index in the table, without checking whether the index is in-bounds or occupied.

For a safe alternative, see get_bucket_entry.

Safety

It is undefined behavior to call this method with an index that is out-of-bounds or unoccupied, even if the resulting entry is not used.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
assert!(std::ptr::eq(
    table.get_bucket_entry(index).unwrap().into_mut(),
    unsafe { table.get_bucket_entry_unchecked(index).into_mut() },
));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn get_bucket(&self, index: usize) -> Option<&T>

Gets a reference to an entry in the table at the given bucket index, or None if it is unoccupied or out of bounds.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
assert_eq!(table.get_bucket(index), Some(&(2, 'b')));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

unsafe fn get_bucket_unchecked(&self, index: usize) -> &T

Gets a reference to an entry in the table at the given bucket index, without checking whether the index is in-bounds or occupied.

For a safe alternative, see get_bucket.

Safety

It is undefined behavior to call this method with an index that is out-of-bounds or unoccupied, even if the resulting reference is not used.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
assert!(std::ptr::eq(
    table.get_bucket(index).unwrap(),
    unsafe { table.get_bucket_unchecked(index) },
));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn get_bucket_mut(&mut self, index: usize) -> Option<&mut T>

Gets a mutable reference to an entry in the table at the given bucket index, or None if it is unoccupied or out of bounds.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
assert_eq!(table.get_bucket(index), Some(&(2, 'b')));
if let Some((_key, value)) = table.get_bucket_mut(index) {
    *value = 'B';
}
assert_eq!(table.get_bucket(index), Some(&(2, 'B')));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

unsafe fn get_bucket_unchecked_mut(&mut self, index: usize) -> &mut T

Gets a mutable reference to an entry in the table at the given bucket index, without checking whether the index is in-bounds or occupied.

For a safe alternative, see get_bucket_mut.

Safety

It is undefined behavior to call this method with an index that is out-of-bounds or unoccupied, even if the resulting reference is not used.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
assert!(std::ptr::eq(
    table.get_bucket_mut(index).unwrap(),
    unsafe { table.get_bucket_unchecked_mut(index) },
));
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn clear(&mut self)

Clears the table, removing all values.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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());
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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?");
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn num_buckets(&self) -> usize

Returns the raw number of buckets allocated in the table.

This is an upper bound on any methods that take or return a bucket index, as opposed to the usable capacity for entries which is reduced by an unspecified load factor.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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));
table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));

// Each entry is available at some index in the bucket range.
let count = (0..table.num_buckets())
    .filter_map(|i| table.get_bucket(i))
    .count();
assert_eq!(count, 3);

assert_eq!(table.get_bucket(table.num_buckets()), None);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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);

fn len(&self) -> usize

Returns the number of elements in the table.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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());
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn iter(&self) -> Iter<'_, T>

An iterator visiting all elements in arbitrary order. The iterator element type is &'a T.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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(&"b"), "b", hasher);

// Will print in an arbitrary order.
for x in table.iter() {
    println!("{}", x);
}
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn unsafe_iter(&mut self) -> UnsafeIter<'_, T>

An iterator visiting all elements in arbitrary order, with pointers to the elements. The iterator element type is NonNull<T>.

This iterator is intended for APIs where only part of the elements are mutable, with the remainder being immutable. In these cases, wrapping the ordinary mutable iterator is incorrect because all components of the element type will be invariant. A correct implementation will use an appropriate PhantomData marker to make the immutable parts covariant and the mutable parts invariant.

See the documentation for UnsafeIter for more information on how to correctly use this.

fn iter_buckets(&self) -> IterBuckets<'_, T>

An iterator producing the usize indices of all occupied buckets.

The order in which the iterator yields indices is unspecified and may change in the future.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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(&"b"), "b", hasher);

// Will print in an arbitrary order.
for index in table.iter_buckets() {
    println!("{index}: {}", table.get_bucket(index).unwrap());
}
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
}
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn iter_hash_buckets(&self, hash: u64) -> IterHashBuckets<'_, T>

An iterator producing the usize indices of all buckets which may match a hash.

This iterator may return indices from the table that have a hash value different than the one provided. You should always validate the returned values before using them.

The order in which the iterator yields indices is unspecified and may change in the future.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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 the indices with "a" and "b" (and possibly "c") in an arbitrary order.
for index in table.iter_hash_buckets(hasher(&"a")) {
    println!("{index}: {}", table.get_bucket(index).unwrap());
}
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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

# #[cfg(feature = "nightly")]
# fn test() {
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);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn drain(&mut self) -> Drain<'_, T, A>

Clears the set, returning all elements in an iterator.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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());
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool,

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

# #[cfg(feature = "nightly")]
# fn test() {
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]);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

fn get_disjoint_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 ith 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

# #[cfg(feature = "nightly")]
# fn test() {
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_disjoint_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_disjoint_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(got, [Some(&mut ("Athenæum", 1807)), None]);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

# #[cfg(feature = "nightly")]
# fn test() {
# 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 [
    ("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_disjoint_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test();
#     #[cfg(not(feature = "nightly"))]
#     panic!();
# }

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.

unsafe fn get_disjoint_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 ith 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_disjoint_mut.

Safety

Calling this method with overlapping keys is undefined behavior even if the resulting references are not used.

Examples

# #[cfg(feature = "nightly")]
# fn test() {
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_disjoint_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_disjoint_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(got, [Some(&mut ("Athenæum", 1807)), None]);
# }
# fn main() {
#     #[cfg(feature = "nightly")]
#     test()
# }

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.

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

impl<T, A> Clone for HashTable<T, A> where T: Clone, A: Allocator + Clone,

fn clone(&self) -> Self
fn clone_from(&mut self, source: &Self)

impl<T, A> Debug for HashTable<T, A> where T: Debug, A: Allocator,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

impl<T, A> Default for HashTable<T, A> where A: Allocator + Default,

fn default() -> Self

impl<T, A> IntoIterator for HashTable<T, A> where A: Allocator,

type Item = T;
type IntoIter = IntoIter<T, A>;
fn into_iter(self) -> IntoIter<T, A>

Auto Trait Implementations

impl<T, A> Freeze for HashTable<T, A> where RawTable<T, A>: Freeze,

impl<T, A> RefUnwindSafe for HashTable<T, A> where RawTable<T, A>: RefUnwindSafe,

impl<T, A> Send for HashTable<T, A> where RawTable<T, A>: Send,

impl<T, A> Sync for HashTable<T, A> where RawTable<T, A>: Sync,

impl<T, A> Unpin for HashTable<T, A> where RawTable<T, A>: Unpin,

impl<T, A> UnsafeUnpin for HashTable<T, A> where RawTable<T, A>: UnsafeUnpin,

impl<T, A> UnwindSafe for HashTable<T, A> where RawTable<T, A>: UnwindSafe,

Blanket Implementations

impl<T> Any for HashTable<T, A> where T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for HashTable<T, A> where T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for HashTable<T, A> where T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> CloneToUninit for HashTable<T, A> where T: Clone,

unsafe fn clone_to_uninit(&self, dest: *mut u8)

impl<T> From<T> for HashTable<T, A>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> ToOwned for HashTable<T, A> where T: Clone,

type Owned = T;
fn to_owned(&self) -> T
fn clone_into(&self, target: &mut T)

impl<T, U> Into<U> for HashTable<T, A> where U: From<T>,

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of [From]<T> for U chooses to do.

impl<T, U> TryFrom<U> for HashTable<T, A> where U: Into<T>,

type Error = never;
fn try_from(value: U) -> Result<T, never>

impl<T, U> TryInto<U> for HashTable<T, A> where U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error;
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>