Tracking Issue for `HashTable`

Feature gate: #![feature(hash_table)]

This is a tracking issue for introducing a HashTable to the standard library

This is a lower level version of HashMap that uses closures at access points instead of using Hash and Eq.

Public API

pub struct HashTable<T, A = Global> {/* ... */}

pub struct OccupiedEntry<'a, T, A> {/* ... */}
pub struct VacantEntry<'a, T, A> {/* ... */}
/// `AbsentEntry` only hold a reference to the table
/// so that the user can access the table in the branch
/// where `find_entry` doesn't find anything
pub struct AbsentEntry<'a, T, A> {/* ... */}
pub enum Entry<'a, T, A> {/* ... */}

pub struct Iter<'a, T> {/* ... */}
pub struct IterMut<'a, T> {/* ... */}
pub struct IterPtr<T> {/* ... */}
pub struct Drain<'a, T, A> {/* ... */}
pub struct ExtractIf<T, F, A> {/* ... */}

pub struct IterHash<'a, T> {/* ... */}
pub struct IterHashMut<'a, T> {/* ... */}
pub struct IterHashPtr<T> {/* ... */}

pub struct TryReserveError {/* ... */}

impl<T> HashTable<T> {
    pub const fn new() -> Self;

    /// create a new `HashTable` with the given allocator
    pub fn with_capacity(capacity: usize) -> Self;
}

impl<T, A> HashTable<T, A> {
    /// create a new `HashTable` with the given allocator
    pub const fn new_in(alloc: A) -> Self;

    /// create a new `HashTable` with the given allocator
    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self;

    /// The number of elements in the `HashTable` contains
    pub const fn len(&self) -> usize;

    /// Returns true iff there are no elements in the `BTree`
    pub const fn is_empty(&self) -> bool;

    /// The number of elements in the `HashTable` can hold before growing
    pub const fn capacity(&self) -> usize;

    /// Returns a reference to the underlying allocator.
    pub const fn allocator(&self) -> &A;

    /// find the given entry without any need to insert a new element
    /// into the map
    pub fn find_entry(
        &mut self,
        hash: u64,
        eq: impl FnMut(&mut T) -> bool,
    ) -> Result<OccupiedEntry<'_, T, A>, AbsentEntry<'_, T, A>>;

    pub fn entry(
        &mut self,
        hash: u64,
        eq: impl FnMut(&mut T) -> bool,
        hasher: impl FnMut(&mut T) -> u64,
    ) -> Entry<'_, T, A>;

    // finds the element with the given hash that is equal by the given function
    pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>;

    // finds the element with the given hash that is equal by the given function
    pub fn find_mut(&mut self, hash: u64, eq: impl FnMut(&mut T) -> bool) -> Option<&mut T>;

    // finds the element with the given hash that is equal by the given function
    // (note: this has the same provenance as the allocation)
    pub fn find_ptr(&self, hash: u64, eq: impl FnMut(NonNull<T>) -> bool) -> Option<NonNull<T>>;

    // insert a new element without checking for duplicates
    pub fn insert_unique(&mut self, hash: u64, value: T, hasher: impl FnMut(&mut T) -> u64) -> OccupiedEntry<'_, T, A>;

    /// removes all elements from the BTree
    pub fn clear(&mut self);

    /// remove all excess capacity in the map
    pub fn shrink_to_fit(&mut self, hasher: impl FnMut(&mut T) -> u64);

    /// remove all excess capacity in the map, keeping at least enough capacity for `capacity` elements
    pub fn shrink_to(&mut self, capacity: usize, hasher: impl FnMut(&mut T) -> u64);

    /// reserve enough space to insert `additional` elements
    pub fn reserve(&mut self, additional: usize, hasher: impl FnMut(&mut T) -> u64);

    /// reserve enough space to insert `additional` elements, returning an error if the reservation failed
    pub fn try_reserve(&mut self, additional: usize, hasher: impl FnMut(&mut T) -> u64) -> Result<(), TryReserveError>;

    // iterates over all elements, yielding `&T`
    pub fn iter(&self) -> Iter<'_, T>; /* Iterator<Item = &T> */

    // iterates over all elements, yielding `&mut T`
    pub fn iter_mut(&mut self) -> IterMut<'_, T>; /* Iterator<Item = &mut T> */

    /// iterates over all elements, yielding `NonNull<T>`
    /// (note: this has the same provenance as the allocation)
    /// 
    /// # Safety
    /// 
    /// This iterator must not be accessed after this `HashTable` has been dropped or mutated
    pub unsafe fn iter_ptr(&self) -> IterPtr<T>; /* Iterator<Item = NonNull<T>> */

    // iterates over all elements with the given hash, yielding `&T`
    pub fn iter_hash(&self, hash: u64) -> IterHash<'_, T>; /* Iterator<Item = &T> */

