非泛型集合（System.Collections）

特点：可存储任意类型（object），但存在装箱拆箱性能损耗，类型不安全。

ArrayList

动态数组，支持自动扩容。

默认容量上限是4，初始容量是0。当容量不够时会判断触发双倍增容。

1
2
3

ArrayList list = new ArrayList();
list.Add("Hello"); // 任意类型
list.Add(123);

注意由于 ArrayList 是非泛型集合所以很多操作都会触发拆装箱。不过如果插入一个继承自 ICollection 的集合，其内部会批量化拆装箱。

Hashtable

键(Object)值(Object)对集合，基于哈希表实现。

1 2	Hashtable table = new Hashtable(); table["key1"] = "value1";

Queue

Stack

SortedList

BitArray

上面的集合都类似于 ArrayList 和 ArrayList<T> 的对比，所以剩下的内容直接写入泛型集合中。

泛型集合

List<T>

用途：动态数组，替代非泛型的 ArrayList。
特点：
- 类型安全，仅能存储 T 类型的元素。
- 值类型无需装箱（直接存储原始类型）。
- 支持索引访问、排序、查找等操作。

1
2
3

List<int> numbers = new List<int> { 1, 2, 3 };
numbers.Add(4);  // 直接存储 int，无装箱
int num = numbers[0]; // 直接取值，无拆箱

部分源代码结构

private const int _defaultCapacity = 4;
private T[] _items;
[ContractPublicPropertyName("Count")]
private int _size;
private int _version;
static readonly T[]  _emptyArray = new T[0];

这里可以看到列表的默认容量上限是4，初始容量为0。

Dictionary<TKey, TValue>

用途：键值对哈希表，替代非泛型的 Hashtable。
特点：
- 键和值的类型明确，无需强制转换。
- 键必须唯一，查找效率为 O(1)。

1
2
3

Dictionary<string, int> ages = new Dictionary<string, int>();
ages.Add("Alice", 30);
int aliceAge = ages["Alice"]; // 直接返回 int

源码

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 int count;
private int version;
private int freeList;
private int freeCount;
private IEqualityComparer<TKey> comparer;
private KeyCollection keys;
private ValueCollection values;
private Object _syncRoot;

// constants for serialization
private const String VersionName = "Version";
private const String HashSizeName = "HashSize";  // Must save buckets.Length
private const String KeyValuePairsName = "KeyValuePairs";
private const String ComparerName = "Comparer";

简单原理描述

简单原理描述是为了快速想起关于这个知识点的原理。
首先看 C# 中关于 Dictionary<Key,Value> 的开源代码。

可以看到有两个最重要的数组，buckets 和 entries，简单的来说每插入一个键制对都会先形成一个 Entry 数据结构，然后将根据 key 得到的哈希码存入 buckets 数组中。

但是哈希码有可能是重复的啊，所以重复的哈希码不会添加到 buckets 数组中，而是根据已有的哈希码得到对应的 Entry 数据结构，将当前 Entry 的 next 指向插入的 Entry，如果 next 已经有了就一直找到指向的最后一个，然后存入插入的 Entry。

所以这里面大部分的 int 值都是指针，指向 entries 中的索引，比如说用来重用的 freeList 就是已删除列表的头指针。

标准表述

标准描述是为了清晰记录内容，防止关键内容混淆。

内部数据结构
- Entry 数组：存储所有键值对的结构体（Entry），每个 Entry 包含：
  - Key：键对象。
  - Value：对应的值。
  - Next：指向下一个 Entry 的索引（用于处理冲突）。
- Bucket 数组（桶数组）：每个桶是一个整数，指向 Entry 数组中的位置，表示该哈希值对应的链表头。
- 自由列表（Free List）：用于重用被删除的 Entry 位置，避免内存浪费。
哈希函数与索引计算
- 计算哈希码：对键调用 GetHashCode() 方法获取哈希值。
- 处理哈希码：通过取模运算（或其他方式）将哈希码映射到桶数组的索引。
1
int bucketIndex = key.GetHashCode() % buckets.Length;
添加键值对（Add/Insert）
- 计算哈希索引：根据键的哈希值确定桶的位置。
- 处理冲突：
  - 若桶为空（buckets[bucketIndex] == -1），直接在 Entry 数组中分配新位置。
  - 若桶非空（哈希冲突），遍历链表检查键是否已存在：
    - 存在 → 抛出 ArgumentException（键重复）。
    - 不存在 → 将新 Entry 插入链表头部。
- 更新数据结构：
  - 新 Entry 的 Next 指向原链表头。
  - 桶数组更新为新 Entry 的位置。
查找键值对（Get）
- 计算哈希索引：通过键的哈希值定位桶。
- 遍历链表：从桶指向的 Entry 开始，逐项检查键的相等性（使用 Equals 方法）。
- 找到匹配项：返回对应的值；否则返回默认值或抛出异常。
删除键值对（Remove）
- 定位键的位置：类似查找过程，找到目标 Entry。
- 调整链表：
  - 若目标 Entry 是链表头，直接更新桶的指向。
  - 否则，调整前驱节点的 Next 指针，跳过目标 Entry。
