原文标题：Why doesn't Rust's BTreeMap have a with_capacity() method?


原文链接：https://www.nicolas-hahn.com/2020/11/30/btreemap-with-capacity/

公众号： Rust 碎碎念


翻译 by： Praying

声明：我发现这里已经有一篇解释，但是我认为它有点不太好理解，所以我希望我写的这篇文章能够更容易理解一些。

Rust 的 HashMap（以及 HashSet 和 Vec）集合都提供了一个初始化方法—— fn with_capacity(capacity: usize)，该方法预先分配足够的内存空间以存储capacity个元素。为什么 BTreeMap（和 BTreeSet）没有这个方法呢？

答案就在于这两个结构体在内存中布局的不同。简而言之，HashMap，就像 Vec，使用了一个 array（一个连续的内存块），要求在 O(1)的时间内插通过索引插入和查找元素。在 Vec 中，这很明显，但是在 HashMap 中，key 是被 hash 之后转为 value 在数组中的索引。

让我们来看一个已经存入四条记录的 HashMap（简单起见，我打算忽略真实的实现细节，比如 hash 碰撞时的装桶(bucket)）。它在本质上来讲是一个拥有四个元素的数组。下面是一个表示存有三条记录的 HashMap 的内存表示（每个格子为一个字节），以及若干个方格（亮绿色是内存中被填充的字节，深绿色是空的，但是被结构体保留）。

我们插入两个元素。现在我们需要分类更多内存以存放第五个元素。常见的实现是将数组的大小翻倍（以便于我们不必在每次插入时都进行分配）。在理想情况下，我们可以直接使用内存中接下来的四个字节。

（事实上，元素是不可能像这样被连续存放的，因为 hasher 会以近似随机分布的方式输入一个数组的索引）。

尽管如此，如果接下来的四个字节已经被分配给其他的结构体了会怎么样呢？

在这种情况下，我们需要把整个 HashMap 移动到内存中的某个可以容下八条记录的位置。不同于额外分配四个字节 ，这次我们需要先分配八个字节（将数据拷贝过去），然后析构原来的四个字节，这个开销就比较高了。

这里就是with_capacity()出现的原因。如果我们预先知道我们至少会有五个元素，那么预先分配八个字节就能让我们不必反复析构和重分配，这也是with_capacity()所做的事情。

那么 BTreeMap 为什么没有这个方法呢？来看一下BTree 是如何工作的。在下面这个例子中，我打算把它简化为一个普通的二分查找树。它们俩之间的本质区别在于，BST（二分查找树）的每个节点有一个值和两个指针，但是一个 BTree 的每个节点拥有一组值和一组指针：

这里为了便于上面的解释，它们暂时可以被视作等同。

BST 的每个节点由一个值和两个分别指向左右子节点的指针组成。下面是一个只有一个节点和值的BTreeMap（亮蓝色）。第二个和第三个暗蓝色的字节被保留用于指向子节点的指针，目前是空的。

当一个元素被插入时，一个新节点会被创建并且会分配属于它的内存。因为指针可以指向内存中的任意地址，所以不必要求节点像 HashMap 那样在内存中存储为连续的字节。如果我们打算插入一条新记录，会如下图所示：

我们可以把这条新记录放在内存中任意拥有三个字节的自由空间的位置。一个 BTreeMap 可以遍布在程序的内存各处，因为我们不必把记录连续存放。这意味着，我们将从不需要析构和重分配空间以拷贝记录（元素），所以我们不会在 BTreeMap 初始化时通过预先分配额外的内存空间来节省某些环节（在整个程序运行时）。

如果你明确想要预先分配以节省插入过程的时间，或者如果这时的延迟代价很大， BTreeMap::with_capacity()或许会有意义。但我想这种用例对于标准库函数而言过于特殊。在有用（usefulness）和臃肿之间存在一个微妙的平衡。

欢迎关注公众号：Rust碎碎念，获取更多好文章