1. 常用数据结构

.NET 中的数据结构主要分布在 System.Collections 和 System.Collections.Generic 命名空间中，后者是我们现代开发中更常用的泛型集合。

核心思想：数据结构是什么？
你可以把数据结构想象成 “存放和组织数据的容器”。不同的容器有不同的形状和特性，有的擅长快速查找，有的擅长有序排列，有的擅长高效增删。选择正确的数据结构是写出高性能、可维护代码的关键。

---

1.1 线性结构 (Linear Structures)

这类结构中的数据元素像一条线一样串在一起。

1.1.1 数组 (T[ ]) / List< T >

• 本质：连续的内存块。这是所有数据结构中最高效、最基础的一种。

• 原理：

  • 在内存中申请一整块连续的空间。

  • 每个元素紧密相邻地存放，通过索引（下标）可以直接计算出任何元素的内存地址：地址 = 首地址 + 索引 * 元素大小。这是一个 O(1) 操作，极快。

  • List<T> 的本质是一个动态数组。它内部封装了一个 T[]。当容量不足时，它会自动申请一块更大的新数组（通常是原来的 2 倍），并将旧数据拷贝过去。这就是为什么在 List<T> 中间 Insert 或删除效率低，因为需要移动后续所有元素。

• 特点：

  • 优点：随机访问极快（按索引读/写）。

  • 缺点：插入/删除（尤其是在中间）效率低（需要移动元素）；容量固定（数组）或动态扩容有成本（List）。

• 比喻：一排连续编号的储物柜。你知道是 3 号柜子，直接走过去开就行，很快。但你想在两个柜子中间加一个，就得把后面的柜子全都往后挪，很麻烦。

1.1.2 LinkedList< T > (双向链表)

• 本质：非连续的内存块，通过指针连接每个元素。

• 原理：

  • 每个元素（节点）包含三部分：1) 实际数据 (Data) 2) 指向前一个节点的指针 (Previous) 3) 指向后一个节点的指针 (Next)。

  • 元素在内存中是分散存储的，靠这些指针“手拉手”连成一条链。

  • 添加/删除元素时，只需要修改相邻节点的指针指向即可，不需要移动任何数据，效率是 O(1)。

• 特点：

  • 优点：在已知节点的情况下，插入/删除极快。

  • 缺点：随机访问极慢（只能从头部或尾部开始一个一个遍历查找，O(n) 操作）；每个元素占用更多内存（因为要存储指针）。

• 比喻：寻宝游戏。每个线索告诉你下一个线索在哪。你想在中间加一个线索，只需要修改前后线索的指向。但你想直接找到第 5 个线索，必须从第一个开始一个一个找下去。

1.1.3 Stack< T > (栈)

• 本质：后进先出 (LIFO - Last In, First Out) 的线性表。

• 原理：

  • 只允许在一端（称为栈顶）进行插入（Push）和删除（Pop）操作。

  • .NET 中 Stack< T > 的内部是用数组实现的。

• 操作：

  • Push(T)：压栈，将元素放入栈顶。

  • Pop()：出栈，移除并返回栈顶元素。

  • Peek()：窥视，返回栈顶元素但不移除。

• 比喻：一摞盘子。你总是取最上面的那个盘子（最后放上去的），也只能把新盘子放在最上面。

1.1.4 Queue< T > (队列)

• **本质：先进先出 (FIFO - First In, First Out) **的线性表。

• 原理：

  • 允许在一端（称为队尾）插入（Enqueue），在另一端（称为队首）删除（Dequeue）。

  • .NET 中 Queue< T > 的内部使用环形数组（Circular Buffer） 实现，以便高效利用内存。

• 操作：

  • Enqueue(T)：入队，将元素加入队尾。

  • Dequeue()：出队，移除并返回队首元素。

• 比喻：单条队伍的排队。先来的人先接受服务（先离开队伍），新来的人只能排在队伍末尾。

---

1.2 集合结构 (Collection Structures)

这类结构更关注元素的唯一性和查找速度。

1.2.1 HashSet< T > (哈希集)

• 本质：一个基于哈希表实现的、不含重复元素的集合。

• 原理：

  1. 哈希函数：当你添加一个元素时，它会调用元素的 GetHashCode() 方法，计算出一个唯一的（理想情况下）数字（哈希码）。

  2. 哈希桶：内部维护一个数组（桶数组）。根据计算出的哈希码，通过某种映射（如 桶索引 = hashcode % 数组长度）决定这个元素应该放在哪个“桶”里。

  3. 解决冲突：不同的元素可能计算出相同的桶索引（哈希冲突）。.NET 使用一种叫 “链地址法” 的方法，让同一个桶里的元素形成一个链表。

  4. 查找：查找时，先计算哈希码找到对应的桶，然后在桶内的链表中进行（少量）比较（使用 Equals 方法）即可找到元素。这使得平均情况下的查找、插入、删除接近 O(1)。