- 标记空闲位置：将被删除的 Entry 加入自由列表，供后续插入重用。
扩容机制（Rehash）
- 触发条件：当元素数量超过阈值（count > buckets.Length * loadFactor，默认负载因子为 0.72）。
- 创建新数组：桶数组和 Entry 数组扩容至原大小的两倍（或其他策略）。
- 重新映射：遍历所有 Entry，重新计算哈希索引并插入新桶数组。
- 更新状态：释放旧数组，使用新数组。
性能分析
- 时间复杂度：
  - 插入、删除、查找：平均 O(1)（理想情况下）。
  - 最坏情况（大量冲突）：退化为 O(n)。
- 优化策略：
  - 选择良好的哈希函数（键的 GetHashCode 实现）。
  - 设置合理的初始容量，避免频繁扩容。
总结
- Dictionary<Key, Value> 通过哈希表实现高效操作，其核心在于：
- 哈希函数快速定位桶。
- 链地址法解决冲突。
- 动态扩容保持低冲突率。
- 泛型设计确保类型安全和性能优化。

Queue<T>

用途：先进先出（FIFO）队列，替代非泛型 Queue。
方法：
- Enqueue(T item)：入队。
- Dequeue()：出队并返回 T 类型。

1
2
3

Queue<string> messages = new Queue<string>();
messages.Enqueue("Hello");
string msg = messages.Dequeue(); // 类型安全

Stack<T>

用途：后进先出（LIFO）栈，替代非泛型 Stack。
方法：
- Push(T item)：压栈。
- Pop()：弹栈并返回 T 类型。

1
2
3

Stack<double> values = new Stack<double>();
values.Push(3.14);
double pi = values.Pop(); // 直接返回 double

SortedList<TKey, TValue> 和 SortedDictionary<TKey,TValue>

核心区别概览

特性	SortedList<TKey, TValue>	SortedDictionary<TKey, TValue>
内部数据结构	动态数组（两个并行数组：keys[] 和 values[]）	红黑树（平衡二叉搜索树）
插入/删除时间复杂度 O(n)	（需移动元素保持有序性）	O(log n)（树结构调整）
查找时间复杂度	O(log n)（二分查找）	O(log n)（树遍历）
内存占用	更低（连续内存存储	更高（树节点分散存储，每个节点含父子指针）
索引访问	支持（通过索引访问键或值	不支持
适用场景	小数据量、频繁按索引访问、低频插入/删除	大数据量、频繁插入/删除、无需索引访问

内部实现与性能

SortedList<TKey, TValue>：
- 使用两个动态数组分别存储键和值，插入时通过二分查找定位位置，并移动后续元素以维持有序性。
- 插入/删除性能：
  - 平均 O(n)（需要移动数组元素）。
  - 示例：插入一个元素到已排序数组中间时，需将后半部分元素整体后移。
- 适用场景：
  - 数据量小（例如 < 1000 元素）。
  - 需要按索引快速访问元素（如 Keys[3] 或 Values[5]）。
SortedDictionary<TKey, TValue>：
- 基于红黑树（一种自平衡二叉搜索树），插入/删除时通过旋转和变色保持树平衡。
- 插入/删除性能：
  - 平均 O(log n)（树高度为 log n）。
  - 示例：插入元素时只需调整局部树结构，无需整体移动数据。
- 适用场景：
  - 数据量大（例如 > 1000 元素）。
  - 频繁插入/删除操作。

功能特性

索引访问：
- SortedList 支持通过索引直接访问键或值（如 mySortedList.Keys[2]）。
- SortedDictionary 无索引访问功能，只能通过迭代器遍历。
内存占用：
- SortedList 内存更紧凑（数组存储），适合内存敏感场景。
- SortedDictionary 每个树节点需存储父/子节点指针，内存开销较大。
遍历顺序：
- 两者均按键的升序遍历（默认基于 IComparable 或自定义 IComparer）。

代码对比

// 使用 SortedList（适合小数据量）
SortedList<int, string> sortedList = new SortedList<int, string>();
sortedList.Add(3, "Charlie");
sortedList.Add(1, "Alice");
sortedList.Add(2, "Bob");

// 通过索引访问
Console.WriteLine(sortedList.Keys[0]);    // 输出 1
Console.WriteLine(sortedList.Values[1]); // 输出 "Bob"

// 使用 SortedDictionary（适合频繁插入）
SortedDictionary<int, string> sortedDict = new SortedDictionary<int, string>();
sortedDict.Add(3, "Charlie");
sortedDict.Add(1, "Alice");
sortedDict.Add(2, "Bob");

// 无法通过索引访问，只能遍历
foreach (var kvp in sortedDict) {
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}
// 输出：
// 1: Alice
// 2: Bob
// 3: Charlie

性能测试对比

操作	SortedList (1,000 元素)	SortedDictionary (1,000 元素)
插入 1,000 个元素	~10 ms（需频繁移动数组）	~2 ms（红黑树调整）
删除中间元素	~5 ms	~0.1 ms
按键查找	~0.01 ms（二分查找）	~0.01 ms（树遍历）

