秩序

快速、基于向量的映射实现，保留插入顺序。

• 映射实现为一个二叉树，存储在 Vec 上，每个条目只有两个字节的额外空间用于64位架构上的记账。
• 使用快速且随机分布良好的哈希函数来平衡树。秩序不保证树会完全平衡，但通常情况下键查找接近 O(log n)。
• 树遍历始终是广度优先的，并且在一个单一的连续内存块中发生，这使得它对缓存友好。
• 遍历所有条目始终是 O(n)，与 Vec<(K, V)> 相同。
• 没有桶，因此在扩展映射时不需要重新分桶。

何时应该使用它？

• 您需要保留映射的插入顺序。
• 遍历映射对性能非常敏感。
• 您的平均映射条目少于 100 个。
• 在开始创建映射时，您没有关于映射最终大小的先验知识。
• 从映射中删除条目非常、非常罕见。

基准测试

• 所有图表显示时间以纳秒为单位，越小越好。
• 所有基准测试都使用 -C target-cpu=native 编译，以利用 aHash。

映射构造

虽然秩序中的插入速度随着映射大小的增加而逐渐变慢，但由于重新分桶的成本，HashMap 的增长速度也在逐渐变慢。

使用预分配内存的映射构造

使用预分配内存，秩序对于少量条目仍然更快。

通过键查找值的平均时间

随着地图大小的加倍，由于其~O(log n)特性，Ordnung的成本大致呈常数级跳跃，但它仍然与快速的HashMap具有竞争力。

许可证

此代码在MIT许可证和Apache许可证（版本2.0）的条款下分发，您可以选择适合您的许可证。

有关详细信息，请参阅LICENSE-APACHE和LICENSE-MIT。