    // iterates over all elements with the given hash, yielding `&mut T`
    pub fn iter_hash_mut(&mut self, hash: u64) -> IterHashMut<'_, T>; /* Iterator<Item = &mut T> */

    // iterates over all elements with the given hash, yielding `NonNull<T>`
    // (note: this has the same provenance as the allocation)
    /// 
    /// # Safety
    /// 
    /// This iterator must not be accessed after this `HashTable` has been dropped or mutated
    pub unsafe fn iter_hash_ptr(&self, hash: u64) -> IterHashPtr<T>; /* Iterator<Item = NonNull<T>> */

    /// keep only the elements where `f` returns true
    pub fn retain(&mut self, f: impl FnMut(&mut T) -> bool);

    /// remove all elements from the `HashTable` and yield them as an iterator
    /// if the iterator is dropped, then all further elements are kept in the `HashTable`
    pub fn drain(&mut self) -> Drain<'_, T, A>; /* Iterator<Item = T> */

    /// remove all elements for which `f` returns true and yield them as an iterator
    /// if the iterator is dropped, then all further elements are kept in the `HashTable`
    pub fn extract_if(&mut self, f: impl FnMut(&mut T) -> bool) ->  ExtractIf<'a, T, F, A>; /* Iterator<Item = T> */
}

impl<'a, T, A> OccupiedEntry<'a, T, A>
where
    A: Allocator {
    /// Takes the value out of the entry, and returns it along with a VacantEntry that can be used to insert another value with the same hash as the one that was just removed.
    pub fn remove(self) -> (T, VacantEntry<'a, T, A>);

    /// Gets a pointer to the value in the entry
    pub fn as_ptr(&self) -> NonNull<T>;

    /// Gets a reference to the value in the entry
    pub fn get(&self) -> &T;

    /// Gets a mutable reference to the value in the entry
    pub fn get_mut(&mut self) -> &mut T;

    /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry with a lifetime bound to the table itself
    pub fn into_mut(self) -> &'a mut T;

    /// Converts the `OccupiedEntry` into a mutable reference to the underlying table
    pub fn into_table(self) -> &'a mut HashTable<T, A>;
}

impl<'a, T, A> VacantEntry<'a, T, A>
where
    A: Allocator {
    /// Inserts a new element into the table with the hash that was used to obtain the VacantEntry.
    pub fn insert(self, value: T) -> OccupiedEntry<'a, T, A>;

    /// Converts the `VacantEntry` into a mutable reference to the underlying table
    pub fn into_table(self) -> &'a mut HashTable<T, A>;
}

impl<'a, T, A> AbsentEntry<'a, T, A>
where
    A: Allocator {
    /// Converts the `AbsentEntry` into a mutable reference to the underlying table
    pub fn into_table(self) -> &'a mut HashTable<T, A>;
}

impl<'a, T, A> Entry<'a, T, A>
where
    A: Allocator {
    /// Sets the value of the entry, replacing any existing value if there is one, and returns an `OccupiedEntry`
    pub fn insert(self, value: T) -> OccupiedEntry<'a, T, A>;

    /// Ensures a value is in the entry by inserting if it was vacant.
    /// 
    /// Returns an OccupiedEntry pointing to the now-occupied entry.
    pub fn or_insert(self, default: T) -> OccupiedEntry<'a, T, A>;

    /// Ensures a value is in the entry by inserting the result of the default function if empty..
    /// 
    /// Returns an OccupiedEntry pointing to the now-occupied entry.
    pub fn or_insert_with(
        self,
        default: impl FnOnce() -> T,
    ) -> OccupiedEntry<'a, T, A>;

    /// Provides in-place mutable access to an occupied entry before any potential inserts into the table.
    pub fn and_modify(self, f: impl FnOnce(&mut T)) -> Self;

    /// Converts the `Entry` into a mutable reference to the underlying table
    pub fn into_table(self) -> &'a mut HashTable<T, A>;
}

Notes

This API was mostly shamelessly stolen from hashbrown's HashTable.

There were some changes made, like dropping the bucket API and instead adding access via raw pointers. This keeps hides more implementation details, but allows similar patterns.

Some quality of life parts of the API were dropped, like OccupiedEntry::replace_entry_with or HashTable::get_disjoint_mut. These could be added at a later time, the current API allows users to implement these themselves if they really need it for now.

Steps / History

(Remember to update the S-tracking-* label when checking boxes.)

• ACP: rust-lang/libs-team#812
• Implementation: #...
• Final comment period (FCP)^1
• Stabilization PR

Unresolved Questions

• Should we have separate key and value parameters?

Start with the proposed HashTable public API in this issue and compare it with hashbrown's HashTable, which the issue identifies as the source of the design. The implementation is not yet linked: completion requires an implementation PR, resolution of the separate-key/value question, the final comment period, and a stabilization PR.