为何C# Hashtable类内置素数数组未包含全部素数

首先明确源码注释中写死的扩容规则：扩容时先计算旧容量的2倍，再取数组中第一个大于该值的素数作为新容量，所有设计逻辑都围绕这个规则展开。 #

1. 为什么没有5、13这类素数 #

预定义素数序列的相邻元素严格遵循前一个素数 * 2 < 后一个素数的规律，不符合这个要求的素数就算加进去也完全用不上：

• 第一个素数是3，3*2=6，下一个素数取大于6的7，5小于6，没有任何场景会选中5，不需要加入数组
• 7*2=14，下一个素数取大于14的17，13小于14，就算加入数组也不会被选中，属于冗余数据
• 后续所有素数都遵循这个筛选规则，不会出现比前一个素数2倍更小的值

你提到的例子：容量为7时扩容计算得2*7=14，13小于14，本身就不在候选范围内，所以数组里不需要保留13。 #

2. 设计的核心目的 #

• 保证性能稳定性：每次扩容后容量至少翻倍是哈希表平摊O(1)复杂度的前提，如果扩容后容量涨幅太小，会导致扩容频率大幅升高，严重拖累增删查操作的性能
• 减少冗余开销：所有预定义的素数都是实际扩容时会用到的值，既减少数组本身的内存占用，也能加快查找符合要求素数的速度
• 满足哈希算法要求：容量为素数可以保证双散列算法不会出现死循环，双散列的步长函数和素数容量天然互质，不会出现所有探测位置都被占满的极端情况。

内容的提问来源于stack exchange，提问作者Windings-Lab