Leapfrog

Leapfrog crate 包含两种哈希表实现，HashMap，这是一个单线程的哈希表，以及 LeapMap，这是 HashMap 的快速并发版本，所有操作都可以从任何数量的线程中并发执行。如果键和值类型支持原子操作，则映射是无锁的；当键或值的原子支持不存在时，则在该非原子类型上对映射内的操作使用高效的自旋锁，锁定非常细粒度。

这两个映射在已测试的基准测试中的性能都很好。与 HashMap 相比，HashMap 的性能在 1.2 到 1.5 倍之间。与 RwLock<HashMap> 相比，在 16 个核心上，LeapMap 的速度大约是 13.5 倍。它还非常适用于多个工作负载，直到高核心数。基准测试结果可以在 rust hashmap benchmarks 中找到。然而，这些基准测试的使用案例有限，应扩展到更广泛的范围。尽管如此，对于这些基准测试，LeapMap 是最快的映射。

有关 API 的更多详细信息以及与 std::collections::HashMap 的比较，请参阅 crate 文档。

最近更改

这些映射的实现最近已更新以存储键，因此两者的 API 都更接近于 std::collections::HashMap。现在还支持使用可选的 "serde" 功能进行 serde。映射现在还具有迭代器支持。默认哈希器已更改为标准库中的抗 DOS 哈希器。

已添加 "stable_alloc" 功能标志，以便可以将 crate 与稳定工具链一起使用。

当前限制

目前尚不支持 rayon，且尚无 Map 的 Set 版本。

性能

在16核心AMD 3950x CPU上对LeapMap在读取密集型工作负载下的结果快照如下（吞吐量以Mops/秒计，括号内为核心数，性能与std::collections::HashMap使用RwLock的性能比较）

在12核心M2 Max上的结果是以下（同样，所有值都是相对于std::collections::HashMap）

在其他用例的基准测试中，LeapMap的LeapMap速度甚至更高。

对于单线程Leapfrog的HashMap，对随机插入和删除的基准测试（此基准测试为C++哈希表的基准测试的移植）显示，Rust std HashMap的吞吐量约为40Mops/s，Leapfrog HashMap的吞吐量约为50Mops/s，使用标准库中的默认哈希器，与链接基准测试的C++哈希表具有竞争力。

探测

这两个映射都使用相同的Leapfrog探测策略，更多关于该策略的信息可以在Jeff Preshing的Leapfrog探测博客文章中找到。该映射的C++实现可以在他的Junction库中找到，这是此实现的起点。那些映射不支持键和因此没有冲突，而这些映射有。探测策略需要每个键值对8个字节，并且存储额外的8个字节用于存储哈希键，以便在比较时不需要重新哈希。

特性

通过"serde"特性，有可选的serde支持。

与稳定版一起使用

此crate需要allocator_api特性，该特性仅在nightly版本中可用。要启用使用稳定工具链的crate，已添加了"stable_alloc"特性。

如果allocator_api特性不再处于实验性状态，此功能标志将被删除。

许可证

此crate可在Apache License，Version 2.0下获得许可，请参阅此处或此处，或者MIT许可，请参阅此处或此处，您可以选择。它可以免费用于商业和非商业应用，只要您在文档中的某处发布所选许可文件的内容。