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

inttable

专门用于随机分布的u64键的HashMap

1 个不稳定版本

0.1.0 2024年7月10日

#990算法

无许可证

25KB
401

IntTable

这个crate主要存在是为了提供IntTable类型,一个u64 -> V的映射,不对其键进行哈希。这自然意味着它非常快,非常简单,但也意味着如果你的键不是随机的,你可能会自己伤害自己。

这封装了hashbrown的优秀HashTable。

这个crate在概念上与intmap相似,但更加专门。

在Intel(R) Core(TM) i7-10610U(c) CPU(SM)上,基准测试给出

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)

在实际上不错的CPU上,你可能会得到更快的数字。

法律性质的通知

我已经尽最大努力尽可能地尊重原始的MIT许可证,但我可能已经忽略了某些适用此许可证的代码。如果存在这种情况,请指出有问题的部分,我将包括该通知。

依赖关系

~485–780KB
~12K SLoC