• 特点：

  • 优点：查找、插入、删除速度极快（平均 O(1)）；自动去重。

  • 缺点：元素无序；性能依赖于哈希函数的质量。

• 比喻：一个有很多抽屉的柜子（哈希桶）。你要存一个“苹果”，根据“苹果”的拼音算出它应该放在第 3 个抽屉。你再存“香蕉”，算出放第 5 个抽屉。查找时也是同样的过程，直接去对应的抽屉找，非常快。如果两个东西算出来都在第 3 个抽屉（冲突），那就把这个抽屉里的东西列个清单（链表），查找时再看看清单上是哪个。

1.2.2 Dictionary<TKey, TValue> (字典)

• 本质：基于哈希表实现的键值对集合。你可以把它理解为 HashSet<KeyValuePair<TKey, TValue>>。

• 原理：与 HashSet< T > 完全一样，也是通过键（TKey）的哈希码来定位存储位置（桶）。每个桶里存储的是 KeyValuePair 结构。TValue 本身不参与哈希计算。

• 特点：

  • 优点：通过键来查找、插入、删除值的速度极快（平均 O(1)）；键必须是唯一的。

  • 缺点：元素无序（但遍历顺序是确定的）；性能依赖键的哈希函数。

• 比喻：一个字典/电话簿。你通过“名字”（Key）快速查找到对应的“电话号码”（Value）。

1.2.2 SortedSet< T > / SortedDictionary<TKey, TValue> (有序集合/有序字典)

• 本质：基于红黑树（Red-Black Tree） 这种自平衡二叉搜索树实现的有序集合。

• 原理：

  • 红黑树是一种复杂的数据结构，它始终保持树的大致平衡，从而保证了最坏情况下操作的时间复杂度也是 O(log n)。

  • 元素在树中是按顺序存储的（基于 IComparer< T >）。

• 特点：

  • 优点：元素始终是排序的；查找、插入、删除的时间复杂度稳定为 O(log n)。

  • 缺点：操作速度比基于哈希表的 HashSet/Dictionary 慢（O(log n) vs O(1)）；占用更多内存。

• 比喻：一棵始终保持平衡的二叉搜索树。每个节点左子节点的值比自己小，右子节点的值比自己大。查找时类似于“二分查找”，每次比较都能排除一半的节点。

---

1.3 其他实用结构

1. LinkedList< T > (上面已讲)
2. Span< T > / Memory< T >

• 本质：对连续内存区域的视图/引用，是 .NET Core 及以后版本中为了高性能而引入的。

• 原理：它们本身不分配内存，而是提供了一种安全且高效的方式来访问一段已有的内存（如数组、字符串、栈内存）。避免了不必要的内存拷贝。

• 比喻：一张“地图”。它本身不是土地（内存），但它精确地描述了如何访问和使用某一块已有的土地。

总结与如何选择

根据场景选择数据结构，可以参考下面的决策流程图：

记住这个核心口诀：

• 索引快，用 List/Array

• 查找快，用 HashSet/Dictionary

• 排序快，用 SortedSet/SortedDictionary

• 增删快，用 LinkedList

• 后进先出用 Stack

• 先进先出用 Queue

---

2. 常用设计模式

设计模式不是具体的代码，而是解决特定问题的经验总结和最佳实践模板。它就像建筑大师总结出的经典建筑蓝图，你知道在什么地形、有什么需求时，用哪种蓝图最合适。

设计模式的三大分类

分类	核心关注点	模式举例
创建型模式	对象的创建：如何用更灵活、更合适的方式来实例化对象，而不是直接 new。	工厂方法、抽象工厂、建造者、单例
结构型模式	类和对象的组合：如何将类或对象组合成更大、更复杂的结构，同时保持结构的灵活和高效。	适配器、装饰器、代理、组合
行为型模式	对象间的通信：对象之间如何交互、分配职责，以及算法的流动。	观察者、策略、命令、责任链

2.1 创建型模式 (Creational Patterns)

2.1.1 工厂方法模式 (Factory Method Pattern)

• 本质：定义一个创建对象的接口，但让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。

• 原理：将 new 操作封装起来，客户端不需要知道具体要创建哪个类的对象，只需要知道对应的工厂即可。这符合“依赖倒置原则”——依赖于抽象（接口），而不是具体实现。

