Small-Map

一个专为少量数据设计的内联SIMD加速哈希表。

用法

use small_map::SmallMap;
// Don't worry about the 16 here.
// When the size grows, it will automatically switch to heap impl.
type MySmallMap<K, V> = SmallMap<16, K, V>;

let mut map = MySmallMap::new();
map.insert(1_u8, 2_u8);
assert_eq!(*map.get(&1).unwrap(), 2);

通常您可以用这个映射表处理生命周期短和键值较小的数据，例如http或RPC头部。

您可以用它像其他普通哈希表一样使用，无需担心其大小。

性能

SmallMap的性能取决于容量、键/值大小和操作场景。

建议设置为16（或32），因为SSE2可以在一条指令内搜索16个条目。仅推荐用于小型键值，如数字和字符串。

以下是一个大小为16，键/值为u8的基准结果。这个基准测试是在Intel Xeon上进行的。

[!注意] 在测试场景中，与HashBrown相比，可以节省25%~43%的CPU；与std HashMap相比，可以节省25%~54%的CPU。

工作原理

与SmallVec类似，对于少量数据的HashMap，内联数据可以避免堆分配开销并提高性能。

SmallMap内联了一个固定大小的顺序结构，并参考了swisstable的设计，在组单元中存储数据的哈希值，并使用SIMD来加速搜索。

当数据容量超过内联容量时，数据将转移到由hashbrown实现的HashMap中。

致谢

Hashbrown 项目大量参考并复制了此项目，是一个非常优雅和高效的实现。