常用集合类¶

private struct Entry {
   public int hashCode; // Lower 31 bits of hash code, -1 if unused
   public int next;     // Index of next entry, -1 if last
   public TKey key;     // Key of entry
   public TValue value; // Value of entry
}

private int[] buckets;
private Entry[] entries;

private void Insert(TKey key, TValue value, bool add) {

    if( key == null ) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    // 初始化数组buckets和entries 会取素数作为size 这里最小为3
    if (buckets == null) Initialize(0);

    // 取Hash值 符号位 置0
    int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;

    // 取余数得到桶位置
    int targetBucket = hashCode % buckets.Length;

#if FEATURE_RANDOMIZED_STRING_HASHING
    // 记录碰撞次数
    int collisionCount = 0;
#endif

    // 检查是否已经存在键值对，有的话直接写入
    for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
        if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
            if (add) { 
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
            }
            entries[i].value = value;
            version++;
            return;
        }

#if FEATURE_RANDOMIZED_STRING_HASHING
        // 发生碰撞
        collisionCount++;
#endif
    }
    int index;

    // 是否存在空闲位置（执行删除操作后的空闲位置）
    if (freeCount > 0) {
        // 取空闲位置index
        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;
    version++;

    // 碰撞次数过多会触发扩容 HashHelpers.HashCollisionThreshold = 100
#if FEATURE_RANDOMIZED_STRING_HASHING

#if FEATURE_CORECLR
    // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
    // in this case will be EqualityComparer<string>.Default.
    // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will 
    // be using randomized string hashing

    if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) 
    {
        comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
        Resize(entries.Length, true);
    }
#else
    if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
    {
        comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
        Resize(entries.Length, true);
    }
#endif // FEATURE_CORECLR

#endif

}