• 比喻：招聘网站。你（客户端）只需要发布一个“招聘程序员”的请求（调用工厂接口）。网站（工厂）会根据你的需求，决定是给你推荐一个 CSharpProgrammer 还是一个 JavaProgrammer。你不需要关心他们具体是怎么被招来的。

• .NET 示例：System.Net.WebRequest.Create(url) 就是一个工厂方法。你传入一个 http:// 的 URL，它返回一个 HttpWebRequest 对象；传入 ftp://，它返回一个 FtpWebRequest 对象。

// 产品接口
public interface ILogger
{
    void Log(string message);
}

// 具体产品A
public class FileLogger : ILogger
{
    public void Log(string message) => File.WriteAllText("log.txt", message);
}

// 具体产品B
public class DatabaseLogger : ILogger
{
    public void Log(string message) => Console.WriteLine($"Write to DB: {message}");
}

// 工厂接口
public interface ILoggerFactory
{
    ILogger CreateLogger();
}

// 具体工厂A
public class FileLoggerFactory : ILoggerFactory
{
    public ILogger CreateLogger() => new FileLogger();
}

// 具体工厂B
public class DatabaseLoggerFactory : ILoggerFactory
{
    public ILogger CreateLogger() => new DatabaseLogger();
}

// 客户端代码
class Client
{
    private readonly ILoggerFactory _loggerFactory;
    
    public Client(ILoggerFactory loggerFactory) // 依赖注入工厂
    {
        _loggerFactory = loggerFactory;
    }
    
    public void DoWork()
    {
        // 使用工厂创建产品，客户端不知道具体是哪个Logger
        ILogger logger = _loggerFactory.CreateLogger();
        logger.Log("Working...");
    }
}

2.1.2 单例模式 (Singleton Pattern)

• 本质：保证一个类只有一个实例，并提供一个全局访问点。

• 原理：将构造函数设为私有，防止外部用 new 创建。在内部创建一个静态实例，并通过一个静态属性提供给外部访问。

• 比喻：公司的CEO。一个公司只能有一个CEO，所有人都通过同一个渠道访问他，而不是随便谁都能“new”一个CEO出来。

• 注意事项：多线程环境下需要双重锁检查等机制来保证线程安全。谨慎使用，因为它本质上是一个全局变量，可能导致代码耦合度高，难以测试。

public sealed class Singleton // sealed 防止通过继承破坏单例
{
    private static Singleton _instance;
    private static readonly object _lock = new object(); // 用于锁的对象
    
    // 私有构造函数，防止外部实例化
    private Singleton() { }
    
    // 全局访问点
    public static Singleton Instance
    {
        get
        {
            // 双重锁检查，确保线程安全且高效
            if (_instance == null)
            {
                lock (_lock)
                {
                    if (_instance == null)
                    {
                        _instance = new Singleton();
                    }
                }
            }
            return _instance;
        }
    }
    
    public void SomeMethod() { ... }
}

// 使用
Singleton.Instance.SomeMethod();

2.1.3 建造者模式 (Builder Pattern)

• 本质：将一个复杂对象的构建与其表示分离，使得同样的构建过程可以创建不同的表示。

• 原理：将创建复杂对象的步骤分解到不同的方法中，由一个“指导者”按特定顺序指挥“建造者”一步步构建。最终由建造者返回构建好的产品。

• 比喻：组装电脑。指导者（Director）是销售员，他按照订单流程（先装CPU，再装内存，最后装显卡）来指挥建造者（不同的装机师傅）。不同的建造者（高配师傅、低配师傅）使用不同的零件，但遵循相同的流程，最终组装出不同配置的电脑（产品）。

• 适用场景：创建需要多个步骤、配置复杂的对象，且对象的组成部分可能变化时。

// 要构建的复杂产品
public class Computer
{
    public string CPU { get; set; }
    public string RAM { get; set; }
    public string SSD { get; set; }
    // ... 其他组件
}

// 建造者抽象接口
public interface IComputerBuilder
{
    void BuildCPU();
    void BuildRAM();
    void BuildSSD();
    Computer GetComputer();
}

// 具体建造者
public class GamingComputerBuilder : IComputerBuilder
{
    private Computer _computer = new Computer();
    
    public void BuildCPU() => _computer.CPU = "Intel i9";
    public void BuildRAM() => _computer.RAM = "32GB DDR5";
    public void BuildSSD() => _computer.SSD = "2TB NVMe";
    public Computer GetComputer() => _computer;
}

// 指导者
public class ComputerDirector
{
    public void Construct(IComputerBuilder builder)
    {
        builder.BuildCPU();
        builder.BuildRAM();
        builder.BuildSSD();
    }
}

