UniqueStringList 再探
一个有用的类，现在速度提升一倍。
引言
本文介绍了一个名为UniqueStringList的类，我多年来一直使用它的各种版本。我曾认为它已经完全优化，但最近我使用了一些新技术，使其速度加倍，并想与您分享。
背景
重用同一个不同的字符串值的副本称为字符串驻留。字符串驻留之所以好，主要有两个原因：
- 它减少了内存消耗：100,000个指向同一个字符串的引用，远比100,000个指向100,000个相同字符串副本的引用要好。
- 它加快了字符串比较速度：如果两个字符串引用指向同一个位置，您无需比较任何字符就知道它们是相等的。
C#编译器在构建程序集时会自动驻留源文件中的所有字面量字符串。您可能已经看到过String.Intern()方法。不要在您的代码中使用它！添加到此驻留池中的任何字符串都无法移除，并且会一直存在直到您的应用程序关闭！
虽然这本身不是字符串驻留，但在我的.NET 中的序列化优化文章中，最大的优化之一是为每个要序列化的唯一字符串生成一个令牌。它不会影响序列化端的字符串，但确保在反序列化端，只有一个字符串副本存在——您可以将其视为自动驻留。
如果可以在源头就防止重复字符串，这将非常有益。想象一下读取一个包含10万行的CSV文件，假设某个字符串出现在每一行（例如，“未发现故障”）。由于每行是单独读取的，并且与它上面和下面的行没有联系，您将在内存中存储该相同字符串的10万个副本。如果您可以驻留从单行读取的所有字符串，那么您最终只会有一个每个唯一字符串的副本，这可以节省数兆字节的内存。
读取XML文件或从中间层获取数据并为每个项创建POCO（普通旧类对象）时，情况也类似，您很可能会遇到字符串重复，除非您自己进行删除。
想象一下在网格中显示大量数据。您点击标题中的筛选图标，经过短暂的延迟后，它会显示一个要筛选的唯一项列表。如果生成此列表的过程如此之快，以至于它立即出现，那不是很棒吗？
一个更简单的场景是简单地询问该字符串是否之前见过，如果见过，则可能跳过某些处理。
当然，驻留字符串的过程并非没有成本，它需要一些时间，所以花费的时间越少越好，这正是本文的主题。另外，不要忘记您将通过减少内存分配来节省一些时间，因此最终您可以两全其美：节省大量内存，同时几乎没有额外开销。
因此，我们这里有几个字符串驻留/识别重复项的场景，但需求略有不同：
- “令牌化”场景需要返回一个索引，并且该索引之后不能更改。此外，了解该索引是针对现有字符串还是新字符串会很有帮助。
- “重用相同字符串”场景（即真正的驻留）需要一个字符串作为输出——索引无关紧要，它是不是新字符串也不重要。
- “我之前是否见过这个字符串”场景只需要返回一个
bool。 - “给我所有唯一的字符串”场景在添加时不需要返回任何内容——只需要一种方法在最后将所有字符串提取出来。
我最终想出的代码使用了三个来源的思路：
- 来自.NET 中的序列化优化文章的原始代码。使用黄金素数（Golden Primes）的概念，并为较低的容量加速桶计数，同时还有一个加载因子（LoadFactor），使桶的数量多于容量，以减少哈希码冲突的可能性。
- 在Reflector中看到的.NET 4.0
HashSet<T>代码。我没有直接将字符串存储在数组中，而是使用了一个Slot结构，该结构还存储了字符串的哈希码以及下一个Slot的索引。存储哈希码消除了许多字符串比较和预计算，尤其是在扩展容量时。Next索引有助于处理冲突，确保达到最少的比较次数。在Reflector中查看HashSet<T>时，我还发现在System.Collections命名空间中有一个HashHelpers类，其中预计算了许多素数。可惜的是，这个类（以及System.Collections.Generic中一个几乎相同的同名类）被标记为internal。 - 由rob tillaart撰写的一篇非常有趣的《在C#中使用乘法移位优化整数除法》文章，该文章展示了如何加快整数除法，并间接加快模运算。我的代码不使用除法运算，但确实使用模运算来确定给定哈希码使用的哈希桶。
为了提高可重用性，我创建了一个MathHelper类和一个QuickDivideInfo结构，这些代码列在下面。它们结合了预计算黄金素数和预计算它们快速除法信息（求模运算）的思想。
在QuickDivideInfo结构中，只有ModuloPositive()方法被UniqueStringList实际使用，但我包含了其他方法以示完整性，并针对所有可能的int分子进行了检查。除了int.MinValue之外，所有其他值返回的结果与“%”运算符完全相同，但速度快3倍。
QuickDivideInfo 结构
我的测试时间表明，所有这些方法都可以内联。
我还添加了不安全（unchecked）语句来包围算术运算，因为没有溢出的可能性。因此，使用“检查算术溢出/欠流”选项进行编译不会影响速度的提升。
public struct QuickDivideInfo
{
public readonly int Divisor;
public readonly long Multiplier;
public readonly int Shift;
public QuickDivideInfo(int divisor, long multiplier, int shift)
{
Divisor = divisor;
Multiplier = multiplier;
Shift = shift;
}
public int Divide(int numerator)
{
return numerator < 0 ? DivideNegative(numerator) : DividePositive(numerator);
}
public int DividePositive(int numerator)
{
unchecked
{
return (int) ((numerator * Multiplier) >> Shift);
}
}
// Does not work with int.MinValue as the numerator!
public int DivideNegative(int numerator)
{
unchecked
{
return (int) -((-numerator * Multiplier) >> Shift);
}
}
public int Modulo(int numerator)
{
return numerator < 0 ? ModuloNegative(numerator) : ModuloPositive(numerator);
}
public int ModuloPositive(int numerator)
{
return numerator - DividePositive(numerator) * Divisor;
}
// Does not work with int.MinValue as the numerator!
public int ModuloNegative(int numerator)
{
return numerator - DivideNegative(numerator) * Divisor;
}
}
MathHelper
为保持完整性，我还添加了Microsoft使用的普通预计算素数，并预计算了它们的快速除法信息。
public static class MathHelper
{
public const int Lower31BitMask = 0x7fffffff;
// Allows quadrupling of bucket table size for smaller sizes then
// reverting to doubling.
static readonly int[] GoldenPrimeAccelerators =
new[]
{
389, 1543, 6151, 24593, 98317
};
// Based on Golden Primes (as far as possible from nearest two powers of two)
// at http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
// and Optimizing integer divisions with Multiply Shift in C#
// at <a href="FindMulShift.aspx">FindMulShift.aspx</a>
static readonly QuickDivideInfo[] GoldenPrimes =
new[]
{
new QuickDivideInfo(53, 1296593901, 36), // acceration skip
new QuickDivideInfo(97, 354224107, 35), // acceration skip
new QuickDivideInfo(193, 356059465, 36), // acceration skip
new QuickDivideInfo(389, 2826508041, 40),
new QuickDivideInfo(769, 2859588109, 41), // acceration skip
new QuickDivideInfo(1543, 356290223, 39),
new QuickDivideInfo(3079, 714200473, 41), // acceration skip
new QuickDivideInfo(6151, 178753313, 40),
new QuickDivideInfo(12289, 1431539267, 44), // acceration skip
new QuickDivideInfo(24593, 2861332257, 46),
new QuickDivideInfo(49157, 1431510145, 46), // acceration skip
new QuickDivideInfo(98317, 2862932929, 48),
new QuickDivideInfo(196613, 715809679, 47),
new QuickDivideInfo(393241, 1431564749, 49),
new QuickDivideInfo(786433, 1431653945, 50),
new QuickDivideInfo(1572869, 2863302429, 52),
new QuickDivideInfo(3145739, 2863301519, 53),
new QuickDivideInfo(6291469, 2863305615, 54),
new QuickDivideInfo(12582917, 1431655197, 54),
new QuickDivideInfo(25165843, 1431654685, 55),
new QuickDivideInfo(50331653, 2863311247, 57),
new QuickDivideInfo(100663319, 2863310877, 58),
new QuickDivideInfo(201326611, 2863311261, 59),
new QuickDivideInfo(402653189, 357913937, 57),
new QuickDivideInfo(805306457, 2863311215, 61),
new QuickDivideInfo(1610612741, 1431655761, 61),
};
// Based on the list of primes in Systems.Collections.Generic.HashHelpers
static readonly QuickDivideInfo[] Primes =
new[]
{
new QuickDivideInfo(3, 2863311531, 33),
new QuickDivideInfo(7, 2454267027, 34),
new QuickDivideInfo(11, 780903145, 33),
new QuickDivideInfo(17, 2021161081, 35),
new QuickDivideInfo(23, 2987803337, 36),
new QuickDivideInfo(29, 2369637129, 36),
new QuickDivideInfo(37, 3714566311, 37),
new QuickDivideInfo(47, 2924233053, 37),
new QuickDivideInfo(59, 582368447, 35),
new QuickDivideInfo(71, 3871519817, 38),
new QuickDivideInfo(89, 3088515809, 38),
new QuickDivideInfo(107, 1284476201, 37),
new QuickDivideInfo(131, 1049152317, 37),
new QuickDivideInfo(163, 210795941, 35),
new QuickDivideInfo(197, 1395319325, 38),
new QuickDivideInfo(239, 2300233531, 39),
new QuickDivideInfo(293, 3752599413, 40),
new QuickDivideInfo(353, 3114763819, 40),
new QuickDivideInfo(431, 2551071063, 40),
new QuickDivideInfo(521, 1055193501, 39),
new QuickDivideInfo(631, 871245347, 39),
new QuickDivideInfo(761, 1444824741, 40),
new QuickDivideInfo(919, 2392843587, 41),
new QuickDivideInfo(1103, 498418689, 39),
new QuickDivideInfo(1327, 3314277703, 42),
new QuickDivideInfo(1597, 2753942713, 42),
new QuickDivideInfo(1931, 284700059, 39),
new QuickDivideInfo(2333, 1885146383, 42),
new QuickDivideInfo(2801, 785085061, 41),
new QuickDivideInfo(3371, 2609342339, 43),
new QuickDivideInfo(4049, 2172411219, 43),
new QuickDivideInfo(4861, 904761677, 42),
new QuickDivideInfo(5839, 188304783, 40),
new QuickDivideInfo(7013, 2508510773, 44),
new QuickDivideInfo(8419, 2089581429, 44),
new QuickDivideInfo(10103, 870641693, 43),
new QuickDivideInfo(12143, 1448751219, 44),
new QuickDivideInfo(14591, 602843741, 43),
new QuickDivideInfo(17519, 2008355049, 45),
new QuickDivideInfo(21023, 1673613285, 45),
new QuickDivideInfo(25229, 1394600345, 45),
new QuickDivideInfo(30293, 2322937451, 46),
new QuickDivideInfo(36353, 3871413319, 47),
new QuickDivideInfo(43627, 3225926339, 47),
new QuickDivideInfo(52361, 167989401, 43),
new QuickDivideInfo(62851, 1119612165, 46),
new QuickDivideInfo(75431, 932888921, 46),
new QuickDivideInfo(90523, 97169703, 43),
new QuickDivideInfo(108631, 2591110979, 48),
new QuickDivideInfo(130363, 2159163081, 48),
new QuickDivideInfo(156437, 1799286465, 48),
new QuickDivideInfo(187751, 2998385913, 49),
new QuickDivideInfo(225307, 1249295303, 48),
new QuickDivideInfo(270371, 2082138815, 49),
new QuickDivideInfo(324449, 1735095357, 49),
new QuickDivideInfo(389357, 722922605, 48),
new QuickDivideInfo(467237, 2409697663, 50),
new QuickDivideInfo(560689, 2008064911, 50),
new QuickDivideInfo(672827, 1673386929, 50),
new QuickDivideInfo(807403, 87154425, 46),
new QuickDivideInfo(968897, 2324085857, 51),
new QuickDivideInfo(1162687, 1936720557, 51),
new QuickDivideInfo(1395263, 403472287, 49),
new QuickDivideInfo(1674319, 336226223, 49),
new QuickDivideInfo(2009191, 1120749503, 51),
new QuickDivideInfo(2411033, 933956447, 51),
new QuickDivideInfo(2893249, 1556589021, 52),
new QuickDivideInfo(3471899, 1297157443, 52),
new QuickDivideInfo(4166287, 135120301, 49),
new QuickDivideInfo(4999559, 56299961, 48),
new QuickDivideInfo(5999471, 3002664487, 54),
new QuickDivideInfo(7199369, 2502219085, 54),
};
public static bool IsPrime(int candidate)
{
if ((candidate & 1) == 0)
{
return candidate == 2;
}
int max = (int) Math.Sqrt(candidate);
for (int i = 3; i <= max; i += 2)
{
if (candidate % i == 0)
{
return false;
}
}
return true;
}
public static int GetPrime(int min)
{
return GetPrimeCore(Primes, min);
}
public static int GetGoldenPrime(int min)
{
return GetPrimeCore(GoldenPrimes, min);
}
public static QuickDivideInfo GetPrimeInfo(int min)
{
return GetPrimeInfoCore(Primes, min);
}
public static QuickDivideInfo GetGoldenPrimeInfo(int min, bool accelerate = true)
{
if (accelerate)
{
foreach (var goldenPrimeAccelerator in GoldenPrimeAccelerators)
{
if (min > goldenPrimeAccelerator) continue;
min = goldenPrimeAccelerator;
break;
}
}
return GetPrimeInfoCore(GoldenPrimes, min);
}
static QuickDivideInfo GetPrimeInfoCore(QuickDivideInfo[] set, int min)
{
for (int i = 0; i < set.Length; ++i)
{
if (set[i].Divisor >= min)
{
return set[i];
}
}
throw new ArgumentOutOfRangeException("min",
"You really need a prime larger than 1,610,612,741?!");
}
static int GetPrimeCore(QuickDivideInfo[] set, int min)
{
for (int i = 0; i < set.Length; ++i)
{
int num = Primes[i].Divisor;
if (num >= min) return num;
}
for (int i = min | 1; i < 2147483647; i += 2)
{
if (IsPrime(i))
{
return i;
}
}
return min;
}
public static bool IsPowerOfTwo(int value)
{
return value > 0 && (value & (value - 1)) == 0;
}
public static bool IsPowerOfTwo(long value)
{
return value > 0 && (value & (value - 1)) == 0;
}
}
UniqueStringList
为了性能，我保持这个类精简高效。
- 不支持null值，但也不进行检查——这是调用者的责任。
- 一旦添加，就没有移除单个值的选项。但是，您可以使用
Clear()方法移除所有值。 - 我添加了一些额外的成员，如
Count、Contains()、IndexOf()和this[]，以表明它仍然是一个列表，但我认为Add()和Intern()方法将是主要使用的。 - 如果您知道所需的最大容量，可以在构造函数中提供它来预先确定内部数组的大小。注意：这将向上舍入以匹配使用的黄金素数和加载因子，但不会小于指定值。
public sealed class UniqueStringList
{
const float LoadFactor = .72f;
Slot[] slots;
int[] buckets;
int slotIndex;
QuickDivideInfo quickDivideInfo;
public UniqueStringList()
{
Expand(0);
}
public UniqueStringList(int capacity)
{
Expand(capacity);
}
public int Count
{
get { return slotIndex; }
}
public void Clear()
{
Array.Clear(slots, 0, slotIndex);
Array.Clear(buckets, 0, buckets.Length);
slotIndex = 0;
}
public string Intern(string item)
{
int index;
return slotIndex == (index = AddIfMissing(item)) ? item : slots[index].Value;
}
public void Intern(ref string item)
{
int index;
if (slotIndex != (index = AddIfMissing(item)))
{
item = slots[index].Value;
}
}
public void AddRange(IEnumerable<string> items)
{
foreach (var item in items)
{
if (item == null) continue;
AddIfMissing(item);
}
}
public bool Add(string item)
{
return slotIndex == AddIfMissing(item);
}
public bool Add(string item, out int index)
{
return slotIndex == (index = AddIfMissing(item));
}
public IEnumerable<string> GetItems()
{
var index = 0;
while(index < slotIndex)
{
yield return slots[index++].Value;
}
}
public string this[int index]
{
get { return slots[index].Value; }
}
public bool Contains(string item)
{
return IndexOf(item) != -1;
}
public int IndexOf(string item)
{
int hashCode = item.GetHashCode() & MathHelper.Lower31BitMask;
int bucketIndex = quickDivideInfo.ModuloPositive(hashCode);
for (int i = buckets[bucketIndex] - 1; i >= 0; i = slots[i].Next)
{
if (slots[i].HashCode == hashCode && string.Equals(slots[i].Value, item))
{
return i;
}
}
return -1;
}
int AddIfMissing(string item)
{
var hashCode = item.GetHashCode() & MathHelper.Lower31BitMask;
var bucketIndex = quickDivideInfo.ModuloPositive(hashCode);
for (int i = buckets[bucketIndex] - 1; i >= 0; i = slots[i].Next)
{
if (slots[i].HashCode == hashCode && string.Equals(slots[i].Value, item))
{
return i;
}
}
if (slotIndex == slots.Length)
{
Expand(slots.Length + 1);
bucketIndex = quickDivideInfo.ModuloPositive(hashCode);
}
slots[slotIndex].HashCode = hashCode;
slots[slotIndex].Value = item;
slots[slotIndex].Next = buckets[bucketIndex] - 1;
buckets[bucketIndex] = ++slotIndex;
return slotIndex - 1;
}
void Expand(int capacity)
{
quickDivideInfo = MathHelper.GetGoldenPrimeInfo(Math.Max(quickDivideInfo.Divisor + 1,
(int) (capacity / LoadFactor)));
capacity = Math.Max(capacity, (int) (quickDivideInfo.Divisor * LoadFactor));
buckets = new int[quickDivideInfo.Divisor];
Array.Resize(ref slots, capacity);
for (int i = 0; i < slotIndex; ++i)
{
int bucketIndex = quickDivideInfo.ModuloPositive(slots[i].HashCode);
slots[i].Next = buckets[bucketIndex] - 1;
buckets[bucketIndex] = i + 1;
}
}
struct Slot
{
public int HashCode;
public string Value;
public int Next;
}
}
使用代码
对于简单的驻留使用，有两个Intern()重载：
- 第一个将返回传入的字符串或一个已见过的等效字符串。
var myString = myUniqueStringList.Intern(myString);
ref传入的字符串。myUniqueStringList.Intern(ref myPOCOClass.AStringField);
还有两个Add()重载：
- 如果字符串是新的，两者都返回
true，否则返回false。
var justAdded = myUniqueStringList.Add("XXX");
int index;
if (myUniqueStringList.Add("XXX", ref index)
{
...
}
AddRange()方法允许一次添加多个字符串（这里会检查null值并忽略）。
GetItems()方法返回一个枚举器，以添加的顺序提取唯一的字符串。此输出可以填充string[]或List<string>或其他任何内容。
工作原理
概述
过程的最高层概述是：给定一个输入字符串，我们在列表中查找一个与之相等的字符串，并返回它在该列表中的索引。如果找不到该字符串，则将其添加到列表末尾并返回该索引。
主要问题是搜索字符串列表的速度。我们可以从头开始，然后依次检查每个字符串，直到找到一个相等的。但是，想象一下要搜索一百万个字符串——平均需要50万次相等性检查才能找到一个现有的字符串（如果找不到，则需要100万次！）。这当然太慢了。
另一种方法是在添加字符串时对其进行排序。然后，使用二分查找可以非常快速地定位字符串，但在首次构建列表时会非常缓慢，因为字符串必须不断地进行改动以保持排序。此外，需求定义了非改变的索引，所以这 anyway行不通。
我们需要保留能够简单地将新字符串附加到列表的想法，但在搜索列表时，将比较次数减少到最少。哈希是解决方案；它能够快速识别一小部分可能与输入字符串匹配的字符串（或者，如果您愿意，可以排除所有不可能相等的字符串）。然后，我们只需要检查这些字符串，看看是否有匹配的。
哈希使用一个“哈希桶”数组，并计算一个项应该放入或关联到哪个“桶”。对于给定的项，计算总是会选择同一个桶，因此可以忽略所有其他桶的内容，因为它们不包含所寻找的项。这就是哈希搜索速度快的原因。
哈希是通过为项生成一个哈希码来实现的——一个简单的int值，通常通过其GetHashCode()方法获得，尽管任何方法都可以使用。对我们来说，它实际上是一个介于int.MinValue和int.MaxValue之间的“随机”数，保证具有相同内容的字符串会得到相同的哈希码。但它不是唯一的——完全不同的字符串可能产生相同的哈希码，但一个好的哈希算法会在整个int范围内均匀分布数字，以尽量减少这种情况。例如，使用我测试字典中的单词：
"wren".GetHashCode() -> 1400949012
"inwood".GetHashCode() -> 1400949012
这会产生“冲突”，这是任何哈希系统中都预期并处理的情况。
但这并不是冲突的唯一来源：
"bougainvillia".GetHashCode() -> 1516975564
"aniseroot".GetHashCode() -> -630508084
因为我们需要在数组中选择一个桶，所以我们需要一个正数，因此我们必须使哈希码变为正数。最快的方法是简单地屏蔽掉最高位——负数标志——所以我们的后一种情况得到与前一种情况相同的正数1516975564——这是另一个冲突的来源。
此外，由于桶是数组的形式，我们需要计算一个介于0和buckets.Length - 1之间的索引，这可以通过模运算来完成，这将导致更多的冲突。如果我们有更多的桶，通过这个最后的步骤创建的冲突就会更少。这减少了相等性检查的次数，但需要更多的内存。如果我们有更少的桶，我们节省了一些内存，但需要进行更多的相等性检查——这是速度与内存之间的老式权衡。因此，在哈希中，经常使用加载因子（Load Factor）来定义一个合理的折衷。当达到这个加载因子时（例如，我们使用72%），我们会增加桶的数量，并重新计算现有项的桶，以将它们分散开。
冲突是通过查看与该桶关联的每个项并执行相等性检查来处理的，以找到精确匹配——在我们的例子中，是字符串相等性检查。我们需要进行的检查次数将远远少于列表中字符串的总数。我们的系统将使用一个Slot的链表，其头部由该桶指向。尽管这种冲突解决听起来很麻烦而且可能很慢，但实际上数字很出色。在我的测试中，在我添加了213,557个唯一字符串之后，最长的链是7，平均链长是1.2717——这比如果我们尝试顺序搜索的106,778的平均值要好得多！
所以我们将使用两个数组。第一个数组将存储Slot结构（包含字符串本身、正哈希码以在扩展时节省重新计算，以及指向链表中下一个Slot的索引）。第二个数组是哈希桶——一个简单的int[]，它保存一个指向Slot数组中头部项的索引。
我们精炼后的大致思路变为：给定输入字符串，获取它的哈希码。从哈希码，我们得到一个桶索引。从桶索引，我们得到一个Slot索引。如果我们运气好，Slot将包含我们正在寻找的字符串；如果没有，Slot.Next属性将引导我们尝试另一个Slot——数组中的一个链表。如果我们到达链表末尾仍然没有找到我们的字符串，那么它一定是新的，我们将它添加到系统中。
详细信息
大部分工作是在AddIfMissing()方法中完成的。
第一步是获取项的哈希码，并通过与01111111111111111111111111111111进行按位与（AND）操作将其变为正数，以屏蔽负数标志。然后，我们使用我们增强的模运算（即除以桶数量后的余数）从正哈希码计算出桶索引。
桶的内容是一个int，它是“指向”slots数组的一个“指针”，但请注意，在for/next循环中，我们首先减去1以获得实际要使用的索引。原因是当一个数组被创建时，它最初包含所有零（所有内存分配都以这种方式工作）。我们可以将桶数组中的所有值设置为-1来表示一个空桶，但这比简单地假设数组的内容都是基于1的并且总是减去1以获得基于0的头部Slot索引要慢。一个空桶将保持其原始的0，但for循环将从i == -1开始，并由于条件表达式而立即退出。如果进入了for/next循环，则表示一个有效的Slot，但不一定包含我们的搜索字符串。我们首先比较哈希码（我们存储的正哈希码），只有当它们相同时，我们才需要实际比较字符串。如果找到匹配项，我们退出循环，搜索完成，找到索引；否则，循环表达式将使用Slot的Next成员将i设置为要尝试的下一个Slot。（Next为-1将表示链表结束，项未找到，并跳出循环。）
如果执行结束在for/next循环之后，则表示搜索字符串未找到，需要将其添加到列表中。此时，我们检查slots数组当前是否已满，如果已满，则调用Expand方法增加它（以及按比例增加buckets数组），同时不要忘记重新计算桶索引。最后一个未使用的Slot然后会被填充我们拥有的信息，并将其索引返回给调用者。这样，任何字符串总是能被找到。请注意，Next成员是如何设置为buckets[bucketIndex] - 1的，它曾经是链表的头部。现在这个Slot将成为链表中的第二个，而我们新填充的Slot将成为头部。我们首先增加slotIndex，然后将其存储在buckets数组中（因为buckets是基于1的，所以先增加），使其正式成为该哈希码的头部Slot。
Expand()方法更简单。首先是计算新的桶数量，始终确保我们使用一个黄金素数，并且该素数比之前使用的素数大。我们存储这个QuickDivideInfo结构，并将容量变量调整为与我们的LoadFactor匹配。
桶容量的增加使现有桶失效，因此它们被简单地丢弃并重新创建为一个新数组。slots数组仍然（主要）包含有效信息，因此使用Array.Resize来增加容量但保留现有的Slots。最后一步是从保留的Slots重新创建哈希桶。循环遍历所有现有的Slots，并使用我们保留的正哈希码来计算新的桶索引，而无需再次调用GetHashCode()——这是对原始代码的又一次改进，特别是对于长字符串。Slot上的Next成员设置为当前桶指向的内容，然后更新桶以指向当前Slot（在这两种情况下都调整为1基索引）。因此，链表会自动重建。
其他代码都很直接，但可能值得指出的是，Add()和Intern()方法中的代码都依赖于C#的从左到右表达式求值来检测字符串何时刚刚添加到列表中。*当前*的slotIndex被求值*首先*，然后调用AddIfMissing()，后者*可能*会增加slotIndex。如果数字相同，则表示字符串刚刚被添加。请注意，如果先调用AddIfMissing()，则此方法将不起作用，并且始终返回false。
性能测试
有人询问了用于测试性能的代码，所以我现在添加了一个包含整个解决方案（.NET 4.0/VS2010）的下载，包括上面的源代码和性能测试代码（基于NUnit 2.5.2）。
在我整理代码以便发布时，我将速度测试代码重构为适合重用的抽象类。您只需要继承您的测试类，就可以访问相同的性能测试代码。
例如，一个[Test]方法看起来像：
[Test]
public void UniqueStringList_AddCopies()
{
TimeProcess(() =>
{
var l = new UniqueStringList();
for (var i = 0; i < words.Length; i++)
{
l.Add(words[i]);
l.Add(copiedWords[i]);
}
Assert.AreEqual(words.Length, l.Count);
});
}
并向控制台（或单元测试输出窗口）返回此输出：
Timing per Process; 10 sets; 20 repeats per set; GC Mode=PerRepeat:
1: Total set time=639 ms. Average process time=31.950000 ms. GC(62/62/61). Memory used=6,236,952 bytes.
2: Total set time=640 ms. Average process time=32.000000 ms. GC(61/61/61). Memory used=6,236,952 bytes.
3: Total set time=639 ms. Average process time=31.950000 ms. GC(61/61/61). Memory used=6,236,952 bytes.
4: Total set time=626 ms. Average process time=31.300000 ms. GC(2077/2077/61). Memory used=6,236,952 bytes.
5: Total set time=627 ms. Average process time=31.350000 ms. GC(1088/1088/61). Memory used=6,236,952 bytes.
6: Total set time=628 ms. Average process time=31.400000 ms. GC(61/61/61). Memory used=6,236,952 bytes.
7: Total set time=625 ms. Average process time=31.250000 ms. GC(1248/1248/61). Memory used=6,236,952 bytes.
8: Total set time=626 ms. Average process time=31.300000 ms. GC(596/596/61). Memory used=11,196,296 bytes.
9: Total set time=627 ms. Average process time=31.350000 ms. GC(912/912/61). Memory used=6,236,952 bytes.
10: Total set time=629 ms. Average process time=31.450000 ms. GC(61/61/61). Memory used=6,236,952 bytes.
All:
Fastest: 625 ms, Slowest: 640 ms, Average: 630.60 ms (31.530000 ms), StdDevP: 5.82 ms (0.92%)
Best 9: (excludes 2).
Fastest: 625 ms, Slowest: 639 ms, Average: 629.56 ms (31.477778 ms), StdDevP: 5.17 ms (0.82%)
Best 8: (excludes 1-2).
Fastest: 625 ms, Slowest: 639 ms, Average: 628.38 ms (31.418750 ms), StdDevP: 4.18 ms (0.67%)
Best 7: (excludes 1-3).
Fastest: 625 ms, Slowest: 629 ms, Average: 626.86 ms (31.342857 ms), StdDevP: 1.25 ms (0.20%)
正如您所见，输出相当全面。除了每次运行/每个进程的计时之外，它还显示了内存使用情况以及每次收集的垃圾回收代数计数。
底部的附加摘要显示了在排除较慢的运行集后的数据，这在您进行性能测试时，其他计算机进程碰巧干扰并减慢您的速度时非常有用。
可以使用Resharper的单元测试运行程序（或等效工具）来执行测试，以获得最大的便利性，或者单独作为控制台应用程序执行，以获得稍准确和更快的数字。无论哪种方式，请始终记住确保Release Mode处于开启状态！
TimingTestFixture有许多属性，如TimingCount（默认为10）、RepeatCount（默认为20）等。
您可以通过在[TestFixture]类中添加一个构造函数来调用TimingTestFixture上的这个构造函数来更改任何/所有数字：
protected TimingTestFixture(int defaultTimingCount = 10,
int defaultRepeatCount = 20,
GarbageCollectMode defaultGarbageCollectMode =
GarbageCollectMode.PerRepeat,
TimingMode defaultTimingMode = TimingMode.AutoByRepeatCount,
bool defaultPerformJITPass = true,
bool defaultUseHighPriorityThread = true)
然后，您类中的所有测试都将使用您的默认设置。
此外，您可以在[Test]方法开头设置任何属性，以仅覆盖该方法的默认设置——TimingTestFixture/Nunit将在运行其他[Test]方法之前重置回默认值。
作为比较，UniqueStringListOriginal返回了这些数字：
Timing per Process; 10 sets; 20 repeats per set; GC Mode=PerRepeat:
1: Total set time=1,286 ms. Average process time=64.300000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
2: Total set time=1,285 ms. Average process time=64.250000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
3: Total set time=1,285 ms. Average process time=64.250000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
4: Total set time=1,285 ms. Average process time=64.250000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
5: Total set time=1,289 ms. Average process time=64.450000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
6: Total set time=1,287 ms. Average process time=64.350000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
7: Total set time=1,291 ms. Average process time=64.550000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
8: Total set time=1,289 ms. Average process time=64.450000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
9: Total set time=1,293 ms. Average process time=64.650000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
10: Total set time=1,287 ms. Average process time=64.350000 ms. GC(61/61/61). Memory used=4,824,344 bytes.
All:
Fastest: 1,285 ms, Slowest: 1,293 ms, Average: 1,287.70 ms (64.385000 ms), StdDevP: 2.61 ms (0.20%)
Best 9: (excludes 9).
Fastest: 1,285 ms, Slowest: 1,291 ms, Average: 1,287.11 ms (64.355556 ms), StdDevP: 2.02 ms (0.16%)
Best 8: (excludes 7, 9).
Fastest: 1,285 ms, Slowest: 1,289 ms, Average: 1,286.63 ms (64.331250 ms), StdDevP: 1.58 ms (0.12%)
Best 7: (excludes 5, 7, 9).
Fastest: 1,285 ms, Slowest: 1,289 ms, Average: 1,286.29 ms (64.314286 ms), StdDevP: 1.39 ms (0.11%)
由于新代码显示约31.5毫秒，而旧代码约63.3毫秒，我可以自信地声称它现在快了一倍！
关注点
在编写此代码时，我特别关注确保对QuickDivideInfo上的方法调用的内联以获得速度。我不知道有简单的方法可以检查JIT输出，所以我依赖于测试用例的计时。我为每个方法编写了三个测试：一个用于计时正常操作（除法或模运算），一个用于实际内联乘法和移位，一个用于调用QuickDivideInfo方法。如果后两者产生大致相等的时间，则假定该方法已被内联。两者都应该产生大约是使用普通运算符的方法速度的三分之一的时间。
令我惊讶的是，其中一组产生了奇怪的结果。起初我以为我的方法没有被内联，但后来我注意到，实际内联优化的测试也没有显示出预期的速度提升！
这段代码
var check = 0;
for (var numerator = 0; numerator <= maxNumerator; numerator++)
{
check += numerator >= 0
? numerator - (int) ((numerator * qdi.Multiplier) >> qdi.Shift) * qdi.Divisor
: numerator - (int) -((-numerator * qdi.Multiplier) >> qdi.Shift) * qdi.Divisor;
}
return check;
比这段代码快了3倍。
var check = 0;
for (var numerator = 0; numerator <= maxNumerator; numerator++)
{
check += numerator >= 0
? (int) ((numerator * qdi.Multiplier) >> qdi.Shift)
: (int) -((-numerator * qdi.Multiplier) >> qdi.Shift);
}
return check;
然而它有更多的操作要完成！
我最终发现，通过反转条件为“<0”或者更改为if/else结构（无论哪种条件），我可以获得预期的速度提升。
所以，在写这四种表达式的写法中，三种产生了快速的JITed代码，但另一种，也就是我碰巧选择的那种，产生了慢的JITed代码。
所以我的结论是，JIT编译器本身没有bug，因为结果是正确的，但肯定有可以改进的地方。这让我对在性能关键代码中使用?:感到有些不安。
历史
- v1 - 初始发布。
- v2 - 添加了“它是如何工作的”部分。
- v2.1 - 添加了包含代码、测试、测试框架的解决方案下载；将“性能测试”部分添加到文章中。