集合与泛型

`List<T>` 和数组有什么区别？

list-vs-array

数组 T[] 是固定长度的连续存储；List<T> 是封装了数组的动态集合，可以自动扩容。

int[] arr = new int[3];

List<int> list = new List<int>();
list.Add(1);
list.Add(2);

核心区别

对比点	数组 `T[]`	`List<T>`
长度	创建后固定	可动态增长
访问	`arr[i]`	`list[i]`
数量属性	`Length`	`Count`
容量概念	长度就是容量	有 `Count` 和 `Capacity`
添加删除	不方便，需要自己搬数据	`Add`、`Remove` 更方便
性能	更轻量，少一层封装	更灵活，但扩容/移动有成本
适合	数量固定、性能敏感	数量变化、业务集合

List<T> 内部本质上也是数组：

List<int> list = new List<int>();

list.Add(1);
list.Add(2);
list.Add(3);

当内部数组满了，List<T> 会创建一个更大的数组，把旧元素复制过去。所以 Add 通常很快，但偶尔扩容时会有复制成本。

面试加分点：

数组和 List<T> 的按索引访问都是 O(1)。但中间插入、删除通常是 O(n)，因为后面的元素要移动。数量固定或追求极致性能时用数组；数量会变化、需要方便增删时用 List<T>。

`List<T>` 扩容机制大概是什么？

list-expansion-mechanism

List<T> 底层是数组。当 Count == Capacity 时再 Add，它会创建一个更大的新数组，把旧元素复制过去，然后再放入新元素。

var list = new List<int>();

list.Add(1);
list.Add(2);
list.Add(3);

可以把它理解成：

Count    = 当前实际元素个数
Capacity = 底层数组容量

当容量不够时，大致流程是：

申请一个更大的数组，通常按约 2 倍扩容。
把旧数组里的元素复制到新数组。
让 List<T> 内部引用指向新数组。
把新元素追加进去。

例如：

扩容前：
Count = 4
Capacity = 4

再 Add 一个元素：

扩容后：
Count = 5
Capacity = 8

所以 list.Add(x) 大多数时候很快，是 O(1)；但遇到扩容那一次，需要复制旧元素，是 O(n)。从连续多次添加来看，均摊复杂度通常还是 O(1)。

面试加分点：

如果提前知道大概数量，可以初始化容量，减少扩容次数。

var list = new List<int>(1000);

或者：

list.EnsureCapacity(1000);

收尾可以这样说：

List<T> 是动态数组，不是链表。它靠 Capacity 预留空间，容量不够时扩容并复制，因此尾部添加很高效，中间插入删除仍然可能需要移动元素。

`Dictionary<TKey, TValue>` 底层是什么？

dictionary-underlying-structure

Dictionary<TKey, TValue> 底层是哈希表：通过 key 的哈希值快速定位桶，再在冲突链中比较 key，找到对应 value。

现代 .NET 源码里核心结构大致是：

int[] buckets;
Entry[] entries;

struct Entry
{
    int hashCode;
    int next;
    TKey key;
    TValue value;
}

查找流程：

key.GetHashCode()
        ↓
定位 bucket
        ↓
找到 entries 中的链头
        ↓
沿 next 处理哈希冲突
        ↓
用 Equals 比较 key
        ↓
返回 value

例如：

var dict = new Dictionary<string, int>();

dict["age"] = 18;

Console.WriteLine(dict["age"]);

大致发生的是：

对 "age" 算哈希值。
根据哈希值找到桶位置。
桶里记录某个 entry 的索引。
去 entries 数组里找真正的 key/value。
如果哈希冲突，就沿着 next 继续找。
找到 key 相等的 entry 后返回 value。

复杂度

平均情况下：

查找：O(1)
插入：O(1)
删除：O(1)

但如果哈希冲突很多，最坏情况会退化。实际性能很依赖 GetHashCode() 和 Equals() 的质量。

面试加分点

Dictionary 判断 key 是否相同，不是只看哈希值，还要看相等比较：

GetHashCode()
Equals()

也可以传入自定义比较器：

var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

另外，作为 key 的对象不要在放入字典后修改参与哈希计算的字段，否则可能导致“明明 key 在里面，却找不到”。

