DOCSEARCHbyAlgolia
Submit Docs

hashbrown

repository·main·Indexed 23 days ago

https://github.com/rust-lang/hashbrown

A high-performance Rust port of Google's SwissTable hash map, serving as a drop-in replacement for Rust's standard HashMap and HashSet. It offers improved speed, lower memory usage, and is suitable for #[no_std] environments. The crate provides HashMap, HashSet, and a low-level HashTable implementation, with optional support for serde serialization and rayon parallel iterators.

Tokens
7.5K
Snippets
14
Records
54
Agent score
76%

What's inside hashbrown

  2. Initialize a HashSet

    main

    You can create a new HashSet using several methods depending on your requirements for capacity, hasher, and allocator:

    • HashSet::new(): Creates an empty set with 0 initial capacity. It will not allocate until the first insertion.
    • HashSet::with_capacity(capacity): Creates an empty set with at least capacity elements.
    • HashSet::new_in(alloc): Creates an empty set using a specific allocator.
    • HashSet::with_capacity_in(capacity, alloc): Creates an empty set with a specific capacity and allocator.
    • HashSet::with_hasher(hasher): Creates a set with a custom BuildHasher (useful for HashDoS resistance).
    • HashSet::with_capacity_and_hasher(capacity, hasher): Creates a set with specific capacity and a custom hasher.

    Note on HashDoS resistance: The default hasher does not protect against HashDoS attacks. For security-sensitive applications, use std::hash::RandomState with with_hasher or with_capacity_and_hasher.

  3. Use Rayon parallel iterators with HashTable

    main

    If you have the rayon feature enabled, HashTable supports parallel iteration via the rayon::iter traits. You can perform parallel operations on entries using shared references, mutable references, or by consuming the map.

    Available parallel iteration methods:

    • par_iter(): Iterates over shared references (&T).
    • par_iter_mut(): Iterates over mutable references (&mut T).
    • into_par_iter(): Consumes the map and iterates over owned values (T).
    • par_drain(): Consumes all values in arbitrary order while preserving the map's allocated memory for reuse.

  4. Use hashbrown HashMap

    main

    hashbrown provides a drop-in replacement for Rust's standard HashMap and HashSet. You can use it by importing the types from the hashbrown crate.

    use hashbrown::HashMap;

let mut map = HashMap::new();
map.insert(1, "one");

  5. Configure hashbrown Cargo features

    main

    hashbrown provides several optional features that can be enabled in your Cargo.toml to extend functionality or optimize performance:

    FeatureDescription
    nightlyEnables nightly-only features including #[may_dangle].
    serdeEnables serde serialization support.
    rayonEnables rayon parallel iterator support.
    equivalentAllows comparisons to be customized with the Equivalent trait. (enabled by default)
    raw-entryEnables access to the deprecated RawEntry API.
    inline-moreAdds inline hints to most functions, improving run-time performance at the cost of compilation time. (enabled by default)
    default-hasherCompiles with foldhash as default hasher. (enabled by default)
    allocator-api2Enables support for allocators that support allocator-api2. (enabled by default)

  6. Use replace to update an existing value in HashSet

    main
    The replace method allows you to insert a value into the set. If the value (based on Eq) was already present, it returns the old value and replaces it with the new one. If the value was not present, it returns None.

  8. Perform set operations (Union, Intersection, etc.)

    main

    The HashSet provides several methods for set theory operations:

    • difference(&other): Returns an iterator over values in self but not in other.
    • symmetric_difference(&other): Returns an iterator over values in either self or other, but not both.
    • intersection(&other): Returns an iterator over values present in both self and other.
    • union(&other): Returns an iterator over all values in self or other (without duplicates).
    • is_disjoint(&other): Returns true if self and other have no elements in common.
    • is_subset(&other): Returns true if all elements in self are also in other.
    • is_superset(&other): Returns true if self contains all elements of other.

  10. Use parallel comparison methods for `HashSet`

    main

    You can check relationships between two sets in parallel using the following methods:

    • par_is_disjoint(&other): Returns true if the sets have no elements in common.
    • par_is_subset(&other): Returns true if other contains all elements of self.
    • par_is_superset(&other): Returns true if self contains all elements of other.
    • par_eq(&other): Returns true if both sets contain the same values.

  11. Initialize a `HashTable`

    main

    You can create a new HashTable using the default global allocator or a custom allocator.

    • HashTable::new(): Creates an empty table with 0 capacity. No allocation occurs until the first insertion.
    • HashTable::with_capacity(capacity): Creates an empty table with at least capacity elements.
    • HashTable::new_in(alloc): Creates an empty table using a specific allocator.
    • HashTable::with_capacity_in(capacity, alloc): Creates an empty table with at least capacity elements using a specific allocator.

  12. Use VacantEntry::insert to add a value to a vacant entry

    main

    If an entry is vacant, you can call insert() on the VacantEntry to place a value into the set. This returns an OccupiedEntry representing the newly occupied slot.

    use hashbrown::HashSet;
use hashbrown::hash_set::Entry;

let mut set: HashSet<&str> = HashSet::new();

if let Entry::Vacant(o) = set.entry("poneyland") {
    o.insert();
}
assert!(set.contains("poneyland"));