c# HashSet的扩容机制需要注意的

一：背景

1. 讲故事

自从这个纯内存项目进了大客户之后，搞得我现在对内存和CPU特别敏感，跑一点数据内存几个G的上下，特别没有安全感，总想用windbg抓几个dump看看到底是哪一块导致的，是我的代码还是同事的代码？ 很多看过我博客的老朋友总是留言让我出一套windbg的系列或者视频，我也不会呀，没办法，人在江湖飘，迟早得挨上几刀，逼着也得会几个花架子😄😄😄，废话不多说，这一篇就来看看 HashSet 是如何扩容的。

二：HashSet的扩容机制

1. 如何查看

了解如何扩容，最好的办法就是翻看HashSet底层源码，最粗暴的入口点就是 HashSet.Add 方法。

从图中可以看到最后的初始化是用 Initialize 的，而且里面有这么一句神奇的代码: int prime = HashHelpers.GetPrime(capacity);，从字面意思看是获取一个质数，哈哈，有点意思，什么叫质数？ 简单说就是只能被 1 和 自身 整除的数就叫做质数，那好奇心就来了，一起看看质数是怎么算的吧！ 再次截图。

从图中看，HashSet底层为了加速默认定义好了 72 个质数，最大的一个质

本文来源gao!daima.com搞$代!码网

数是 719w，换句话就是说当元素个数大于 719w 的时候，就只能使用 IsPrime 方法动态计算质数，如下代码：

public static bool IsPrime(int candidate)
{
	if ((candidate & 1) != 0)
	{
		int num = (int)Math.Sqrt(candidate);
		for (int i = 3; i <= num; i += 2)
		{
			if (candidate % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	return candidate == 2;
}

看完了整个流程，我想你应该明白了，当你第一次Add的时候，默认的空间占用是 72 个预定义中最小的一个质数 3，看过我之前文章的朋友知道List的默认大小是4，后面就是简单粗暴的 * 2 处理，如下代码。

private void EnsureCapacity(int min)
{
	if (_items.Length < min)
	{
		int num = (_items.Length == 0) ? 4 : (_items.Length * 2);
	}
}

2. HashSet 二次扩容探究

当HashSet的个数达到3之后，很显然要进行二次扩容，这一点不像List用一个 EnsureCapacity 方法搞定就可以了，然后细看一下怎么扩容。

public static int ExpandPrime(int oldSize)
{
	int num = 2 * oldSize;
	if ((uint)num > 2146435069u && 2146435069 > oldSize)
	{
		return 2146435069;
	}
	return GetPrime(num);
}

从图中可以看到，最后的扩容是在 ExpandPrime 方法中完成的，流程就是先 * 2， 再取最接近上限的一个质数，也就是 7 ，然后将 7 作为 HashSet 新的Size，如果你非要看演示，我就写一小段代码证明一下吧，如下图：

2. 您嗅出风险了吗？

<1> 时间上的风险

为了方便演示，我把 72 个预定义的最后几个质数显示出来。

public static readonly int[] primes = new int[72]
{
	2009191,
	2411033,
	2893249,
	3471899,
	4166287,
	4999559,
	5999471,
	7199369
};

喜欢 (0)赏

[搞代码]

分享 (0)