C# Hashtable.cs 没有所有素数

Question

为什么 Hashtable 类不包含所有素数？ 所以基本素数有那些数字 https://en.wikipedia.org/wiki/Prime_number

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

但是 C# 库中的 Hashtable.cs 中的代码有这个

// Table of prime numbers to use as hash table sizes. 
// A typical resize algorithm would pick the smallest prime number in this array
// that is larger than twice the previous capacity. 
// Suppose our Hashtable currently has capacity x and enough elements are added 
// such that a resize needs to occur. Resizing first computes 2x then finds the 
// first prime in the table greater than 2x, i.e. if primes are ordered 
// p_1, p_2, ..., p_i, ..., it finds p_n such that p_n-1 < 2x < p_n. 
// Doubling is important for preserving the asymptotic complexity of the 
// hashtable operations such as add.  Having a prime guarantees that double 
// hashing does not lead to infinite loops.  IE, your hash function will be 
// h1(key) + i*h2(key), 0 <= i < size.  h2 and the size must be relatively prime.
public static readonly int[] primes = {
    3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
    1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
    17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
    187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
    1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

我不太明白为什么会这样？

编辑1: 我的意思是，我不是在谈论为什么它这么小。为什么这个数组中没有 5 或 13。例如:如果我们 7*2 = 14，为什么最接近的是 11，而不是 13？

Answer 1

这些素数用于确定哈希表的大小。例如，我们可以使其长度为 197 个桶或槽。但区分 197 和 199 的大小是没有意义的，因为无论如何，哈希表至少比其项目数长大约 30%，以避免出现太多的键冲突。并且，正如评论所说，“调整大小首先计算 2x，然后找到表中第一个大于 2x 的素数”。因此，更细粒度的步骤没有任何优势。

因此，他们选择了更经济的方法。对于较大的素数，此列表中的两个连续素数相差约 20%。对于较小的素数，甚至还有更大的一步。但这对内存使用的影响非常小。

{      3,       7}, delta % = 133.33
{      7,      11}, delta % =  57.14
{     11,      17}, delta % =  54.55
{     17,      23}, delta % =  35.29
{     23,      29}, delta % =  26.09
{     29,      37}, delta % =  27.59
{     37,      47}, delta % =  27.03
{     47,      59}, delta % =  25.53
{     59,      71}, delta % =  20.34
{     71,      89}, delta % =  25.35
{     89,     107}, delta % =  20.22
{    107,     131}, delta % =  22.43
{    131,     163}, delta % =  24.43
{    163,     197}, delta % =  20.86
{    197,     239}, delta % =  21.32
{    239,     293}, delta % =  22.59
{    293,     353}, delta % =  20.48
{    353,     431}, delta % =  22.10
{    431,     521}, delta % =  20.88
{    521,     631}, delta % =  21.11
{    631,     761}, delta % =  20.60
{    761,     919}, delta % =  20.76
{    919,    1103}, delta % =  20.02
{   1103,    1327}, delta % =  20.31
{   1327,    1597}, delta % =  20.35
{   1597,    1931}, delta % =  20.91
{   1931,    2333}, delta % =  20.82
{   2333,    2801}, delta % =  20.06
{   2801,    3371}, delta % =  20.35
{   3371,    4049}, delta % =  20.11
{   4049,    4861}, delta % =  20.05
{   4861,    5839}, delta % =  20.12
{   5839,    7013}, delta % =  20.11
{   7013,    8419}, delta % =  20.05
{   8419,   10103}, delta % =  20.00
{  10103,   12143}, delta % =  20.19
{  12143,   14591}, delta % =  20.16
{  14591,   17519}, delta % =  20.07
{  17519,   21023}, delta % =  20.00
{  21023,   25229}, delta % =  20.01
{  25229,   30293}, delta % =  20.07
{  30293,   36353}, delta % =  20.00
{  36353,   43627}, delta % =  20.01
{  43627,   52361}, delta % =  20.02
{  52361,   62851}, delta % =  20.03
{  62851,   75431}, delta % =  20.02
{  75431,   90523}, delta % =  20.01
{  90523,  108631}, delta % =  20.00
{ 108631,  130363}, delta % =  20.01
{ 130363,  156437}, delta % =  20.00
{ 156437,  187751}, delta % =  20.02
{ 187751,  225307}, delta % =  20.00
{ 225307,  270371}, delta % =  20.00
{ 270371,  324449}, delta % =  20.00
{ 324449,  389357}, delta % =  20.01
{ 389357,  467237}, delta % =  20.00
{ 467237,  560689}, delta % =  20.00
{ 560689,  672827}, delta % =  20.00
{ 672827,  807403}, delta % =  20.00
{ 807403,  968897}, delta % =  20.00
{ 968897, 1162687}, delta % =  20.00
{1162687, 1395263}, delta % =  20.00
{1395263, 1674319}, delta % =  20.00
{1674319, 2009191}, delta % =  20.00
{2009191, 2411033}, delta % =  20.00
{2411033, 2893249}, delta % =  20.00
{2893249, 3471899}, delta % =  20.00
{3471899, 4166287}, delta % =  20.00
{4166287, 4999559}, delta % =  20.00
{4999559, 5999471}, delta % =  20.00
{5999471, 7199369}, delta % =  20.00