Lib.rs

一种将调整大小的负载分散到插入过程中的 HashMap 变体。

大多数哈希表实现（包括 Rust 标准库中的 hashbrown）必须偶尔“调整”映射的后备内存，因为元素的数量增长。这意味着分配一个新的表（通常大小加倍），并将所有元素从旧表移动到新表中。随着您表的增大，这个过程会越来越长。

对于大多数应用程序，这种行为是可以接受的——如果一些插入操作比其他操作慢，应用程序甚至不会注意到。如果映射本身相对较小，即使是那些“慢”的插入也相当快。同样，如果您的映射一段时间内增长，然后停止增长，那么应用程序的“稳定状态”根本不会看到任何调整大小的暂停。

调整大小成为问题的地方在于使用映射来保持不断增长的状态的应用程序，其中尾部延迟很重要。在大型规模上，当大多数插入操作都在微秒以下时，一个映射插入操作需要30毫秒是完全不可接受的。更糟糕的是，这些调整大小暂停可能会累积，导致尾部延迟的显著峰值。

此 crate 实现了一种称为“增量调整大小”的技术，与上面概述的常见“一次性”方法相反。其核心思想非常简单：不是在立即将所有元素移动到调整大小的映射中，而是在每次插入时移动几个元素。这分散了移动元素的成本，使得每个插入都稍微慢一点，直到调整大小完成，而不是一次插入就变得非常慢。

然而，这种方法并非没有代价。在调整大小进行时，必须保留旧表（因此内存不会被立即回收），并且所有读取都必须检查旧表和新表，这使它们变慢。只有当调整大小完成后，才能回收旧表并恢复完整的读取性能。

为了帮助您决定此实现是否适合您，以下是关于此实现与标准库map进行比较的便捷参考。

• 所有插入操作所需时间大致相同。在调整大小后，它们会暂时变慢，但仅相对较慢。
• 调整大小后不会立即回收内存。
• 在调整大小后的一段时间内，读取和删除旧键或缺失键会变慢。
• 增量map在堆栈上略微大一些。
• 调整大小的“效率”略低，因为一次性调整大小将项目从小表移动到大数据表是批量进行的，而增量则进行一系列插入。

基准测试

在benches/vroom.rs中有一个愚蠢但具有说明性的基准测试。它只是连续运行大量的插入操作，并测量每个操作的持续时间。问题很快就会显现出来

$ cargo bench --bench vroom > vroom.dat
hashbrown::HashMap max: 38.335088ms, mean: 94ns
griddle::HashMap max: 1.846561ms, mean: 126ns

您可以看到，标准库实现（通过hashbrown）有一些相当严重的延迟峰值。通过时间线延迟图（misc/vroom.plt）可以更清楚地看到这一点

随着映射的增长，调整大小发生的频率较低，但它们在发生时也会更长。在griddle中，这些峰值几乎都消失了。剩下一个小线性成分，我认为这来自于找到必须移动的元素所在的桶所需的工作量。

实现

Griddle使用了hashbrown::raw API，这使得它能够利用已经投入使hashbrown尽可能快的工作。Griddle的关键不同部分位于src/raw/mod.rs。

Griddle的目标是与hashbrown尽可能紧密地结合，无论是代码还是API。 src/map.rs和src/set.rs几乎与hashbrown中相应的文件相同（我鼓励您比较它们！），除了移除了一些（目前； #4）不受支持的API之外。像hashbrown一样，griddle公开了一个raw模块，它允许您在griddle的表变体之上构建自己的映射实现。

为什么是“griddle”？

您可以通过使用griddle来摊销制作hashbrown的成本吗？

许可证

根据您的选择，许可如下

• Apache License，版本2.0（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

。

贡献

除非您明确声明，否则任何有意提交以供您包含在作品中的贡献，根据Apache-2.0许可证的定义，应按上述方式双重许可，不得附加任何额外条款或条件。