收尾可以这样说：

Dictionary<TKey,TValue> 本质是哈希表，内部维护 bucket 数组和 entry 数组。bucket 用来快速定位，entry 保存 hashCode、next、key、value。冲突时通过 next 链接起来，所以平均 O(1)，但依赖好的哈希函数和稳定的 key。

参考：Microsoft Learn 的 Dictionary<TKey,TValue> 文档说明它表示键值集合，并暴露 Capacity、Comparer、Count 等属性；.NET 源码中能看到 _buckets、_entries、Entry 链和 IEqualityComparer 相关实现。 Microsoft Learn · .NET Dictionary.cs 源码

`HashSet<T>` 和 `Dictionary<T, bool>` 有什么关系？

hashset-vs-dictionary-bool

HashSet<T> 可以概念上理解成“只有 key、没有 value 的 Dictionary<T, bool>”，但它不是简单用 Dictionary<T, bool> 包了一层。

var set = new HashSet<string>();
set.Add("A");

var dict = new Dictionary<string, bool>();
dict["A"] = true;

它们的共同点：

都是哈希表思路
都通过 GetHashCode() 定位桶
都通过 Equals() 判断元素/key 是否相等
查找、添加、删除平均都是 O(1)
都要求 key/元素的哈希相关状态保持稳定

区别是：

对比点	`HashSet<T>`	`Dictionary<T, bool>`
语义	集合：元素是否存在	映射：key 对应 bool
数据	只保存元素	保存 key 和 value
API	`Add`、`Contains`、`UnionWith`、`IntersectWith`	`Add`、索引器、`TryGetValue`
重复处理	重复 `Add` 返回 `false`	重复 `Add` 抛异常，索引器会覆盖
内存	不需要额外 bool value	每个 key 还带一个 bool 值
适用	去重、存在性判断、集合运算	需要 key 映射到某个值

面试可以这样答：

HashSet<T> 和 Dictionary<TKey,TValue> 底层都基于哈希表。HashSet<T> 只关心元素是否存在，可以看成没有 value 的字典；Dictionary<T,bool> 可以模拟集合，但语义不如 HashSet<T> 清楚，也多存了一个没太大意义的 bool。

.NET 官方文档也说，HashSet<T> 可被简单看作没有值的 Dictionary<TKey,TValue>；源码里 HashSet<T> 使用类似 Dictionary 的数组式实现，核心也有 _buckets 和 _entries。参考：Microsoft Learn HashSet · .NET HashSet.cs 源码

`Queue<T>` 和 `Stack<T>` 适合什么场景？

queue-vs-stack-scenarios

Queue<T> 是先进先出，适合排队；Stack<T> 是后进先出，适合回退。

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
Console.WriteLine(queue.Dequeue()); // 1

var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
Console.WriteLine(stack.Pop()); // 2

Queue<T> 适合

Queue<T> 是 FIFO：First In, First Out。

适合“先来的先处理”：

任务排队
消息缓冲
打印队列
广度优先搜索 BFS
生产者消费者模型
请求排队处理

常用方法：

queue.Enqueue(item); // 入队
queue.Dequeue();     // 出队
queue.Peek();        // 看队头，不移除

Stack<T> 适合

Stack<T> 是 LIFO：Last In, First Out。

适合“最近的先处理”：

撤销 Undo
浏览器后退
深度优先搜索 DFS
括号匹配
表达式解析
回溯算法
模拟递归调用栈

常用方法：

stack.Push(item); // 入栈
stack.Pop();      // 出栈
stack.Peek();     // 看栈顶，不移除

面试加分点：

Queue<T> 和 Stack<T> 都不是线程安全集合。多线程生产消费场景应优先考虑 ConcurrentQueue<T>，需要并发栈时用 ConcurrentStack<T>。空集合上直接 Dequeue / Pop 会抛异常，可以用 TryDequeue / TryPop 更安全。

`IEnumerable` 和 `IEnumerator` 区别是什么？

ienumerable-vs-ienumerator

IEnumerable 表示“这个对象可以被遍历”；IEnumerator 表示“真正执行遍历的游标”。

