rust-lang/hashbrown

Rust port of Google's SwissTable hash map

hashbrown

This crate is a Rust port of Google's high-performance SwissTable hash map, adapted to make it a drop-in replacement for Rust's standard HashMap and HashSet types.

The original C++ version of SwissTable can be found here, and this CppCon talk gives an overview of how the algorithm works.

Since Rust 1.36, this is now the HashMap implementation for the Rust standard library. However you may still want to use this crate instead since it works in environments without std, such as embedded systems and kernels.

Change log

Features

• Drop-in replacement for the standard library HashMap and HashSet types.
• Uses AHash as the default hasher, which is much faster than SipHash. However, AHash does not provide the same level of HashDoS resistance as SipHash, so if that is important to you, you might want to consider using a different hasher.
• Around 2x faster than the previous standard library HashMap.
• Lower memory usage: only 1 byte of overhead per entry instead of 8.
• Compatible with #[no_std] (but requires a global allocator with the alloc crate).
• Empty hash maps do not allocate any memory.
• SIMD lookups to scan multiple hash entries in parallel.

Performance

Compared to the previous implementation of std::collections::HashMap (Rust 1.35).

With the hashbrown default AHash hasher:

name	oldstdhash ns/iter	hashbrown ns/iter	diff ns/iter	diff %	speedup
insert_ahash_highbits	18,865	8,020	-10,845	-57.49%	x 2.35
insert_ahash_random	19,711	8,019	-11,692	-59.32%	x 2.46
insert_ahash_serial	19,365	6,463	-12,902	-66.63%	x 3.00
insert_erase_ahash_highbits	51,136	17,916	-33,220	-64.96%	x 2.85
insert_erase_ahash_random	51,157	17,688	-33,469	-65.42%	x 2.89
insert_erase_ahash_serial	45,479	14,895	-30,584	-67.25%	x 3.05
iter_ahash_highbits	1,399	1,092	-307	-21.94%	x 1.28
iter_ahash_random	1,586	1,059	-527	-33.23%	x 1.50
iter_ahash_serial	3,168	1,079	-2,089	-65.94%	x 2.94
lookup_ahash_highbits	32,351	4,792	-27,559	-85.19%	x 6.75
lookup_ahash_random	17,419	4,817	-12,602	-72.35%	x 3.62
lookup_ahash_serial	15,254	3,606	-11,648	-76.36%	x 4.23
lookup_fail_ahash_highbits	21,187	4,369	-16,818	-79.38%	x 4.85
lookup_fail_ahash_random	21,550	4,395	-17,155	-79.61%	x 4.90
lookup_fail_ahash_serial	19,450	3,176	-16,274	-83.67%	x 6.12

With the libstd default SipHash hasher:

name	oldstdhash ns/iter	hashbrown ns/iter	diff ns/iter	diff %	speedup
insert_std_highbits	19,216	16,885	-2,331	-12.13%	x 1.14
insert_std_random	19,179	17,034	-2,145	-11.18%	x 1.13
insert_std_serial	19,462	17,493	-1,969	-10.12%	x 1.11
insert_erase_std_highbits	50,825	35,847	-14,978	-29.47%	x 1.42
insert_erase_std_random	51,448	35,392	-16,056	-31.21%	x 1.45
insert_erase_std_serial	87,711	38,091	-49,620	-56.57%	x 2.30
iter_std_highbits	1,378	1,159	-219	-15.89%	x 1.19
iter_std_random	1,395	1,132	-263	-18.85%	x 1.23
iter_std_serial	1,704	1,105	-599	-35.15%	x 1.54
lookup_std_highbits	17,195	13,642	-3,553	-20.66%	x 1.26
lookup_std_random	17,181	13,773	-3,408	-19.84%	x 1.25
lookup_std_serial	15,483	13,651	-1,832	-11.83%	x 1.13
lookup_fail_std_highbits	20,926	13,474	-7,452	-35.61%	x 1.55
lookup_fail_std_random	21,766	13,505	-8,261	-37.95%	x 1.61
lookup_fail_std_serial	19,336	13,519	-5,817	-30.08%	x 1.43

Usage

Add this to your Cargo.toml:

[dependencies]
hashbrown = "0.14"

Then:

use hashbrown::HashMap;

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

Flags

This crate has the following Cargo features:

• nightly: Enables nightly-only features including: #[may_dangle].
• serde: Enables serde serialization support.
• rkyv: Enables rkyv serialization support.
• rayon: Enables rayon parallel iterator support.
• raw: Enables access to the experimental and unsafe RawTable API.
• inline-more: Adds inline hints to most functions, improving run-time performance at the cost of compilation time. (enabled by default)
• ahash: Compiles with ahash as default hasher. (enabled by default)
• allocator-api2: Enables support for allocators that support allocator-api2. (enabled by default)

License

Licensed under either of:

• Apache License, Version 2.0, (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

hashbrown's Issues

Possible unsafety in the pub(crate) API of RawTable

After reviewing the PR unsafe impl'ing the Send and Sync traits I was looking around trying to see if I could trigger unsafe behavior. I didn't find anything with Send and Sync, but I think I've found a use-after-free in the pub(crate) API of RawTable.

Can someone take a look at this and make sure I'm not crazy? Again, this is in the non-exposed API, so it's not urgent, but it's always good to make unsafety impossible even internally to the codebase.

fn main() {
    let table = RawTable::new();
    let hash_builder = DefaultHashBuilder::new();
    let k = 50;
    let v = 500;
    let hash = make_hash(&hash_builder, &k);
    table.insert(hash, (k, v), |x| make_hash(&hash_builder, &x.0));
    let raw_iter = table.iter();
    drop(table); /* drops the pointers to data? */
    for bad in raw_iter {
        /* badness ensues */
    }
}

Iteration without an iterator

Hi,
I'm interested in whether hashbrown can be used for implementing Lua tables for Luster. (Note: I'm not the owner, just someone interested in the project!)

The unusual requirements for Lua's tables are:

1. Lua's next(table, item) function returns the "next" item in the table, given another.
2. Iteration using next has to be stable when removing items during the iteration.

I've had a look and think that hashbrown can support this with not much modification, and prototyped it here (a few months ago, so I haven't yet caught up on recent changes; this was before it was moved to rust-lang):

