Dictionary的扩容(重点)
那么什么情况下Dictionary会发生扩容呢?一般有两种情况
-1 存放数据的Entry的数组entries存满了,此时就会发生扩容
-2 邪门情况,如果大量数据发生冲突,全部变成链表串在一个桶下,此时查找的效率就会变低,因为要链表的长度越长,那么遍历的Entry也就越长。所以为了避免这种情况,设置了一个最大的碰撞次数,当超过这个次数的时候就会扩容(扩容之后所有的HashCode到桶的映射值会发生改变)。目前.Net Framwork 4.7中设置的碰撞次数阈值为100。
public const int HashCollisionThreshold = 100;
那么扩容的容量变化是怎样的呢?
private void Resize()
{
Resize(HashHelpers.ExpandPrime(count), false);
}
private void Resize(int newSize, bool forceNewHashCodes)
{
Contract.Assert(newSize >= entries.Length);
int[] newBuckets = new int[newSize];
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];
-------
此处省略,详细代码见https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,1dca11c8648f5d65
-------
}
我们主要关注其中的newSize这个变量,就是这个变量决定了扩容之后两个关键数组的大小。我们发现是先将当前的容量大小传入ExpandPrime这个函数。
public static int ExpandPrime(int oldSize)
{
int newSize = 2 * oldSize;
// Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
{
Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
return MaxPrimeArrayLength;
}
return GetPrime(newSize);
}
}
而这个函数显示将老的容量翻倍赋给新的容量,那么Dictionary的扩容是不是就在原先的基础上翻倍的呢,其实不然,我们继续看可以发现返回值是GetPrime(newSize),继续进这个函数去看。
public static int GetPrime(int min)
{
if (min < 0)
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
Contract.EndContractBlock();
for (int i = 0; i < primes.Length; i++)
{
int prime = primes[i];
if (prime >= min) return prime;
}
//outside of our predefined table.
//compute the hard way.
for (int i = (min | 1); i < Int32.MaxValue;i+=2)
{
if (IsPrime(i) && ((i - 1) % Hashtable.HashPrime != 0))
return i;
}
return min;
}
我们发现这是一个取素数的函数,首先会从给定的Primes这个数组中取离原先容量翻倍后数值最接近的素数,如果超过了Primes数组给定的最大值,那么就会直接去寻找离翻倍数值最近的素数,并且改素数减一不是HashPrime(101)的倍数。
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};