3 个稳定版本
| 1.6.1 | 2020 年 12 月 21 日 |
|---|---|
| 1.0.1 | 2020 年 7 月 27 日 |
#2154 在 数据结构
190KB
4K SLoC
indexmap-amortized
一个纯 Rust 哈希表，在有限的意义上保留了插入顺序。
该包实现了紧凑的映射和集合数据结构，其中键的迭代顺序与其哈希或值无关。它保留了插入顺序（删除后除外），并允许通过哈希表键或数值索引查找条目。
该包是对 indexmap 的持续分支，它摊销了重新调整大小的成本。如果您不确定是否需要此功能，请查看 griddle 和 atone 的文档，它们提供了底层摊销。
背景
这受到了 Python 3.6 的新字典实现（它记住插入顺序，迭代速度快，内存紧凑）的启发。
其中一些功能被翻译到了 Rust 中，而另一些则没有。结果是 indexmap，它具有以下属性
- 顺序是 与哈希函数和键的哈希值无关。
- 迭代速度快。
- 在紧凑的空间中索引。
- 只要您不调用.remove().
- 它就像 Rust 的 libstd 中的 HashMap使用 hashbrown 作为内部表。
性能
IndexMap直接从其构建方式中得出几个性能事实，大致为
原始键值索引的哈希表和一个键值对的向量。
- 迭代非常快，因为它在密集的键值上。
- 删除速度快，因为它只在表中移动内存区域，并在向量中执行单个交换。
- 查找速度较快，因为初始的7位哈希查找使用SIMD，并且索引存储密集。但由于实际键值对是分别存储的，所以查找速度较慢。（当CPU缓存大小限制时可见。）
- 实际上，IndexMap在rustc的hashmap中进行了测试，见PR45282，在整个工作负载中性能大致相当。
- 如果您需要IndexMap的属性，或者其最佳性能点适合您的负载，它可能是最好的哈希表实现。
近期更改
- 1.6.1
- 包不再仅限nightly版本！
- 与上游版本1.6.1同步
- 1.0.1
- 请注意，包仅限nightly版本。
- 使基准测试再次编译。
- 1.0.0
- 初始发布。
依赖关系
~1.2–1.6MB
~27K SLoC