// 客户端使用
var director = new ComputerDirector();
var builder = new GamingComputerBuilder();

director.Construct(builder); // 指导者指挥建造过程
Computer myGamingPC = builder.GetComputer(); // 从建造者获取产品

---

2.2 结构型模式 (Structural Patterns)

2.2.1 适配器模式 (Adapter Pattern)

• 本质：将一个类的接口转换成客户期望的另一个接口。使原本接口不兼容的类可以一起工作。

• 原理：创建一个适配器类，它包装了被适配者，并实现了目标接口。在适配器的方法内部，调用被适配者的方法，并进行必要的转换。

• 比喻：电源转换插头。你的中国插头（客户端）需要插入欧洲的插座（目标接口）。转换插头（适配器）实现了欧洲插座的规格，但其内部包裹的是中国插头的电气结构（被适配者），从而完成了转换。

// 目标接口（欧洲插座）
public interface ITarget
{
    string GetRequest();
}

// 被适配者（中国插头）
public class Adaptee
{
    public string GetSpecificRequest() => "Specific request.";
}

// 适配器（转换插头）
public class Adapter : ITarget
{
    private readonly Adaptee _adaptee;

    public Adapter(Adaptee adaptee)
    {
        _adaptee = adaptee;
    }

    public string GetRequest()
    {
        // 转换过程：将 Adaptee 的接口转换为 ITarget 的接口
        return $"This is '{_adaptee.GetSpecificRequest()}'";
    }
}

// 客户端代码
Adaptee adaptee = new Adaptee();
ITarget target = new Adapter(adaptee); // 客户端通过目标接口与适配器交互

Console.WriteLine(target.GetRequest());
// 输出: This is 'Specific request.'

2.2.2 装饰器模式 (Decorator Pattern)

• 本质：动态地给一个对象添加一些额外的职责。就增加功能来说，装饰器模式相比生成子类更为灵活。

• 原理：装饰器和被装饰对象实现相同的接口。装饰器内部持有被装饰对象的引用。在调用装饰器的方法时，先调用被装饰对象的方法，然后再加上自己的行为。

• 比喻：穿衣服。人（核心对象）是最基本的。你可以动态地为他添加不同的装饰：穿衬衫（装饰器A）、穿西装（装饰器B）、打领带（装饰器C）。顺序可以改变，功能可以叠加，但人本身没有变化。

• .NET 示例：System.IO.Stream 体系就是装饰器模式的经典应用。FileStream、MemoryStream 是基础组件，而 GZipStream、CryptoStream、BufferedStream 都是装饰器，可以包裹在其它 Stream 外面，动态地添加压缩、加密、缓冲等功能。

// 组件接口
public interface IComponent
{
    string Operation();
}

// 具体组件
public class ConcreteComponent : IComponent
{
    public string Operation() => "ConcreteComponent";
}

// 装饰器基类
public abstract class Decorator : IComponent
{
    protected IComponent _component;

    public Decorator(IComponent component)
    {
        _component = component;
    }

    public virtual string Operation()
    {
        return _component.Operation();
    }
}

// 具体装饰器A
public class ConcreteDecoratorA : Decorator
{
    public ConcreteDecoratorA(IComponent component) : base(component) { }

    public override string Operation()
    {
        return $"ConcreteDecoratorA({base.Operation()})"; // 在核心功能前/后添加新行为
    }
}

// 具体装饰器B
public class ConcreteDecoratorB : Decorator
{
    public ConcreteDecoratorB(IComponent component) : base(component) { }

    public override string Operation()
    {
        return $"ConcreteDecoratorB({base.Operation()})";
    }
}

// 客户端使用
IComponent component = new ConcreteComponent();
Console.WriteLine(component.Operation()); // 输出: ConcreteComponent

// 用装饰器动态添加功能
IComponent decoratorA = new ConcreteDecoratorA(component);
IComponent decoratorB = new ConcreteDecoratorB(decoratorA); // 可以嵌套装饰！

Console.WriteLine(decoratorB.Operation());
// 输出: ConcreteDecoratorB(ConcreteDecoratorA(ConcreteComponent))

2.3 行为型模式 (Behavioral Patterns)

2.3.1 观察者模式 (Observer Pattern)

• 本质：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。

• 原理：主题（Subject）维护一个观察者（Observer）列表，并提供注册/注销方法。当主题状态变化时，调用 Notify 方法遍历观察者列表，调用每个观察者的更新方法。

• 比喻：微信公众号。你（观察者）关注了某个公众号（主题）。当公众号发布新文章（状态改变）时，所有关注者都会收到通知（推送）。你可以随时取消关注（注销）。