https://github.com/jugglerchris/hashbrown/tree/hash_next

I added a fn next_after(&self, key: Option<&K>) -> Option<(&K, &V)> which simply steps through hash buckets via a RawIterRange constructed to point part way through to implement #1, and #2 happens for free by using tombstones when removing (which relies on there not being a resize when shrinking too far; I'm not confident I haven't missed any cases).

I would be interested to know if functionality like this would be considered for hashbrown itself (I could understand not; I can certainly see not wanting to guarantee no resize on removal), or if not whether I've missed any obvious issues if I (or someone else) were to maintain a fork with these changes.

Thanks! I've certainly enjoyed looking through and having a play either way. :-)

Implement Hash for collections

Is it possible to implement Hash on the hashmap or hashset?
I know that rust stdlib doesn't do this for security reasons. See rust-lang/rust#21182
But as it seems like the goal of this library isn't as focused on security (y'all are using fxhash) as much the stdlib HashSet is, that shouldn't be an issue.

A compiling error which will not occur when using std::collections::HashMap?

Code examples:

// if I use hashbrown::HashMap, compiler complains
// if I use std::collections::HashMap instead, it compiles
use hashbrown::HashMap;
//use std::collections::HashMap;
use typed_arena::Arena;

struct A<'a>(HashMap<&'a str, &'a A<'a>>);

struct B<'a>(&'a Arena<A<'a>>);

fn main() {
  let alloc: Arena<A> = Arena::new();
  let b = B(&alloc);
}

The compiler gives me the following message:

error[E0597]: `alloc` does not live long enough
  --> driver/src/main.rs:20:13
   |
20 |   let b = B(&alloc);
   |             ^^^^^^ borrowed value does not live long enough
21 | }
   | -
   | |
   | `alloc` dropped here while still borrowed
   | borrow might be used here, when `alloc` is dropped and runs the destructor for type `typed_arena::Arena<A<'_>>`

My Cargo.toml:

[dependencies]
typed-arena = "1.4.1"
hashbrown = "0.5"

My rustc version:

rustc 1.37.0-nightly (04a3dd8a8 2019-06-18)

Support for the raw_entry API

This isn't yet part of std::collections::HashMap's API, but has a number of features that cannot be done in the current API. It would be extremely nice if these could be done with hashbrown.

For background, see:

• Raw entry Pre-RFC: https://internals.rust-lang.org/t/pre-rfc-abandonning-morals-in-the-name-of-performance-the-raw-entry-api/7043
• And the rust-lang PR: rust-lang/rust#54043

Hashes are assumed to be only usize

h1 will fail on 32-bit targets if a hasher yields a u64 greater than u32::MAX:
https://github.com/Amanieu/hashbrown/blob/9068eb7a2268d879dc4453ac72238e8a992f1469/src/raw/mod.rs#L120-L126

The comment in h2 gives some insight to this, but that only applies to FxHash:
https://github.com/Amanieu/hashbrown/blob/9068eb7a2268d879dc4453ac72238e8a992f1469/src/raw/mod.rs#L131-L138

See also the failure in rust-lang/rust#58623 (comment)

Getting EXC_I386_GPFLT on custom heap memory allocator

I built a simple memory allocator and set it as global. When I tried to run the test, I got EXC_BAD_ACCESS (code=EXC_I386_GPFLT) under Mac OS X.

This is the stack

hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88b1
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88b1
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88b1
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88ac
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88a5
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba886c
term::terminfo::parser::compiled::parse::hbece3b8f1d06cb9e 0x000000010b95a974

This is the what I see in the disassembler

hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057:
	movdqa (%r15), %xmm0

I assume I did not get the alignment right for movdqa instruction, but content of r15 is 0x000000011355f858 when the mmap returned address is 0x0000000113559000

The code to my allocator is at
https://github.com/ShisoftResearch/Nulloc/blob/a28b93b3647b9628a4c3d247d52257a88a756cd8/src/bump_heap.rs

Making benchmarks better

The benchmarks should really be using criterion
It would be interesting to benchmark it against bytell-hash-map which I did rust implementation for (Haven't optimised it that much and should really make it usable library).

Sentinel byte

The original raw_hash_set code assigns the last control byte to a special "sentinel" value: https://github.com/abseil/abseil-cpp/blob/3088e76c597e068479e82508b1770a7ad0c806b6/absl/container/internal/raw_hash_set.h#L1836. I don't understand the purpose, but since I see you don't do this in hashbrown, I suppose that you might have understood. Could you please share the idea?

Assertion panics

Hi,
I'm still trying to figure out why it happens (it's not easy to get backtrace on a panic without std)
But I'm getting a panic here:

thread panicked at 'Box<Any>', /root/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.3.0/src/raw/mod.rs:1078:9

If that's a known thing or if you have any ideas help is welcome :)

Thanks!

hashbrown/src/raw/mod.rs

Line 1078 in 4368aa4

debug_assert_eq!(ctrl as usize % Group::WIDTH, 0);

Rayon support

It'd be great to have Rayon compatibility for hashbrown's HashMap and HashSet. I think it's a case of implementing IntoParallelIterator, FromParallelIterator and ParallelExtend.

alloc crate will be stable tomorrow

Currently, hashbrown is only no_std with the nightly feature enabled. Since alloc will be stable in 1.36.0, I think it can be no_std even on stable then.

Declare Group::static_empty()'s value as static.

