当前位置：网站首页>C＃基础之字典——Dictionary（二）

C＃基础之字典——Dictionary（二）

2022-08-11 05:31:00 【canon_卡农】

接上回: C# 基础之字典——Dictionary（一）
上次我们知道字典是通过一个数组来存储Entry，那么当我们往字典添加数据的时候，如果数组的容量不够了怎么办呢？
下面我们带着这个疑问来看看底层是怎么实现数组扩容的。

字典是如何扩容的

先看Insert接口内的一段代码：

int index;
if (freeCount > 0) {
    
    index = freeList;
    freeList = entries[index].next;
    freeCount--;
}
else {
    
    if (count == entries.Length)
    {
    
        Resize();
        targetBucket = hashCode % buckets.Length;
    }
    index = count;
    count++;
}

entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;

可以看到当插入位置count等于容量数组的长度时，则通过Resize()进行扩容，重新定位targetBucket。
Resize()内部则调用 HashHelpers.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);
        }

最终通过调用 GetPrime 来得到真正的新数组的大小，返回一个约为oldSize两倍大小的素数。源码中定义了一个素数数组：

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};

在源码中可以看到，如果没有指定字典的初始容量，那么会调用Initialize(0)，内部将容量初始化为primes数组中最小素数 3.

if (buckets == null) Initialize(0);

这样看来，容量数组大小总为素数，这是为什么呢？

为什么字典的桶buckets 长度为素数？

容量不为素数会出现什么情况

我们假设有这样的一系列keys,他们的分布范围是K={ 0, 1,…, 100 },又假设某一个buckets的长度m=12,因为3是12的一个因子,当key是3的倍数时,那么targetBucket = key%m 也将会是3的倍数.例如：
Keys {0,12,24,36,…} TargetBucket将会是0.
Keys {3,15,27,39,…} TargetBucket将会是3.
Keys {6,18,30,42,…} TargetBucket将会是6.
Keys {9,21,33,45,…} TargetBucket将会是9.
如果Key的值是均匀分布的(每一个Key出现的可能性相同),那么Buckets的Length就没有那么重要了,但是如果Key不是均匀分布呢?

想象一下,如果Key在3的倍数时出现的可能性特别大,其他的基本不出现,TargetBucket那些不是3的倍数的索引就基本不会存储什么数据了,这样就可能有2/3的Bucket空着,数据大量第聚集在0,3,6,9中.

为了减少哈希冲突

这种情况其实是很常见的。
例如，有一种场景，您根据对象存储在内存中的位置来跟踪对象,如果你的计算机的字节大小是4，而且你的Buckets的长度也为4。
那么所有的内存地址都会是4的倍数,也就是说key都是4的倍数,它的HashCode也将会是4的倍数。
导致所有的数据都会存储在TargetBucket=0(Key%4=0)的bucket中,而剩下的3/4的Buckets都是空的. 这样数据分布就非常不均匀了。

每一个key如果与Buckets的长度m有公因子,那么该数据就会存储在这个公因子的倍数为索引的bucket中。
为了让数据尽可能地均匀地分布在Buckets中,我们要尽量减少m和key有公因子出现的可能性。那么,把Bucket的长度设为质数就是最佳选择了,因为质数的因子是最少的。
这就是为什么每次利用Resize给字典扩容时会取大于当前size的最小质数的原因。

避免频繁扩容

在源码中可以看到，每次扩容都会新建数组：

// Resize()
int[] newBuckets = new int[newSize];
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];