总结

SortedList<TKey, TValue>：
- 优势：内存紧凑、支持索引访问。
- 劣势：插入/删除性能差，适合静态或低频更新的有序数据集。
SortedDictionary<TKey, TValue>：
- 优势：插入/删除高效，适合动态数据集。
- 劣势：内存占用高，不支持索引访问。
根据具体需求选择：
- 若需要索引访问或内存敏感 → SortedList。
- 若需要高频插入/删除 → SortedDictionary。

HashSet、 HashSet 和 SortedSet

部分源码

HashSet<T>

private int[] m_buckets;
private Slot[] m_slots;
private int m_count;
private int m_lastIndex;
private int m_freeList;
private IEqualityComparer<T> m_comparer;
private int m_version;

internal struct Slot 
{
    internal int hashCode;      // Lower 31 bits of hash code, -1 if unused
    internal int next;          // Index of next entry, -1 if last
    internal T value;
}

SortedHashSet<T>

Node root;
IComparer<T> comparer;
int count;
int version;
private Object _syncRoot;

internal class Node 
{
    public bool IsRed;
    public T Item;
    public Node Left;
    public Node Right;

    public Node(T item) {
        // The default color will be red, we never need to create a black node directly.                
        this.Item = item;
        IsRed = true;
    }

    public Node(T item, bool isRed) {
        // The default color will be red, we never need to create a black node directly.                
        this.Item = item;
        this.IsRed = isRed;
    }
}

HashSet<T> 的核心特性

内部实现：基于哈希表，类似 Dictionary<TKey, TValue>，但仅存储键（无值）。
核心功能：
- 唯一性：自动去重，插入重复元素会被忽略。
- 无序性：元素存储顺序与插入顺序无关。
- 高效操作：插入、删除、查找的平均时间复杂度为 O(1)（理想哈希函数下）。
适用场景：
- 快速去重（如过滤重复数据）。
- 高频集合运算（交集、并集、差集）。
- 检查元素是否存在（替代 List 的 Contains 方法）。

1
2
3

HashSet<int> numbers = new HashSet<int> { 1, 2, 3 };
numbers.Add(2);      // 忽略重复元素
Console.WriteLine(numbers.Contains(3)); // 输出 True

SortedSet<T> 的核心特性

内部实现：基于红黑树（平衡二叉搜索树），维护元素有序性。
核心功能：
- 唯一性：同 HashSet。
- 有序性：元素按升序排列（默认基于 IComparable 或自定义 IComparer）。
- 操作复杂度：插入、删除、查找的时间复杂度为 O(log n)。
适用场景：
- 需要有序遍历元素的唯一集合。
- 范围查询（如获取某个区间的元素）。

SortedSet<int> sortedNumbers = new SortedSet<int> { 3, 1, 2 };
foreach (int num in sortedNumbers) {
    Console.Write(num + " "); // 输出 "1 2 3"
}

核心功能对比

特性	HashSet<T>	SortedSet<T>
内部结构	哈希表	红黑树
元素顺序	无序	升序排列
插入/删除时间复杂度	平均 O(1)，最坏 O(n)	O(log n)
查找时间复杂度	平均 O(1)，最坏 O(n)	O(log n)
内存占用	较低（哈希表连续存储）	较高（树节点分散）
适用场景	高频去重、无需有序遍历	需要有序性、范围查询

非泛型 HashSet 的局限性

类型不安全：存储 object 类型元素，需强制类型转换。
性能损耗：值类型元素需装箱/拆箱。
已过时：在 .NET 2.0+ 中，优先使用泛型 HashSet。

HashSet legacySet = new HashSet();
legacySet.Add("abc");      // 存储为 object
legacySet.Add(123);        // 装箱 int → object
string s = (string)legacySet.ToArray()[0]; // 拆箱

总结

HashSet<T>：
- 适合高频去重、无需顺序的场景。
- 性能优于 List 的 Contains 操作。
SortedSet<T>：
- 适合需要有序遍历或范围查询的场景。
- 插入/删除性能低于 HashSet，但保证顺序。
非泛型 HashSet：
- 遗留代码中使用，新项目应优先选择泛型版本。

LinkedList

部分源码

public class LinkedList<T>: ICollection<T>, System.Collections.ICollection, IReadOnlyCollection<T>
           ,ISerializable, IDeserializationCallback 
{
    ...

    internal LinkedListNode<T> head;
    internal int count;
    internal int version;
    private Object _syncRoot;

    ...
}


public sealed class LinkedListNode<T> 
{
    internal LinkedList<T> list;
    internal LinkedListNode<T> next;
    internal LinkedListNode<T> prev;
    internal T item;
}

核心结构与特性

双向链表：每个节点（LinkedListNode）包含：

Value：存储的数据（类型为 T）。

Previous：指向前驱节点的引用。

Next：指向后继节点的引用。

链表的头尾：

First：链表的第一个节点。

Last：链表的最后一个节点。

动态大小：无需预分配内存，按需动态增减节点。