• .NET 示例：event 关键字就是观察者模式的语言级实现。IObservable< T > 和 IObserver< T > 接口。

// 定义事件参数
public class NewsEventArgs : EventArgs
{
    public string News { get; }

    public NewsEventArgs(string news)
    {
        News = news;
    }
}

// 主题 (Subject)
public class NewsPublisher
{
    // 声明事件（内置的观察者模式实现）
    public event EventHandler<NewsEventArgs> NewsPublished;

    public void PublishNews(string news)
    {
        Console.WriteLine($"Publisher: Publishing news - {news}");
        OnNewsPublished(new NewsEventArgs(news));
    }

    protected virtual void OnNewsPublished(NewsEventArgs e)
    {
        // 通知所有订阅者
        NewsPublished?.Invoke(this, e);
    }
}

// 观察者 (Observer)
public class Subscriber
{
    public string Name { get; }

    public Subscriber(string name)
    {
        Name = name;
    }

    // 事件处理程序（Update方法）
    public void OnNewsReceived(object sender, NewsEventArgs e)
    {
        Console.WriteLine($"{Name} received news: {e.News}");
    }
}

// 客户端使用
var publisher = new NewsPublisher();
var subscriber1 = new Subscriber("Alice");
var subscriber2 = new Subscriber("Bob");

// 订阅事件（注册观察者）
publisher.NewsPublished += subscriber1.OnNewsReceived;
publisher.NewsPublished += subscriber2.OnNewsReceived;

// 发布新闻，自动通知所有订阅者
publisher.PublishNews("Big announcement!");
// 输出:
// Publisher: Publishing news - Big announcement!
// Alice received news: Big announcement!
// Bob received news: Big announcement!

2.3.2 策略模式 (Strategy Pattern)

• 本质：定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换。策略模式使得算法可独立于使用它的客户而变化。

• 原理：将算法提取成一个个独立的策略类，这些类实现同一个策略接口。客户端持有一个策略接口的引用，可以动态地切换不同的具体策略。

• 比喻：出行导航。你要从A点到B点（上下文）。你可以选择不同的策略：最快路线（具体策略A）、最短路程（具体策略B）、避开高速（具体策略C）。导航App（客户端）可以根据你的选择，轻松切换不同的路线计算算法。

• 适用场景：一个系统需要在多种算法中选择一种，或者需要动态地在运行时切换算法。

// 策略接口
public interface ISortStrategy
{
    void Sort(int[] dataset);
}

// 具体策略A
public class BubbleSortStrategy : ISortStrategy
{
    public void Sort(int[] dataset) => Console.WriteLine("Sorting using Bubble Sort");
}

// 具体策略B
public class QuickSortStrategy : ISortStrategy
{
    public void Sort(int[] dataset) => Console.WriteLine("Sorting using Quick Sort");
}

// 上下文 (Context)
public class Sorter
{
    private ISortStrategy _strategy;

    public Sorter(ISortStrategy strategy)
    {
        _strategy = strategy;
    }

    // 动态设置策略
    public void SetStrategy(ISortStrategy strategy)
    {
        _strategy = strategy;
    }

    public void ExecuteSort(int[] data)
    {
        _strategy.Sort(data);
    }
}

// 客户端使用
var data = new int[] { 1, 5, 4, 3, 2 };
var sorter = new Sorter(new BubbleSortStrategy());
sorter.ExecuteSort(data); // 输出: Sorting using Bubble Sort

// 动态切换算法
sorter.SetStrategy(new QuickSortStrategy());
sorter.ExecuteSort(data); // 输出: Sorting using Quick Sort

---

总结与如何选择

模式	解决的核心问题	.NET 中的应用示例
工厂方法	对象创建的不确定性，希望解耦	WebRequest.Create, ILoggerFactory
单例	控制实例数目，节省资源	配置管理器、数据库连接池（需谨慎）
建造者	创建步骤复杂、配置灵活的对象	HttpClient 通过 HttpClientBuilder 配置
适配器	接口不兼容，无法协同工作	包装旧库、第三方库以适配新接口
装饰器	动态、透明地给对象添加功能	Stream -> GZipStream, CryptoStream
观察者	一个对象变化需要通知其他对象	event, IObservable< T >
策略	算法多变，需要在运行时选择	IComparer< T >（排序策略）、各种支付方式

核心思想：
不要为了用模式而用模式。发现代码中有“坏味道”（如难以扩展、僵化、耦合度高），再查看哪种模式能帮你优雅地解决这个问题。所有模式的本质都是“解耦”，通过引入抽象层来降低软件各部分的依赖性，从而提高代码的灵活性、可维护性和可测试性。