indexmap

一个纯Rust哈希表，在有限的意义上保留了插入顺序。

此crate实现了紧凑的映射和集合数据结构，其中键的迭代顺序与其哈希值或值无关。它保留插入顺序（除删除后外），并允许通过哈希表键或数值索引查找条目。

注意：此crate最初以ordermap的名称发布，但更名为indexmap以更好地反映其特性。现在，ordermap crate作为indexmap的包装存在，具有更强的排序特性。

背景

这受到了Python 3.6的新字典实现（它记得插入顺序，迭代速度快，内存紧凑）的启发。

其中一些功能被翻译到了Rust中，而另一些则没有。结果是indexmap，一个具有以下特性的哈希表：

• 顺序与哈希函数和键的哈希值无关。
• 迭代速度快。
• 在紧凑的空间中索引。
• 只要你不调用.remove()、.swap_remove()或其他显式更改顺序的方法，它就保留插入顺序。替代的.shift_remove()则保留了相对顺序。
• 像Rust的libstd HashMap一样，使用hashbrown作为内部表。

性能

IndexMap直接从其构建方式中推导出一些性能事实，大致如下：

原始的键值索引哈希表和一个键值对向量。

• 迭代非常快，因为它在密集的键值上。

• 删除操作速度快，因为它只在表中移动内存区域，并在向量中使用单个交换。

• 查找操作相对较快，因为初始的7位哈希查找使用SIMD，索引密集存储。但由于实际键值对存储在单独的位置，查找操作也会相对较慢。（当CPU缓存大小限制时可见。）

• 实际上，在PR45282中，IndexMap被测试用作rustc中的哈希表，整个工作负载的性能大致相当。

• 如果您希望IndexMap具有的特性或其最强的性能点适合您的负载，它可能是最好的哈希表实现。

近期更改

请参阅RELEASES.md。