Presently inside of ss2/generic.rs, the method Group::static_empty() returns the address of a const value (promoted to 'static) instead of an explicitly static variable. As a result, the value ends up being created inside of each consuming dylib instead of having a singular location inside of std's dylib (or hashbrown's dylib).

In my use case, this is preventing me from reloading a dylib while any empty (HashMap::new()) instances exist, as their ctrl pointer ends up pointing to garbage in the unloaded dylib, instead of pointing to a static variable inside of std.

If people are cool with changing const -> static, I'd be happy to prepare the trivial PR.

[question] How to configure the stdlib to be fast?

I made a test with the stdlib's hashmap and with this one, hashbrown. The hashbrown version was much faster. In the doc., it's written that the stdlib now uses hashbrown. I guess the stdlib with hashbrown uses a different hash function, which must be slower.

My question: if I want to use the stdlib's hashbrown, how can I configure it to be just as fast as if I had used hashbrown as a dependency?

I don't need DOS-resistance. I just need a very fast hashmap. Thanks.

drain_filter for hashmaps?

Hi,

I saw the RFC for rust-lang/rust#43244, and was wondering if there was an equivalent need for drain_filter-esque behaviour with hashmaps? I've thought about using drain and then reconstructing another HashMap, but I would like to avoid the cost of that.

I also thought about using retain and putting items that weren't retained into a Vec, but I can't take ownership of the items being removed unless I clone/copy them.

In this case, I'm trying to minimize the number of allocations I'm making while taking some items out of a hashmap and putting them into a buffer passed in from elsewhere. The main issue with the retain approach is the inability to not take ownership.

I might be able to dig into the raw api to get something, but I was wondering if this was common enough to be added to the safe api.

I can't seem to find another RFC for this anywhere, and I'm not sure if this is the relevant place to request this, but I thought since this was the underlying implementation for the hashmap it would be good to request it here.

Thanks!

Slower than `std::collections::HashMap` when keys and values are strings?

Hi, I'm very new to rust and just playing around with hash maps and I found that using the code below, the std::collections::HashMap is significantly faster than hashbrown. I'm wondering if someone could explain this? Is hashbrown only meant to be faster for certain types of data? Or am I doing something wrong?

use hashbrown::HashMap;
//use std::collections::HashMap;
use rand::Rng;
use std::time::Instant;
use numtoa::NumToA;

fn main() {
    let mut m = HashMap::new();
    let mut rng = rand::thread_rng();
    let now = Instant::now();
    let mut i = 0;
    let mut last_time = now.elapsed().as_millis();
    while i < 10000000 {
      let mut key_buf = [0u8; 10];
      let mut value_buf = [0u8; 10];
      let key = rng.gen_range(0, 2u32.pow(31)).numtoa_str(16, &mut key_buf);
      let value = rng.gen_range(0, 2u32.pow(31)).numtoa_str(16, &mut value_buf);
      m.insert(key.to_owned(), value.to_owned());
      i += 1;
      if i%1000000 == 0 {
        let now_time = now.elapsed().as_millis();
        println!("{} {}", i, now_time-last_time);
        last_time = now_time;
      }
    }
    
}

Here's my laptop's output for hashbrown::HashMap:

1000000 943
2000000 1749
3000000 1388
4000000 2739
5000000 1433
6000000 1811
7000000 2548
8000000 3885
9000000 1603
10000000 1852

And here's my laptop's output for std::collections::HashMap:

1000000 709
2000000 738
3000000 513
4000000 1062
5000000 527
6000000 573
7000000 677
8000000 1479
9000000 550
10000000 569

Explain in README why one would use this crate after this implementation has landed in `std`

I'm a bit confused: since this implementation landed in std, what's the point of using this crate? I guess the default hash function is different, but apart from that? Would be cool if these things could be explained in the README :)

Optimization in is_full()

https://github.com/Amanieu/hashbrown/blob/63aa152cfd3b3690b69c3f8afd14f4904edb38cf/src/raw/mod.rs#L54-L56

(ctrl as i8) >= 0 might be faster because might benefit the sign bit already set (if LLVM doesn't perform this optimization automatically).

Clone without unnecessary allocations

For my use case I have a worker thread that periodically updates a thread local HashMap and then copies it to another thread. For most iterations no entries are added or removed, only the values change.

I would like to efficiently synchronize the two HashMaps by copying the arrays of control bytes and elements directly to the already allocated arrays of the other HashMap. Basically it would be the same thing that's done in RawTable's clone function without the extra allocations.

hashbrown/src/raw/mod.rs

Lines 978 to 1028 in bacb169

	impl<T: Clone> Clone for RawTable<T> {
	fn clone(&self) -> Self {
	if self.is_empty_singleton() {
	Self::new()
	} else {
	unsafe {
	let mut new_table = ManuallyDrop::new(
	Self::new_uninitialized(self.buckets(), Fallibility::Infallible)
	.unwrap_or_else(|_| hint::unreachable_unchecked()),
	);
	// Copy the control bytes unchanged. We do this in a single pass
	self.ctrl(0)
	.copy_to_nonoverlapping(new_table.ctrl(0), self.num_ctrl_bytes());
	{
	// The cloning of elements may panic, in which case we need
	// to make sure we drop only the elements that have been
	// cloned so far.
	let mut guard = guard((0, &mut new_table), |(index, new_table)| {
	if mem::needs_drop::<T>() {
	for i in 0..=*index {
	if is_full(*new_table.ctrl(i)) {
	new_table.bucket(i).drop();
	}
	}
	}
	new_table.free_buckets();
	});
	for from in self.iter() {
	let index = self.bucket_index(&from);
	let to = guard.1.bucket(index);
	to.write(from.as_ref().clone());
	// Update the index in case we need to unwind.
	guard.0 = index;
	}
	// Successfully cloned all items, no need to clean up.
	mem::forget(guard);
	}
	// Return the newly created table.
	new_table.items = self.items;
	new_table.growth_left = self.growth_left;
	ManuallyDrop::into_inner(new_table)
	}
	}
	}
	}

I saw that the RawTable was recently exposed in #104 but unless I missed something it is not enough to copy the contents from one map into another. Do you think it would be a good idea to implement clone_from on RawTable which reuses the arrays if possible?

What more is needed for 1.0?

This might seem impertinent, but since this is the HashMap of the Rust standard library and std is 1.x, when can this crate become 1.x itself?

Obviously that wouldn't halt development any more than the standard library doesn't develop, but it would mark to direct users of the crate (as the Readme suggests a person might want to do) that they can rely on the direct crate usage not breaking out from under them just as much as they can rely on using this through std won't break out from under them.

Crashing bug: assertion failed: is_special(ctrl)

First: thanks for your talk last night, very enjoyable!

This morning I tried using this new hashmap implementation in my own code as a replacement for libstd's HashMap.

The following code leads to a crash (extracted from my own code and minimized):

extern crate hashbrown;

use hashbrown::HashMap;

fn main() {
    let mut htab = HashMap::new();
    htab.insert(51419, 3);
    htab.insert(32640, 9);
    htab.insert(32475, 22);
}

Error output:

   Compiling hashbrown-bug v0.1.0 (/Users/jrediger/projects/rust/hashbrown-bug)
    Finished dev [unoptimized + debuginfo] target(s) in 0.96s
     Running `target/debug/hashbrown-bug`
thread 'main' panicked at 'assertion failed: is_special(ctrl)', /Users/jrediger/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.1.0/src/raw/mod.rs:62:5
stack backtrace:
   0:        0x109f0caff - std::sys::unix::backtrace::tracing::imp::unwind_backtrace::hd303b0cd45bccf60
                               at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1:        0x109f0497d - std::sys_common::backtrace::print::hf2fe31942821bdcb
                               at libstd/sys_common/backtrace.rs:71
                               at libstd/sys_common/backtrace.rs:59
   2:        0x109f0e543 - std::panicking::default_hook::{{closure}}::h748cb38cc840cba6
                               at libstd/panicking.rs:211
   3:        0x109f0e2cc - std::panicking::default_hook::h81d2ef89c2ad110e
                               at libstd/panicking.rs:227
   4:        0x109f0ebb7 - <std::panicking::begin_panic::PanicPayload<A> as core::panic::BoxMeUp>::get::hc265418ddf96c674
                               at libstd/panicking.rs:477
   5:        0x109f0e71c - std::panicking::continue_panic_fmt::h2d9dbf1e069d262d
                               at libstd/panicking.rs:391
   6:        0x109f0e608 - std::panicking::try::do_call::hcfe6ac53944e0624
                               at libstd/panicking.rs:326
   7:        0x109f47931 - core::ptr::drop_in_place::h2136aea44990720c
                               at libcore/panicking.rs:77
   8:        0x109f47866 - core::ptr::drop_in_place::h2136aea44990720c
                               at libcore/panicking.rs:52
   9:        0x109f01020 - hashbrown::raw::special_is_empty::hd3788a278ef6424a
                               at /Users/jrediger/projects/rust/hashbrown-bug/<::core::macros::panic macros>:3
  10:        0x109efe68e - <hashbrown::raw::RawTable<T>>::insert::h3b2c729d59f9a98d
                               at /Users/jrediger/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.1.0/src/raw/mod.rs:614
  11:        0x109eff8a2 - <hashbrown::map::HashMap<K, V, S>>::insert::h8ea3dcf9ba9cb1e3
                               at /Users/jrediger/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.1.0/src/map.rs:789
  12:        0x109f01571 - hashbrown_bug::main::h8e60525e2e5179d7
                               at src/main.rs:9
  13:        0x109f001e1 - std::rt::lang_start::{{closure}}::hc81fccad58df1a5d
                               at libstd/rt.rs:74
  14:        0x109f0e5e7 - std::panicking::try::do_call::hcfe6ac53944e0624
                               at libstd/rt.rs:59
                               at libstd/panicking.rs:310
  15:        0x109f1ad6e - macho_symbol_search
                               at libpanic_unwind/lib.rs:103
  16:        0x109f0a49c - std::sys_common::bytestring::debug_fmt_bytestring::h2a45b81d7d291ba2
                               at libstd/panicking.rs:289
                               at libstd/panic.rs:392
                               at libstd/rt.rs:58
  17:        0x109f001c1 - std::rt::lang_start::h0cd91951811e88d1
                               at libstd/rt.rs:74
  18:        0x109f015c1 - hashbrown_bug::main::h8e60525e2e5179d7

Hardware: MacBook Pro running macOS High Sierra 10.13.6 on an Intel Core i7

[Request] Update documentation to mention potential `no_std` problem.

Disclaimer: This is actually not an issue with hashbrown but with cargo.

---

Topic: no_std support

While hashbrown itself is able to compile successfully for no_std targets, and even uses the CI pipeline to verify its compatibility to the thumbv6m-none-eabi target, it might still trigger issues if used with other dependencies when the default ahash feature is enabled.

Issue

The dependency tree of ahash injects the getrandom crate if the default feature set is enabled. This crate is heavily platform dependent and does not support targets like the thumbv6 or thumbv7 families.

How does this happen?

The underlying issue is an a long standing and well known cargo bug (rust-lang/cargo#5760) which automatically calculates a required feature set for each (sub-)dependency inside the dependency tree regardless of the dependency origin.

If ahash - with default feature set - is used, it will include the const-random crate and therefore the proc macro crate const-random-macro into the dependency tree. This will request the getrandom feature for the crates rand v^0.7 and indirectly also rand_core v^0.5.1.

As dependencies of proc macros are compiled for the host and not the target architecture this works fine as long as the host architecture is contained in the following list and the no_std build should be successful (as you can see inside the CI).

But it is going to fail as soon as one of the following two conditions are true:

• The host architecture is not supported.

• The target architecture is not supported and the dependency tree contains at least one non proc macro dependency, which requires either rand v^0.7 or rand_core v^0.5.1, because than the underlying cargo issue kicks in. Cargo is going to inject the getrandom feature requirement for these crates, originating from the dependency list of const-random-macro, into the other dependency so that cargo is trying to compile getrandom not only for the host architecture but also for the target architecture.

Request

As long as rust-lang/cargo#5760 is still a thing it would be great if at least the hashbrown documentation could get a warning paragraph explaining this topic including how to work around this issue.

Potential workarounds I can see:

• hashbrown could introduce a way to disable the compile-time-rng feature of ahash if default features are disabled.

• The relying crate could disable the ahash feature of hashbrown and reintroduce another hasher or ahash without compile-time-rng feature.

Both might result in ahash losing the compile time random seed for the hash values.

Expose RawTable publically

I find myself in the need of writing a hash map with some custom ownership semantics in regards to keys.

Your internal RawTable seems to provide exactly the functionality I, with enough flexibility to provide the custom semantics I need.

Would you be open to exposing RawTable publically, possibly behind a feature flag? I do realize that the API most likely is very unstable and may change, but this is something I would be willing to deal with.

Support retrieving an arbitrary element

This may be an exceptionally niche use-case but I figured I'd bring it up anyway. In Noria, we use a hash table as a sort of cache, and occasionally we want to evict a random element from the map. Unfortunately, there is no good way of getting that efficiently (in hashbrown or in std::HashMap). map.keys().skip(rand(map.len())) for example is far too slow. @fintelia has a fork of std::HashMap in rahashmap that we're using, and it:

• Exposes raw_capacity
• Adds remove_element_at_index
• Adds at_index

Together, these three operations let us efficiently find a random key/value pair in a map. I realize that this may be fair more internals than you'd like to expose, but some way of getting at/removing a random element would be really handy, as I don't think there's currently a way of doing it through the normally-exposed APIs. Is there any avenue whereby you could imagine a use-case like this being supported? I was toying with the idea of (ab)using RawEntryBuilder::from_hash, but guessing a hash is very unlikely to yield anything useful, so I think that's out...

Segfault in `RawTable::clear()`

Minimal reproducer:

extern crate hashbrown;

fn main() {
    hashbrown::HashMap::<(), ()>::new().clear();  // calls `self.table.clear()`
}

`HashMap::capacity()` reported lower than the requested one

My understanding of the contracts of std::collections::HashMap is that if a specific capacity is requested through with_capacity() or reserve(), then at no point during the lifetime of the map capacity() would return a quantity that's lower than the requested. This is, however, not the case in the following example:

https://github.com/jakubadamw/hashbrown-capacity-issue-test/blob/d14f5275671dbb70648b47e854cddf936661dd3a/tests/main.rs#L21-L68

where for test_with_capacity() I am seeing the following output:

---- test_with_capacity stdout ----
inserted 1988   capacity = 28
inserted 2666   capacity = 28
inserted 6040   capacity = 28
inserted 25752  capacity = 28
inserted 27146  capacity = 28
inserted 27241  capacity = 28
inserted 27242  capacity = 28
inserted 27243  capacity = 28
inserted 27285  capacity = 28
inserted 27331  capacity = 28
inserted 28712  capacity = 28
inserted 29517  capacity = 28
inserted 32582  capacity = 28
inserted 34410  capacity = 28
inserted 35690  capacity = 28
inserted 38250  capacity = 28
inserted 39274  capacity = 28
inserted 44843  capacity = 28
inserted 48680  capacity = 28
inserted 56389  capacity = 28
inserted 57394  capacity = 28
inserted 61248  capacity = 28
inserted 61510  capacity = 28
inserted 63016  capacity = 28
removed 29517   capacity = 27
thread 'test_with_capacity' panicked at 'assertion failed: `(left == right)`
  left: `28`,
 right: `27`: map.capacity() != previous_with_capacity', tests/hash_map.rs:65:5

28 is the initial capacity requested.

If you'd like to run the test yourself, do make sure to opt out of the aes target feature as the test case is based on hashes from the fallback hasher of ahash.

git clone https://github.com/jakubadamw/hashbrown-capacity-issue-test.git
cd hashbrown-capacity-issue-test
RUSTFLAGS="-C target-feature=-aes" cargo test

serde support

A feature that enables these Hash{Map,Set}s to be used with serde (like std::collections) would be awesome.

Is it possible to build a lazy ScopedHashMap on top of this crate?

If you look at Cranelift's ScopedHashMap, it (in effect) threads a linked-list of keys through the values of the hash map, and to keep track of scopes, entries are deleted eagerly when a scope is exited by following the list.

Instead of doing the work up-front (deleting when a scope is exited), it is possible to keep track of a "generation number" and lazily delete outdated keys for a given depth while performing other operations such as insertion.

For example, if you have a sequence of operations like:

h.increment_depth(); 
h.insert("x", "foo"); 
h.insert("y", "bar"); 
h.decrement_depth(); 
h.insert("x", "frob"); 

Then Cranelift's implementation would have the map evolve like:

{}
{"x" : {"foo", depth = 1}}
{"x" : {"foo", depth = 1}, "y" : {"bar", depth = 1}}
{}
{"x" : {"frob", depth = 1}}

whereas lazily deleting things would give

{}
{"x" : {"foo", depth = 1, gen = 1}}
{"x" : {"foo", depth = 1, gen = 1}, "y" : {"bar", depth = 1, gen = 1}}
{"x" : {"foo", depth = 1, gen = 1}, "y" : {"bar", depth = 1, gen = 1}}
{"x" : {"frob", depth = 1, gen = 2}, "y" : {"bar", depth = 1, gen = 1}}

In this case, I've picked the overwriting key to be identical, but it could very well be something else which just happened to have a hash collision - if the corresponding value is old, we delete the old value.

However, looking at the existing API of the crate, I don't think it is possible to implement such a lazy ScopedHashMap. Is that a fair assessment?

Remove bias in benchmarks

As mentioned briefly in: #71
The benchmarks at present rely on sequential integers. This leads to a serious bias. If the hashmap grows every time it reaches its capacity limit, by the birthday paradox there should be a number of bucket collisions along the way. Hashbrown performs well in this case by storing one byte of the hash code to attempt to resolve the hash collision without having to resort to comparing the keys.

Unfortunately despite the fact that this code path is expected to be common in real life (See footnote) and important to the overall performance of the map, none of the benchmarks presently ever exercise it. (This is because the FxHash is just a single multiplication, so the increasing integers always have evenly spaced low order bits.)

If the benchmarks were changed to instead use random keys, this code path would be exercised and the performance numbers would be more meaningful.

Footnote: (back of the envelope math based on the formula here http://matt.might.net/articles/counting-hash-collisions/ is that as n approaches d and they both get larger the probably of a bucket collisions approaches e^-1 or ~36% when the map is filled. When it is midway between having being resized and needing to be resized again it is ~25%. So we can expect to need to compare the stored byte about a quarter of time.)

Move to the rust-lang org

As rust-lang/rust#58623 has landed we should probably move this to the rust-lang org. If you add me or @pietroalbini as admins to this repo, we can do this move (I think you need to have admin on rust-lang to move a crate there)

Add a proper testsuite

The current code base only has the doctests from the standard library HashMap. We should add a proper testsuite.

Possible sources of inspiration:

• https://github.com/blt/bughunt-rust
• https://github.com/bluss/indexmap/blob/master/tests/quick.rs

Reduce size_of<HashMap> ?

With the switch to Hashbrow, std::mem::size_of::<std::collections::HashMap<(), ()>>() on 64-bit platforms grew from 40 bytes to 56. (24 to 40 bytes with BuildHasherDefault.)

In Servo’s DOM implementation we have types whose size_of is several hundreds of bytes. Because some not-so-unusual pages can have very many DOM nodes this size can add up to significant memory usage. We have unit tests for size_of to ensure it does not accidentally grow, which fail in today’s Rust Nightly because several types grew by 16 bytes because they contain a HashMap.

Hashbrown’s HashMap contains a RawTable which has five pointer-sized fields:

hashbrown/src/raw/mod.rs

Lines 328 to 348 in 7e79b0c

	/// A raw hash table with an unsafe API.
	pub struct RawTable<T> {
	// Mask to get an index from a hash value. The value is one less than the
	// number of buckets in the table.
	bucket_mask: usize,
	// Pointer to the array of control bytes
	ctrl: NonNull<u8>,
	// Pointer to the array of buckets
	data: NonNull<T>,
	// Number of elements that can be inserted before we need to grow the table
	growth_left: usize,
	// Number of elements in the table, only really used by len()
	items: usize,
	// Tell dropck that we own instances of T.
	marker: PhantomData<T>,
	}

Some of them seem potentially redundant, but I’m not sure. For example there are two pointers that seem to be in the same allocation. How expensive would it be to re-compute the second pointer every time it is needed?

Are bucket_mask, growth_left, and len related such that one of them could be computed from the others?

rayon

Many thanks for the library!
Unfortunately, library does not work along with the rayon. What am I doing wrong?

use hashbrown::HashMap;
use rayon::prelude::*;

fn main() {
    let mut test = HashMap::new();
    test.insert("1", 1);
    test.insert("2", 2);
    test.insert("3", 3);
    let vec: Vec<usize> = test.par_iter().map(|(_, val)| *val).collect();
    println!("len: {}", vec.len());
}

error[E0599]: no method named `par_iter` found for type `hashbrown::map::HashMap<&str, {integer}>` in the current scope
  --> src\main.rs:10:32
   |
10 |     let vec: Vec<usize> = test.par_iter().map(|(_, val)| *val).collect();
   |                                ^^^^^^^^
   |
   = note: the method `par_iter` exists but the following trait bounds were not satisfied:
           `hashbrown::map::HashMap<&str, {integer}> : rayon::iter::IntoParallelRefIterator`

error: aborting due to previous error

Cargo.toml

[dependencies]
hashbrown = "0.1.8"
rayon = "1.0.3"

cargo 1.34.0-nightly (5c6aa46e6 2019-02-22)

Why is RawOccupiedEntryMut !Sync?

Entry is Sync if K, V, and S are all Sync, and RawVacantEntryMut is also Sync in the same way, but I'm not sure why RawOccupiedEntryMut is always !Sync?

I ran into this because I'm porting linked-hash-map to be on top of hashbrown's raw-entry API, and I couldn't figure out why this type would need to be !Sync (It also makes RawEntryMut !Sync).

It's definitely possible I'm missing something, so this is genuinely meant as a question.

Add memory usage info to the readme

Hi!

It would be useful to have a rough idea about relative memory usage of hashbrown and rustc_hash!

If hashbrown is 2x faster and the same size, it is super cool
If, for example, it is 2x faster but 2x larger, that it is also very cool, but might not fit some projects.

Look into using a better hash function

We currently use FxHash as the default hash function, but this function handles aligned values poorly: when hashing an integer, if the low X bits of the input value are 0 then the low X bits of the hash value will also be 0.

One option would be to copy Google's CityHash (used by SwissTable). This uses a long multiple and XORs the top and bottom words of the result together:

impl FxHasher {
    #[inline]
    #[cfg(target_pointer_width = "32")]
    fn add_to_hash(&mut self, i: usize) {
        let tmp = self.hash.wrapping_add(i) as u64 * 0xcc9e2d51;
        self.hash = (tmp >> 32 ^ tmp) as usize;
    }
    #[inline]
    #[cfg(target_pointer_width = "64")]
    fn add_to_hash(&mut self, i: usize) {
        let tmp = self.hash.wrapping_add(i) as u128 * 0x9ddfea08eb382d69;
        self.hash = (tmp >> 64 ^ tmp) as usize;
    }
}

cc rust-lang/rust#58249

Missing IndexMut implementation

I hope I'm not blind and missed the reason as for why this is but I noticed that HashMap doesn't seem to implement the IndexMut trait. Is there a specific reason for why this is?

Frequent rehashes when size is close to capacity

In the new benchmark suite, for table sizes just under the capacity, inserting and erasing elements leads to frequent resizes and complete table rehashes.

For SIZE=895:
test insert_erase_std_highbits ... bench:  16,548,714 ns/iter (+/- 1,936,585)
test insert_erase_std_random   ... bench:  16,376,567 ns/iter (+/- 1,338,857)
test insert_erase_std_serial   ... bench:  14,408,640 ns/iter (+/- 2,043,451)

For SIZE=896:
test insert_erase_std_highbits ... bench:      61,495 ns/iter (+/- 6,014)
test insert_erase_std_random   ... bench:      63,244 ns/iter (+/- 3,980)
test insert_erase_std_serial   ... bench:      60,410 ns/iter (+/- 13,798)

The benchmark is inserting and removing items in a loop keeping it at the given size, and once we generate one DELETED control byte we get pushed over the growth_left limit. We're then forced into a resize for a table of the same size as the one we started with. Ideally the amortized cost of insert/remove should be constant.

Optin to store key hashes

I wonder how much of an overhead would be to store hash codes to prevent the worst case [1].

This would be nice as an optin as there's an obvious trade-off with this: memory overhead and insert performance on fully pre allocated tables would be worse.

[1] resizing hash tables which keys are somewhere else in memory (strings) and/or are hard to hash and/or the hasher is slow (like sip).

Augment `raw_entry` API for indexing use case

I'm writing a string-interning data structure in a memory-constrained environment. The strings effectively have 'static lifetime, so I don't need to support deallocation. Therefore, I just append null-terminated strings to a Vec<u8> buffer and identify a string by its (u32) offset into this buffer.

Then, we can query a string by its identifier by starting at the given offset and finding the null byte. But, we'd also like to see if a string is already in the buffer and get its offset if so. I'd like to use hashbrown for maintaining this relation from String to u32 without duplicating each string in memory twice.

The raw entry API is almost there for supporting this. When looking up a string, we can compute its hash and then use RawEntryBuilder::from_hash.

struct Offset(u32);

impl Hash for Offset {
     fn hash<H: Hasher>(&self, h: &mut H) {
         panic!("We shouldn't be hashing the offsets directly!");
     }
}

struct InternedTable {
    buf: Vec<u8>,
    index: HashMap<Offset, ()>,
}

impl InternedTable {
    fn lookup(&self, key: &str) -> Option<u32> {
        let key_hash = ...;
        let result = self.index.raw_entry().from_hash(key_hash, |offset| {
            let offset = offset.0 as usize;
            key.as_bytes() == &self.buf[offset...min(offset + key.len(), buf.len())]
        });
        result.map(|(k, v)| k)
    }
}

However, doing the same for insertions doesn't quite work. The essential issue is that the raw entry API only lets us control the hash of a single key, and inserting may require recomputing hashes of other keys when resizing.

impl InternedTable {
    fn insert(&mut self, key: &str) -> u32 {
        let key_hash = ...;
        let entry = self.index.raw_entry_mut().from_hash(key_hash, |offset| { ... });
        let vacant_entry = match entry {
            // String is already in the table, so return its existing offset.
            RawEntryMut::Occupied(entry) => return *entry.key(),
            RawEntryMut::Vacant(entry) => entry,
        };

        let offset = self.buf.len() as u32;
        self.buf.extend(key.as_bytes());
        self.buf.append(0u8);

        // Panics here from `Hash` implementation called from `RawTable::resize`
        vacant_entry.insert_hashed_nocheck(key_hash, Offset(offset), ());
        offset
    }
}

Today, I get around this by sneaking in a pointer to buf via a thread-local to the Hash implementation. I could also stash a Rc<RefCell<...>> to the buffer on the hash builder for the same effect. However, both of these solutions are ugly, and given how close it is, it feels to me like the RawEntry API should support this use case.

Let me know if accommodating this is acceptable and I can submit a PR. It looks like it should be pretty easy since RawTable already takes in a hasher: impl Fn(&T) -> u64 for many of its methods.

hashbrown has a hard time compiling against libcore now

error[E0599]: no method named `entry` found for type `hashbrown::map::HashMap<rusttype::GlyphId, M>` in the current scope
  --> livesplit-core\src\rendering\glyph_cache.rs:31:21
   |
31 |         self.glyphs.entry(glyph).or_insert_with(|| {
   |                     ^^^^^
   |
   = note: the method `entry` exists but the following trait bounds were not satisfied:
           `hashbrown::map::DefaultHashBuilder : core::hash::BuildHasher`

ed0b240 still builds. So it's either the raw API or more likely AHash that broke it.

meow

I have recently come aross two different interesting projects that did… well "did something with hashes". meowhash and this crate. Now, I have seen thah hashbrown uses FxHash by default, and that it also uses SIMD tricks to speed up lookup. Meow is a hashing algorithm that also extensively uses SIMD and that is apparently very fast.

I have very limited knowledge of how this all works, so maybe it's obviously stupid. But: Would it be interesting to combine the two?

There is a port of Meow to Rust here but from quickly glancing at it, it doesn't seem to support std::hash::Hasher and it might also be difficult to do so as it seems to need to reset some internal data when you'd call finish(&self).

Update README to note that hashbrown is now part of the standard library

Currently, the README claims that hashbrown is faster than itself 😄

entry version w/ borrowed key

Passing ownership of the key to the entry() function can be costly. Especially if then 'common' case is that an element is found this enforces cloning the key for every lookup.

What I would like is to propose a version of the entry function (so far I've not come up with a good name) that takes a a borrowed key and enforces that the ToOwned trait exists. This way the underlying structure can clone/own the key only when required.

I'm happy to make a PR for this but I wanted to discuss the option first to ensure there is interest, make sure that I didn't overlook something blocking, and to find a good and useful name.

Amortize the cost of small tables

When growing a table, hashbrown will start with a table of size 2 (which can hold 1 element due to load factor) and then double every time the load factor is reached.

Table size	Capacity	Memory usage (sizeof(T) = 4)	Memory usage (sizeof(T) = 8)	Memory usage (sizeof(T) = 16)
(empty)	0	0	0	0
2	1	26 (32)	34 (40)	50 (56)
4	3	36 (40)	52 (56)	84 (88)
8	7	56	88	152
16	14	96	160	288
32	28	176	304	560

(rounded up to 8 for allocator alignment)

In comparison, the current std HashMap starts off empty but then immediately grows to a table size of 32 (capacity 29) as soon as the first element is added.

We want to try to balance memory usage for small tables with the allocation overhead when growing tables up to their final size.

Confused about aHash DOS resistance

The README on this repo claims that aHash is not DOS resistant but on the aHash repo it claims that it is DOS resistant.

Goals
AHash is intended to be the fastest DOS resistant hash for use in HashMaps available in the Rust language. Failing in any of these criteria will be treated as a bug.

Drop impl for RawTable should be #[may_dangle]

`entry()` API is slow

Hi there!

Yesterday I tried to use this crate as a drop-in replacement for my FnvHashMap. Surprisingly, it was not faster, but even a bit slower than my previous version. I profiled a bit and noticed that the entry() API of your implementation is probably suboptimal.

Initially I wrote this:

map.entry(key).or_insert_with(|| produce_value())

To test, I changed it to this:

if map.contains_key(&key) {
    map[&key]
} else {
    let v = produce_value();
    map.insert(key, v);
    v
}

In my particular case, the first version runs in 1.96s while the second runs in 1.74s. In my test case, both branches are taken roughly equally often. The code above is executed 3.6 million times and the hashmap ends up with 1.8 million entries. My key is 12 bytes while the value is 4 bytes large.

It's a bit strange that the second version is faster since we have to do two lookups (contains_key plus either map[&key] or map.insert(key, v)). And indeed, FnvHashMap and the hashmap from std) get notably slower in the second version. I mean yeah, the memory used for lookup has probably been properly warmed by contains_key, but we still do unnecessary/duplicate work.

---

I also wrote this micro benchmark (since my results above are in a bigger codebase). In the micro benchmark, the key is also 4 bytes, but it already shows what I wanted to show.

It's basically only two different benchmarks, which are copied to test them with your hash map, FnvHashMap and std::collections::HashMap.

#![feature(test)]

extern crate test;

use hashbrown::HashMap as BrownHashMap;
use fnv::FnvHashMap;
use std::collections::HashMap as StdHashMap;
use self::test::{Bencher, black_box};

const SIZE: usize = 1_000_000;

#[bench]
fn brown_entry(b: &mut Bencher) {
    b.iter(|| {
        let mut m = BrownHashMap::with_capacity(SIZE / 3);
        for i in 0..SIZE as u32 {
            black_box(m.entry(i / 3).or_insert(i));
        }
    })
}

#[bench]
fn brown_manual(b: &mut Bencher) {
    b.iter(|| {
        let mut m = BrownHashMap::with_capacity(SIZE / 3);
        for i in 0..SIZE as u32 {
            let key = i / 3;
            let v = if m.contains_key(&key) {
                m[&key]
            } else {
                m.insert(key, i);
                i
            };
            black_box(v);
        }
    })
}

#[bench]
fn fnv_entry(b: &mut Bencher) {
    b.iter(|| {
        let mut m = FnvHashMap::default();
        m.reserve(SIZE / 3);
        for i in 0..SIZE as u32 {
            black_box(m.entry(i / 3).or_insert(i));
        }
    })
}

#[bench]
fn fnv_manual(b: &mut Bencher) {
    b.iter(|| {
        let mut m = FnvHashMap::default();
        m.reserve(SIZE / 3);
        for i in 0..SIZE as u32 {
            let key = i / 3;
            let v = if m.contains_key(&key) {
                m[&key]
            } else {
                m.insert(key, i);
                i
            };
            black_box(v);
        }
    })
}

#[bench]
fn std_entry(b: &mut Bencher) {
    b.iter(|| {
        let mut m = StdHashMap::with_capacity(SIZE / 3);
        for i in 0..SIZE as u32 {
            black_box(m.entry(i / 3).or_insert(i));
        }
    })
}

#[bench]
fn std_manual(b: &mut Bencher) {
    b.iter(|| {
        let mut m = StdHashMap::with_capacity(SIZE / 3);
        for i in 0..SIZE as u32 {
            let key = i / 3;
            let v = if m.contains_key(&key) {
                m[&key]
            } else {
                m.insert(key, i);
                i
            };
            black_box(v);
        }
    })
}

The results are:

test brown_entry  ... bench:  15,433,281 ns/iter (+/- 6,619,394)
test brown_manual ... bench:  13,233,574 ns/iter (+/- 4,212,542)
test fnv_entry    ... bench:  45,841,114 ns/iter (+/- 11,072,757)
test fnv_manual   ... bench:  47,913,048 ns/iter (+/- 8,861,713)
test std_entry    ... bench:  69,736,423 ns/iter (+/- 14,587,644)
test std_manual   ... bench:  84,257,629 ns/iter (+/- 17,948,341)

So only for brownhash the manual version (without entry()) is faster, while it's slower for the two other hashmaps (as one would expect).

---

So it would be awesome if the entry() API could be improved still. Or is there something about the data structure behind this hashmap that makes it difficult or useless to make the entry APi fast? Thanks!

Expose the hasher algorithm and type aliases for `HashMap`, `HashSet` and `BuildHasher`

As I understand the purpose of this crate, the only thing that is different from std::collections::Hash{Map, Set} and other hash-based data structures from other crates is a different hasher. If that is not true, then what I'm saying below is unapplicable, so feel free to close.

The goal is to eliminate the need to maintain a separate Hash{Map, Set} and also reuse impls for Hash{Map, Set} defined in other crates (provided that they are generic over the hasher) so that we don't have to provide them either.

For example, that's how both fxhash and fnv do:

• FxHashMap and FnvHashMap;
• FxHashSet and FnvHashSet;
• FxBuildHasher and FnvBuildHasher.

This is technically a breaking change since the semantics of hashbrown::HashMap and hashbrown::HashSet might be altered in some ways (that I don't know of, unfortunately).

Solving this issue will help solving https://github.com/Amanieu/hashbrown/issues/6 as well.

Unable to use hashbrown sctuctures between threads

It seems like hashbrown structures doesn't implement Send making it very hard to use them in multithreaded applications

For example, attempt to return them from thread via join handle:

extern crate hashbrown;
fn main () {
    std::thread::spawn(move || { hashbrown::HashSet::new() } );
    std::thread::spawn(move || { hashbrown::HashMap::new() } );
}

Wouldn't compile

➜  cargo build
error[E0277]: `std::ptr::NonNull<u8>` cannot be sent between threads safely
 --> src/main.rs:4:5
  |
4 |     std::thread::spawn(move || { hashbrown::HashSet::new() } );
  |     ^^^^^^^^^^^^^^^^^^ `std::ptr::NonNull<u8>` cannot be sent between threads safely
  |
  = help: within `hashbrown::HashSet<_>`, the trait `std::marker::Send` is not implemented for `std::ptr::NonNull<u8>`
  = note: required because it appears within the type `hashbrown::raw::RawTable<(_, ())>`
  = note: required because it appears within the type `hashbrown::HashMap<_, ()>`
  = note: required because it appears within the type `hashbrown::HashSet<_>`
  = note: required by `std::thread::spawn`

error[E0277]: `std::ptr::NonNull<(_, ())>` cannot be sent between threads safely
 --> src/main.rs:4:5
  |
4 |     std::thread::spawn(move || { hashbrown::HashSet::new() } );
  |     ^^^^^^^^^^^^^^^^^^ `std::ptr::NonNull<(_, ())>` cannot be sent between threads safely
  |
  = help: within `hashbrown::HashSet<_>`, the trait `std::marker::Send` is not implemented for `std::ptr::NonNull<(_, ())>`
  = note: required because it appears within the type `hashbrown::raw::RawTable<(_, ())>`

.....