判断质数的最快方法1597

前言

我打算开启一个新的系列，主要探讨工作中常用的性能优化手段、思路及如何发现性能瓶颈。今天，我想从源码的角度，和大家聊一聊集合类型的性能优化，特别是初始化时设置预估的初始大小的问题。为什么要这么做？让我们从源码开始探索。

集合类型简述

让我们看看.NET框架中的集合类型，如List、HashSet、Dictionary、Queue和Stack等。这些类型在日常编程中非常常见。在使用这些集合类型时，有一个特殊的构造函数，允许我们设置初始容量。

例如：

csharp

public List (int capacity)

public HashSet (int capacity)

为什么这些集合类型需要设置初始容量呢？这与它们的实现方式有关。接下来，我们深入源码探究原因。

List源码分析

List底层通过数组来存储元素，当数组空间不足时，会按照2倍的空间进行扩容。扩容涉及分配新数组、数据复制和GC回收旧数组，这都是较为昂贵的操作。提前设置合理的初始容量可以减少扩容次数，从而提高性能。

Queue和Stack的扩容逻辑与List相似，都是按照2倍的空间进行扩容。

HashSet和Dictionary源码分析

HashSet和Dictionary的扩容方式有所不同，涉及到重新哈希和可能的元素迁移。合理设置初始容量可以优化其性能表现。具体的扩容逻辑较为复杂，涉及到哈希表的实现细节。

Benchmark测试

为了量化设置初始容量的影响，我们可以进行Benchmark测试。测试结果会表明设置刚好需要的初始容量可以带来最大的性能提升。如果不设置初始容量，性能表现会最差。对于List，如果能预估大小，建议设置为2的N次方，因为List是按照2倍扩容的。对于Queue和Stack，也建议按照此规则设置初始容量。对于HashSet和Dictionary，由于扩容方式的复杂性，合理设置初始容量尤为重要。

对于HashSet和Dictionary的扩容策略，不同于List的直接扩容两倍，其扩容后的大小为大于两倍Size的第一个素数。这是为了确保哈希表在存储元素时能够尽可能地均匀分布，避免哈希冲突。在进行扩容操作时，我们可以定义一些常数和函数来实现这一策略。

我们设定两个常数，一个是哈希冲突的阈值HashCollisionThreshold，另一个是最大素数数组长度MaxPrimeArrayLength。我们还定义了一个素数HashPrime作为参考。

当需要扩容时，我们可以调用ExpandPrime函数。这个函数首先计算新的Size为旧Size的两倍。然后检查新的Size是否大于最大素数数组长度且大于旧Size。如果是，则直接返回最大素数数组长度。否则，获取大于新Size的第一个素数并返回。

GetPrime函数用于获取大于指定最小值min的第一个素数。如果min小于0，则抛出异常。我们从预定义的素数列表s_primes中寻找大于min的素数。如果没有找到，则通过计算获取素数。

s_primes是一个包含素数的数组，用于在扩容时提供素数参考。当需要计算较大素数时，我们可以使用IsPrime函数来判断一个数是否为素数。

从性能的角度来看，对于集合类型，指定初始容量是一个很好的实践。以下是几个关键点：

1. 如果知道集合将要存放的元素个数，最好直接设置该大小，这样可以获得最佳性能。比如在分页接，页大小固定为50、100，或者在进行Map操作时，前后元素数量一致，可以直接设置初始容量。

2. 如果不确定集合的初始大小，可以尝试预估元素数量，并选择一个接近的2的次方作为初始容量。这样可以尽量避免Resize操作。

3. HashSet和Dictionary在扩容时会选择大于当前Size的两倍的第一个素数作为新的容量，这与List的扩容策略有所不同。这种策略有助于提高哈希表的性能，减少哈希冲突的发生。