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:

• An IndexMap implementation where indices into a Vec are stored as elements in a HashTable<usize>. Hashing and comparing the elements requires indexing the associated Vec 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

impl<T> HashTable<T, Global>

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

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

impl<T, A> HashTable<T, A>

where A: Allocator,

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 ahash::AHasher;
use bumpalo::Bump;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let bump = Bump::new();
let mut table = HashTable::new_in(&bump);
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use bumpalo::Bump;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let bump = Bump::new();
let mut table = HashTable::with_capacity_in(5, &bump);
let hasher = BuildHasherDefault::<AHasher>::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)

pub fn allocator(&self) -> &A

Returns a reference to the underlying allocator.

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use hashbrown::hash_table::Entry;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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")));

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut v = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::default();
let hasher = |val: &_| hasher.hash_one(val);
v.insert_unique(hasher(&1), 1, hasher);

pub fn clear(&mut self)

Clears the table, removing all values.

Examples

use ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut v = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::default();
let hasher = |val: &_| hasher.hash_one(val);
v.insert_unique(hasher(&1), 1, hasher);
v.clear();
assert!(v.is_empty());

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::with_capacity(100);
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::with_capacity(100);
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table: HashTable<i32> = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::default();
let hasher = |val: &_| hasher.hash_one(val);
table.reserve(10, hasher);
assert!(table.capacity() >= 10);

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table: HashTable<i32> = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::default();
let hasher = |val: &_| hasher.hash_one(val);
table
    .try_reserve(10, hasher)
    .expect("why is the test harness OOMing on 10 bytes?");

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

pub fn len(&self) -> usize

Returns the number of elements in the table.

Examples

use ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let hasher = BuildHasherDefault::<AHasher>::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);

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let hasher = BuildHasherDefault::<AHasher>::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());

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

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

Examples

use ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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);
}

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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);

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 ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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);

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

Clears the set, returning all elements in an iterator.

Examples

use ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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());

pub 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

use ahash::AHasher;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut table = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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]);

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 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 returned if any of the keys are duplicates or missing.

Examples

use ahash::AHasher;
use hashbrown::hash_table::Entry;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut libraries: HashTable<(&str, u32)> = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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), &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, None);

// Duplicate keys result in None
let keys = ["Athenæum", "Athenæum"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(got, None);

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 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_many_mut.

Safety

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

Examples

use ahash::AHasher;
use hashbrown::hash_table::Entry;
use hashbrown::HashTable;
use std::hash::{BuildHasher, BuildHasherDefault};

let mut libraries: HashTable<(&str, u32)> = HashTable::new();
let hasher = BuildHasherDefault::<AHasher>::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), &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, None);

// Duplicate keys result in None
let keys = ["Athenæum", "Athenæum"];
let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
assert_eq!(got, None);

Trait Implementations

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

where T: Clone, A: Allocator + Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

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

where T: Debug, A: Allocator,

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

Formats the value using the given formatter.

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

where A: Allocator + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T, A> IntoIterator for &'a HashTable<T, A>

where A: Allocator,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<'a, T, A> IntoIterator for &'a mut HashTable<T, A>

where A: Allocator,

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, T>

Creates an iterator from a value.

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

where A: Allocator,

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<T, A>

Creates an iterator from a value.