private void Initialize(int capacity) {
//取大于capacity的最小质数(素数)
int size = HashHelpers.GetPrime(capacity);
buckets = new int[size];
for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
entries = new Entry[size];
freeList = -1;
}
****************************************************
internal static class HashHelpers
{
......
public const int HashCollisionThreshold = 100; //碰撞阈值
......
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}; //质数(素数)组
......
public static int GetPrime(int min)
{
if (min < 0)
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
Contract.EndContractBlock();
//查找primes是否有满足的质数(素数)
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.
//primes没有查找到满足的质数(素数),自行计算
for (int i = (min | 1); i < Int32.MaxValue;i+=2)
{
if (IsPrime(i) && ((i - 1) % Hashtable.HashPrime != 0))
return i;
}
return min;
}
}
hashCode = 1; targetBucket = hasCode % buckets.Length; //targetBucket = 1
next = buckets[targetBucket]; //next = -1
buckets[targetBucket] = index; //buckets[1] = 0
hashCode = 2; targetBucket = hasCode % buckets.Length; //targetBucket = 2
next = buckets[targetBucket]; //next = -1
buckets[targetBucket] = index; //buckets[2] = 1
hashCode = 4; targetBucket = hasCode % buckets.Length; //targetBucket = 1
next = buckets[targetBucket]; //next = 0
buckets[targetBucket] = index; //buckets[1] = 2
2.5 在继续添加键值之前,需要扩容操作,因为entries数组长度为3且都已有元素。扩容后需要对buckets和entries每个元素的Next需要重新赋值;
private void Resize() {
//扩容的大小:取大于(当前容量*2)的最小素数
//例:
Resize(HashHelpers.ExpandPrime(count), false);
}
private void Resize(int newSize, bool forceNewHashCodes) {
Contract.Assert(newSize >= entries.Length);
//实例化buckets,并将每个元素置为-1
int[] newBuckets = new int[newSize];
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];
Array.Copy(entries, 0, newEntries, 0, count);
//如果是Hash碰撞扩容,使用新HashCode函数重新计算Hash值
if(forceNewHashCodes) {
for (int i = 0; i < count; i++) {
if(newEntries[i].hashCode != -1) {
newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
}
}
}
//重建单链表
for (int i = 0; i < count; i++) {
if (newE