#random-key #u64 #hash-map #intmap #nohash

inttable

Specialized HashMap for randomly-distributed u64 keys

1 unstable release

0.1.0 Jul 10, 2024

#1904 in Algorithms

23 downloads per month

Unlicense

25KB
401 lines

IntTable

This crate primarily exists to provide the IntTable type, a u64 -> V map that doesn't hash its keys. Naturally, this means it is very fast and very simple, but it also means you can shoot yourself in the foot if your keys aren't random.

This wraps hashbrown's excellent HashTable.

This crate is similar in concept to intmap, but even more specialised.

On an Intel(R) Core(TM) i7-10610U(c) CPU(SM) benchmarks give:

test tests::u64_get_built_in                     ... bench:     137,371.43 ns/iter (+/- 9,054.12)
test tests::u64_get_indexmap                     ... bench:     149,108.03 ns/iter (+/- 7,065.53)
test tests::u64_get_intmap                       ... bench:      75,162.35 ns/iter (+/- 6,712.48)
test tests::u64_get_inttable                     ... bench:      26,691.09 ns/iter (+/- 1,751.50)
test tests::u64_insert_built_in                  ... bench:     171,752.70 ns/iter (+/- 1,718.64)
test tests::u64_insert_checked_intmap            ... bench:      90,894.35 ns/iter (+/- 1,546.25)
test tests::u64_insert_checked_inttable          ... bench:      66,617.80 ns/iter (+/- 735.63)
test tests::u64_insert_entry_intmap              ... bench:     112,376.50 ns/iter (+/- 34,792.00)
test tests::u64_insert_entry_inttable            ... bench:      47,010.84 ns/iter (+/- 967.00)
test tests::u64_insert_indexmap                  ... bench:     190,656.54 ns/iter (+/- 1,239.85)
test tests::u64_insert_intmap                    ... bench:      89,994.67 ns/iter (+/- 7,028.86)
test tests::u64_insert_inttable                  ... bench:      64,322.85 ns/iter (+/- 3,030.45)
test tests::u64_insert_without_capacity_built_in ... bench:     400,817.85 ns/iter (+/- 3,907.70)
test tests::u64_insert_without_capacity_intmap   ... bench:     867,470.10 ns/iter (+/- 40,745.32)
test tests::u64_insert_without_capacity_inttable ... bench:     158,921.34 ns/iter (+/- 1,686.26)
test tests::u64_resize_intmap                    ... bench:      59,305.74 ns/iter (+/- 16,336.20)
test tests::u64_resize_inttable                  ... bench:         229.94 ns/iter (+/- 1.89)

On an actually decent CPU you can probably get faster numbers.

Legal-ish notice

I've done my best to respect the original MIT license as much as possible, but I may have overlooked some code to which it applied. If such is the case, please point out the problematic section and I will include the notice there.

Dependencies

~1MB
~14K SLoC