[C#]Hash算法与质数
说明：文中所有的测试，随机数均为调用
System.Random实例的Next(int.MaxValue)方法获取。
从哈希算法的实现出发
我们在C#中日常会用到的哈希算法具体实现，当属Dictionary与HashSet类。
C#代码中对这两个的实现，大体是通过构建数据桶，并与链表实现对应关系以实现数据的存储与查询。其中数据桶的构建就是一个很有意思的点。
数据桶，存储key的哈希码，并取哈希码所在数据桶内的位置作为value列表在value数组内的下标。具体可读C#源码，内部计算流程是通过哈希码求数据桶长度的余数，作为该哈希码对应数据桶内的id。
.Net对Dictionary与HashSet的数据桶使用了质数作为数据桶长度，并以质数进行扩容，所以令人好奇这是为什么？如果采用余数作为求余的底数，那么似乎采用数组自动扩容的成倍算法也可以实现。
网上有一些参考资料很有价值，转载一篇文章。文章内已说明推导过程：
最终的桶
index = key%m = key - xm = key - f(key/m)m。 这里的 f 函数用于向下取整。可以看到，最终结果是等价于key - f(key/m)m的。那么我们就以进来的key = 2n(即2的倍数)，桶为4来举例。那么结果为2n - f(2n/4)*4，简化后是2(n - f(n/2)*2)。可以看到这其实就是n - f(n/2)*2的两倍，而n - f(n/2)*2则是key = n装进长度为2的桶的公式，因此可以知道在这种情况下，它退化为了长度为2的桶。而又因为key = n装进长度为2的桶可能为0或1，它的两倍也就是0或2，即这种情况下(key为2n，桶长为4)，它只会将值hash到0,2这两个桶里，并不均匀。其他合数亦是如此，只要有公约数，就会退化，无法均匀分布。
概括以上内容，即以质数对数据桶进行扩容，可以尽可能令数据均匀分布，减少哈希冲突。
若观众无心看后文繁多的测试内容，先说明我测试之后的结论：
使用质数进行数据桶扩容，确实可以令数据更均匀分布，提高哈希命中率；该提升并非特别显眼，但作为基础操作，积少成多则可以带来可观的性能效果。
下面我将进行多个测试，以说明我的结论。
对质数与数据桶容量的测试
1.质数是否是减少哈希冲突的唯一解？
之所以引入质数，是因为在有了一批数据之后，将数据桶设计为质数长度时数据更趋向于均匀分布。但是质数并非唯一，数据本身、数据的数量与数据桶的长度比都是影响哈希碰撞的因素。
由于数据本身在实际使用时并非我们完全可控，因此我们便不在此处考虑数据本身的问题，只将数据作为随机数。
下一步，我们通过生成一些随机数，看看随着向Dictionary当中插入数据、数据桶自动扩容，哈希命中率有多少（以下曲线图分别使用质数扩容与成倍扩容两种算法进行对比）：
数据桶使用率与数据桶尺寸关系图
上图中横轴标识插入数据数量，单位100；上图表示了数据桶通过质数进行扩容与成倍进行扩容，数据桶的使用率变化曲线的对比；下图则表示随着插入数据的不同，两种算法下数据桶的实际容量的变化曲线对比。
通过这两幅图可以看出，相同数据桶容量下，数据桶的使用率是逐渐降低的，即哈希命中率逐渐降低；而伴随着数据桶扩容，哈希命中率也会瞬间提升。两种算法均显示出了同样的特征。
2.固定数据桶容量的测试
既然哈希命中率跟数据桶容量息息相关，那么我们可以通过固定数据桶容量再进行测试进行对比。
我们将成倍算法下的数据桶固定为128，将质数算法下的数据桶固定为131。选这两个数是因其值相近，我们将取从66-128内的多个值进行哈希命中率的统计。
| 插入随机数数量 | 质数算法平均哈希命中率 | 成倍算法平均哈希命中率 |
|---|---|---|
| 66 | 0.7965 | 0.7923 |
| 78 | 0.7635 | 0.7472 |
| 90 | 0.7219 | 0.7207 |
| 103 | 0.6966 | 0.6884 |
| 115 | 0.6618 | 0.6625 |
| 128 | 0.6365 | 0.6341 |
上表的数据均通过随机运算百次之后平均求取而得。可以看到两种算法的平均哈希命中率相差不大，质数算法略高于成倍算法。
除了上述测试，我们还可以分别向两种算法的实例中填充数据桶容量数量的随机数据，以次检测数据桶满时的哈希命中率。通过我的计算，相差不大，且多数情况下质数算法略高于成倍算法，但无绝对。
3.某些实际使用环境下的测试
在我们实际使用时，往往会依据自身需求而使用，因此无论随机数的质量、数量都不固定。所以我就分别向两种算法中依次填入1-100个随机数，并分析其哈希命中率。
首先我们来看在1-100个数据下，数据桶容量的变化曲线：
插入1-100个随机数时，数据桶容量变化图
之后分别进行1000次随机测试，获取平均数据曲线如下：
插入1-100个随机数时的数据桶使用率平均值
通过千次数据均值运算后，曲线已变得平滑很多。除了依旧反映出哈希命中率随数据桶容量变化而起伏外，也可以看出相较成倍扩容算法，质数扩容算法下的哈希命中率的峰值要大于成倍扩容算法的峰值；而二者低值则近似，并无峰值如此明显的差距。
4.回到第一个测试
第一个测试中，我们通过插入多个值而绘制出了一条哈希命中率的曲线。现在，让我们把它多进行几次求取均值后再观察其命中率曲线：
每多插入100个随机数哈希命中率曲线
这次横轴每个刻度表示随机插入n*100个随机数。这个时候观察哈希命中率曲线，除了更平滑之外，也可以更明显看出质数扩容相较于成倍扩容的哈希命中率确实更高一些。也需要看到，无论何种扩容算法，哈希命中率主要还是跟随扩容时机进行波动。
总结：无论如何分析上述测试案例的内容，它们都向我们说明了用质数对数据桶进行扩容，从数学证明或实际使用都是更优的选择。虽然这种优化可能只有一点点微不足道，但是作为基础操作的哈希算法，在工程项目中使用越频繁，其所带来的性能优化就越发可观。
