ordermap

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

该 crate 实现了紧凑的映射和集合数据结构，其中键的迭代顺序与其哈希值或值无关。它在大多数修改操作中保持插入顺序，并允许通过哈希表键或数值索引查找条目。

注意：该 crate 原本是成为 indexmap 的东西，曾一度被废弃，但后来 ordermap 作为 indexmap 的包装器返回，具有更强的排序属性。

背景

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

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

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

自0.5版本重新引入以来，ordermap 也使用了其条目顺序来为 PartialEq 和 Eq 提供支持，而 indexmap 则将相同条目在 任何 顺序下视为相等，以便与 HashMap 的语义兼容。使用顺序可以更快，并且还允许 ordermap 实现 PartialOrd、Ord 和 Hash。

性能

OrderMap 直接从其构建方式中得出一些性能事实，大致如下

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

• 作为一个包装器，OrderMap 在大多数操作中应该与 IndexMap 保持相同的性能，主要区别在于删除策略。
• 迭代非常快，因为它是在密集的键值上进行的。
• 查找速度较快，因为初始的7位哈希查找使用了SIMD，并且索引是密集存储的。但查找也相对较慢，因为实际的键值对是分别存储的。（当CPU缓存大小限制时可见。）
• 在实践中，OrderMap 已经在 PR45282 中的 rustc 中进行了测试，整个工作负载的性能大致相当。
• 如果您想使用 OrderMap 的特性，或者其最强性能点适合您的负载，它可能是最佳的哈希表实现。

近期更改

请参阅 RELEASES.md。