IEnumerable<int> nums = new List<int> { 1, 2, 3 };

IEnumerator<int> enumerator = nums.GetEnumerator();

while (enumerator.MoveNext())
{
    Console.WriteLine(enumerator.Current);
}

IEnumerable<T> 的核心是：

IEnumerator<T> GetEnumerator();

它本身不负责“走到第几个元素”，只负责返回一个枚举器。

IEnumerator<T> 的核心是：

bool MoveNext();
T Current { get; }

它保存当前遍历状态，每次 MoveNext() 往前走一步，Current 拿当前元素。

foreach 背后大概就是：

var enumerator = nums.GetEnumerator();

while (enumerator.MoveNext())
{
    var item = enumerator.Current;
}

面试收尾：

IEnumerable 是可枚举的数据源，负责创建 IEnumerator；IEnumerator 是一次遍历过程中的游标，负责移动和取当前值。一个 IEnumerable 可以被多次遍历，每次通常会创建新的 IEnumerator。

`IList`、`ICollection`、`IEnumerable` 区别是什么？

ilist-icollection-ienumerable

IEnumerable<T> 只表示“能遍历”；ICollection<T> 表示“是个集合，有数量和增删能力”；IList<T> 表示“是个有顺序、能按下标访问的列表”。

继承关系大致是：

IList<T> : ICollection<T> : IEnumerable<T>

IEnumerable<T>

只负责遍历：

IEnumerable<int> nums;

核心能力：

GetEnumerator()

能做：

foreach (var item in nums)
{
}

但它不保证有 Count，也不保证能 Add，更不保证能按下标访问。

ICollection<T>

在可遍历基础上，表示一个“集合”。

常见能力：

Count
Add()
Remove()
Clear()
Contains()
CopyTo()

适合你需要知道数量，或者需要增删元素的场景。

IList<T>

在集合基础上，增加“顺序 + 下标访问”。

常见能力：

list[0]
IndexOf()
Insert()
RemoveAt()

适合你明确需要按索引读取、插入、删除的场景。

面试收尾：

选择接口时要用最小够用原则。只需要遍历就用 IEnumerable<T>；需要数量或增删就用 ICollection<T>；需要按下标访问或插入删除指定位置，才用 IList<T>。这样代码耦合更低，也更灵活。

泛型有什么好处？

generic-benefits

泛型就是把“类型”当参数，让一份代码适配多种类型，同时保持强类型检查。

List<int> numbers = new List<int>();
numbers.Add(1);

int x = numbers[0]; // 不需要强转

主要好处

类型安全

不用泛型时常用 object，取出来要强转，错误可能运行时才暴露：

ArrayList list = new ArrayList();
list.Add(123);

int x = (int)list[0];

泛型能在编译期检查类型：

List<int> list = new List<int>();
list.Add(123);
// list.Add("abc"); // 编译错误

代码复用

不用为 int、string、User 分别写一套容器或方法：

class Repository<T>
{
    public void Save(T entity)
    {
    }
}

性能更好

值类型放进 object 可能发生装箱，取出时拆箱。泛型集合比如 List<int> 可以避免很多不必要的装箱拆箱。

表达更清晰

Dictionary<string, User>

一看就知道：key 是 string，value 是 User。比 Dictionary<object, object> 清楚很多。

面试收尾：

泛型的核心价值是类型安全、代码复用和性能优化。它让我们不用退回到 object，减少强制类型转换和装箱拆箱，同时 API 的类型含义也更明确。

泛型约束 `where T : class`、`new()` 是什么？

generic-constraints-class-new

泛型约束就是限制 T 必须满足某些条件。where T : class 表示 T 必须是引用类型；where T : new() 表示 T 必须有 public 无参构造函数。

class Repository<T>
    where T : class, new()
{
    public T Create()
    {
        return new T();
    }
}

where T : class：

class Service<T> where T : class
{
}

表示 T 只能是引用类型，比如：

Service<string>
Service<User>
Service<object>

不能是：

Service<int>
Service<DateTime>

where T : new()：

class Factory<T> where T : new()
{
    public T Create()
    {
        return new T();
    }
}

