浅谈容器扩容参数

在编码时我们经常使用各种容器来做基本的数据结构，比如 C++ STL 中的 vector, C# 的 List 和 Dictionary 等，这篇文章我们简单聊一下这些容器在发生扩容时的扩容系数选择的话题

1. 什么是容器的扩容

虽然容器的使用方法和特点各异，但整体来说底层的存储结构基本上都是基于数组，例如 C++ 中的 vector、C# 中的 List 底层都是使用数组来存放数据，那么容器中的数组长度如何确定呢？

• 容器会进行预分配空间（capacity）
• 通常容器会提供接口，让我们在初始化时指定容器中元素的个数（size 或 length），容器底层会根据元素个数分配对应的数组长度
• 如果初始化时没有提供元素个数，则会初始化一个默认长度（vector 和 List 默认都是4）
• 那么当容器元素超过预分配空间时，会重新分配更多的空间，以存放更多的元素，这个过程就是扩容
  容器扩容的操作：
• 分配新的内存空间
• 搬移元素，将元素全部复制到新分配的内存空间
• 释放旧空间

2. 容器扩容的时机

那么容器的扩容发生在什么时候呢？

• 第一种情况：当容器调用添加元素（push_back, Add等）的方法时，如果当前 capacity 无法容纳新元素，会触发扩容机制
• 第二种情况：基于哈希表的容器（如Dictionary）当哈希冲突超过某个阈值时，触发扩容机制

3. 容器扩容的系数选择逻辑

扩容时分配多大的新空间比较合适呢？（此处综合考虑到普遍情况下的内存分配、元素复制消耗、扩容次数等），假设当前容量是，那么新分配的容量为 ，对于不同容器，不同的版本实现，此处的 不尽相同

3.1 C++ STL vector 的扩容系数

• VC 版本的 vector 扩容系数为 1.5，每次扩容时分配 1.5 倍的新空间
• gcc 版本的 vector 扩容系数为 2，每次扩容时分配 2 倍的新空间

3.2 C# List 的扩容系数

查看 List源码可知，C# List 的扩容系数是 2，扩容是分配 2 倍新空间

对于 vector 和 List 来说，1.5 的扩容系数是比 2 更好的选择。使用扩容系数 2 时产生的问题在于，每次新分配的空间必然刚好大于之前分配的空间之和，之前分配的空间无法复用，使用1.5 是一个更好的选择，便于复用之前分配过的空间，详情可以参考 MiloYip的回答

3.3 C# Dictionary 的扩容系数

和列表不同，Dictionary 由于底层哈希桶数组的存在，添加元素时需要考虑元素哈希值冲突，扩容应该能够尽量避免哈希冲突的产生，所以 Dictionary 的扩容方法是，取小于 的最小质数，为什么要取质数呢？这是因为哈希桶的长度为质数时，能够使得哈希值分配更均匀，最大程度的减少哈希冲突的发生，理论依据简单概括：

• 偶数除以偶数，得到的余数一定是个偶数。
• 偶数除以质数，小于质数得到的余数是偶数，大于质数得到的是奇数。
• 奇数除以偶数，得到的余数一定是个奇数。
• 奇数除以质数，小于质数得到的余数是奇数，大于质数得到的是偶数。

陷入以质数做除数，得到的结果的可能性更多，也就说明了质数能够使数据分配的更均匀，达到了减少哈希冲突的目的。