C#中的常见集合

注意，箭头线不代表继承关系，只代表功能上的加强，如有错误，欢迎指出。

泛型集合时间复杂度

线程安全集合时间复杂度

不可变集合时间复杂度

以下是 C# 中 ImmutableList<T>、ImmutableSortedDictionary<TKey, TValue>、ImmutableDictionary<TKey, TValue>、ImmutableHashSet<T>、ImmutableStack<T> 和 ImmutableQueue<T> 这些不可变集合常见操作的时间复杂度表格：

只读集合时间复杂度

List

当你创建一个新的 List 对象时，若没有指定初始容量，默认为 0，不过当第一个元素被添加进去时，它会自动将容量初始化为 4.并在下次扩容时，以双倍的容量进行扩容。

List.Insert(0, item) 的坑

List 基于数组实现，数组在内存中是连续存储的。当使用 Insert(0, item) 在列表开头插入元素时，列表中现有的所有元素都需要向后移动一个位置，以便为新元素腾出空间。这意味着插入操作的时间复杂度为 O(n) ，其中 n 是列表中现有元素的数量。元素数量越多，移动元素所花费的时间就越长，性能也就越低。

        public void Insert(int index, T item)        {            // Note that insertions at the end are legal.            if ((uint)index > (uint)_size)            {                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);            }            if (_size == _items.Length) Grow(_size + 1);            if (index < _size)            {				//如果index很靠前，且数组size很大的话。这将是一场灾难。                Array.Copy(_items, index, _items, index + 1, _size - index);            }            _items[index] = item;            _size++;            _version++;        }

HashSet/Dictionary

Dictionary<TKey, TValue> 的底层结构主要由以下几个部分组成：

1. 桶（Bucket）数组：这是一个一维数组，数组的每个元素称为一个桶。桶数组的大小是 Dictionary 的容量，初始容量通常是一个较小的质数，后续会根据元素数量的增加而动态调整。

2. 条目（Entry）数组：每个桶对应一个或多个条目，条目是一个结构体，包含三个重要的字段：

3. *. int hashCode：键的哈希码，用于确定键在桶数组中的位置。

4. *. int next：指向下一个条目的索引，用于处理哈希冲突。如果该值为 -1，表示这是该桶中的最后一个条目。

5. *. TKey key：存储的键。

6. *. TValue value：存储的值。

Add 的坑

private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior){	//计算出key的hash	uint hashCode = (uint)((typeof(TKey).IsValueType && comparer == null) ? key.GetHashCode() : comparer!.GetHashCode(key));	//将哈希码与桶数组的长度进行取模运算（hashCode % bucket.Length），得到该键值对应在桶数组中的索引位置。	ref int bucket = ref GetBucket(hashCode);	int i = bucket - 1; // Value in _buckets is 1-based		uint collisionCount = 0;		while (true)	{		// Should be a while loop https://github.com/dotnet/runtime/issues/9422		// Test uint in if rather than loop condition to drop range check for following array access		if ((uint)i >= (uint)entries.Length)		{			break;		}		//		if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))		{			return false;		}		//如果该桶已经有其他条目（即发生了哈希冲突），则通过 next 字段将新条目链接到该桶的链表中。		i = entries[i].next;						collisionCount++;		//如果循环次数>Entry的长度，说明有死循环，抛出异常。		if (collisionCount > (uint)entries.Length)		{			// 在Framework时代，并发情况下会导致entries[i].next被错误定位。			// 从而形成一个‌‌‌死链表，导致Contains查询时，陷入死循环，CPU异常高。			// 在.NET Core中,通过collisionCount来计数，从而规避死循环。			ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();		}	}}

ConcurrentDictionary

ConcurrentDictionary<TKey, TValue> 的底层核心是由多个分段（Segment）组成，每个分段本质上是一个小型的哈希表，并且每个分段都有自己独立的锁。这种设计将整个字典划分为多个部分，不同线程可以同时访问不同的分段，从而减少锁的竞争，提高并发性能。

简单来说就是多个 Dictionary 组合

VolatileNode[]

内部的 Node 类和 Dictionary 的 Entry 一致

Locks[]

将一个大锁拆成多个小锁，提高锁的颗粒度，尽可能小的避免锁竞争。

keys/values 的坑

不要高频次调用属性，因为它们会返回一个全新的 List

ValueFactory 的坑

在使用 ConcurrentDictionary 的过程中，大家会理所当然认为所有操作是线程安全的。但面对 GetOrAdd/GetOrUpdate 中的 ValueFactory 方法时，却是线程不安全的。

原因也很简单，ValueFactory 会被先执行，再执行从 TryUpdateInternal。因此，你有几个线程就会重复执行几次。

举个例子，偷懒用其它大佬的例子。https://www.cnblogs.com/CreateMyself/p/6086752.html如果要确保线程安全，需要搭配 Lazy<>.

ConcurrentQueue

ConcurrentQueue 底层主要基于链表（Linked List）数据结构实现，链表是一种动态的数据结构，由一系列节点（ConcurrentQueueSegment）组成，每个节点包含一个数据元素和一个指向下一个节点的引用。为了保证线程安全，ConcurrentQueue 在链表的基础上使用了无锁（Lock - Free）算法，主要借助原子操作（如 Interlocked 类提供的方法）来避免传统锁带来的性能开销和潜在的死锁问题

头指针（head）

头指针指向队列的第一个节点，用于出队操作

尾指针（tail）

尾指针指向队列的最后一个节点，用于入队操作

Count 的坑

不要高频次调用 Count 属性，因为内部调用逻辑非常复杂，需要遍历每一个 Segment 的 head,tail 之间的差值，动态计算出最终的大小，且还有加锁操作，消耗也不低。

文章转载自：叫我安不理

原文链接：https://www.cnblogs.com/lmy5215006/p/18712729

体验地址：http://www.jnpfsoft.com/?from=001YH