如果没有 new() 约束，泛型代码里不能直接写：

new T()

因为编译器不知道 T 有没有无参构造函数。

注意点：

where T : class, new()

多个约束一起写时，new() 必须放最后。

面试收尾：

class 约束解决“这个 T 是不是引用类型”的问题；new() 约束解决“能不能在泛型内部 new T()”的问题。泛型约束的作用是让编译器知道 T 具备哪些能力，从而允许更安全的调用。

为什么遍历中修改集合会报错？

collection-modified-during-enumeration

因为 foreach 背后的枚举器会记录集合的版本号。遍历期间如果集合结构被修改，版本号变化，枚举器检测到不一致，就会抛异常。

典型错误：

var list = new List<int> { 1, 2, 3, 4 };

foreach (var item in list)
{
    if (item == 2)
    {
        list.Remove(item); // 报错
    }
}

常见异常：

InvalidOperationException:
Collection was modified; enumeration operation may not execute.

背后大概是这样：

foreach 开始
  ↓
创建 Enumerator，记录 version = 7
  ↓
MoveNext() 正常
  ↓
list.Remove(...) 让集合 version = 8
  ↓
下一次 MoveNext() 发现 version 不一致
  ↓
抛异常

这样设计是为了避免遍历结果变得不确定。比如你正在遍历第 2 个元素，突然删除了第 1 个元素，后面的索引、顺序、桶结构都可能变，继续遍历就容易漏元素、重复元素或读到错误状态。

正确做法 1：遍历副本

foreach (var item in list.ToList())
{
    if (item == 2)
    {
        list.Remove(item);
    }
}

正确做法 2：倒序 for 删除

for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] == 2)
    {
        list.RemoveAt(i);
    }
}

正确做法 3：先收集，再统一删除

var toRemove = list.Where(x => x % 2 == 0).ToList();

foreach (var item in toRemove)
{
    list.Remove(item);
}

面试收尾：

遍历中修改集合会破坏枚举器的一致性，所以 .NET 用版本号做 fail-fast 检测。结构性修改比如 Add、Remove、Clear 通常会让枚举器失效；如果只是修改集合里某个引用对象的属性，不改变集合结构，一般不会触发这个异常。

进阶追问

题海扩展:C#高频细节

底层机制

深挖性能优化

C++进阶追问

集合与泛型

`List<T>` 和数组有什么区别？

`List<T>` 扩容机制大概是什么？

`Dictionary<TKey, TValue>` 底层是什么？

`HashSet<T>` 和 `Dictionary<T, bool>` 有什么关系？

`Queue<T>` 和 `Stack<T>` 适合什么场景？

`IEnumerable` 和 `IEnumerator` 区别是什么？

`IList`、`ICollection`、`IEnumerable` 区别是什么？

泛型有什么好处？

泛型约束 `where T : class`、`new()` 是什么？

为什么遍历中修改集合会报错？

读完这篇，留下你的看法

集合与泛型 ​

List<T> 和数组有什么区别？ ​

List<T> 扩容机制大概是什么？ ​

Dictionary<TKey, TValue> 底层是什么？ ​

HashSet<T> 和 Dictionary<T, bool> 有什么关系？ ​

Queue<T> 和 Stack<T> 适合什么场景？ ​

IEnumerable 和 IEnumerator 区别是什么？ ​

IList、ICollection、IEnumerable 区别是什么？ ​

泛型有什么好处？ ​

泛型约束 where T : class、new() 是什么？ ​

为什么遍历中修改集合会报错？ ​

读完这篇，留下你的看法

集合与泛型

`List<T>` 和数组有什么区别？

`List<T>` 扩容机制大概是什么？

`Dictionary<TKey, TValue>` 底层是什么？

`HashSet<T>` 和 `Dictionary<T, bool>` 有什么关系？

`Queue<T>` 和 `Stack<T>` 适合什么场景？

`IEnumerable` 和 `IEnumerator` 区别是什么？

`IList`、`ICollection`、`IEnumerable` 区别是什么？

泛型有什么好处？

泛型约束 `where T : class`、`new()` 是什么？

为什么遍历中修改集合会报错？