15-集合：字典和哈希表

字典（Dictionary）和哈希表（Hashtable）用于存储键值对（Key-Value Pair），通过键快速查找对应的值。

一、为什么需要字典？

场景： 有一个学生名单，需要根据学号快速找到学生姓名。

csharp

// 方式一：用两个数组（查找慢）
string[] ids = { "001", "002", "003", "004" };
string[] names = { "张三", "李四", "王五", "赵六" };

// 查找学号 "003" 的学生——需要遍历！
string FindName(string targetId)
{
    for (int i = 0; i < ids.Length; i++)
        if (ids[i] == targetId)
            return names[i];
    return null;
}

// 方式二：用字典（查找快，O(1)）
Dictionary<string, string> studentMap = new Dictionary<string, string>
{
    { "001", "张三" },
    { "002", "李四" },
    { "003", "王五" },
    { "004", "赵六" }
};

string name = studentMap["003"];  // 直接获取，无需遍历！

字典的核心优势： 通过键直接定位，查找效率 O(1)，远快于数组/列表的 O(n)。

二、Dictionary<TKey, TValue>（泛型字典）

1. 创建和初始化

csharp

using System.Collections.Generic;

// 空字典
Dictionary<string, int> ages = new Dictionary<string, int>();

// 指定容量（优化性能）
Dictionary<string, string> config = new Dictionary<string, string>(100);

// 集合初始化器
Dictionary<string, string> capitals = new Dictionary<string, string>
{
    { "中国", "北京" },
    { "美国", "华盛顿" },
    { "日本", "东京" }
};

// 索引器初始化器（C# 6.0+）
Dictionary<string, int> scores = new Dictionary<string, int>
{
    ["张三"] = 95,
    ["李四"] = 88,
    ["王五"] = 72
};

2. 常用成员

成员	说明	注意事项
`Add(key, value)`	添加键值对	键重复会抛出 `ArgumentException`
`Remove(key)`	删除键值对	返回 bool 表示是否删除成功
`Clear()`	清空字典
`ContainsKey(key)`	是否包含键	O(1)
`ContainsValue(val)`	是否包含值	O(n)（需遍历）
`TryGetValue(key, out val)`	安全取值	不存在不抛异常，返回 false
`Count`	键值对数量
`Keys`	所有键的集合	可遍历，不能修改
`Values`	所有值的集合	可遍历，不能修改

3. 基本操作

csharp

Dictionary<string, int> ages = new Dictionary<string, int>();

// 添加
ages.Add("张三", 25);
ages.Add("李四", 30);
ages.Add("王五", 28);

// 访问（键不存在会抛出 KeyNotFoundException）
Console.WriteLine(ages["张三"]);  // 输出：25

// 安全访问（推荐！）
if (ages.TryGetValue("赵六", out int age))
{
    Console.WriteLine($"赵六的年龄：{age}");
}
else
{
    Console.WriteLine("未找到赵六");  // 会执行这里
}

// 检查键是否存在
if (ages.ContainsKey("李四"))
{
    Console.WriteLine($"李四的年龄：{ages["李四"]}");
}

// 修改值
ages["张三"] = 26;  // 键存在 → 修改
ages["赵六"] = 35;  // 键不存在 → 添加（索引器自动添加）

// 删除
ages.Remove("王五");  // 成功返回 true
ages.Remove("不存在"); // 失败返回 false（不抛异常）

// 遍历键值对
foreach (KeyValuePair<string, int> kvp in ages)
{
    Console.WriteLine($"{kvp.Key}：{kvp.Value}岁");
}

// 只遍历键
foreach (string name in ages.Keys)
    Console.WriteLine(name);

// 只遍历值
foreach (int a in ages.Values)
    Console.WriteLine(a);

4. Add 与索引器的区别

csharp

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

// Add：键重复时抛出异常
dict.Add("a", 1);
// dict.Add("a", 2);  // 异常：已包含键 "a"

// 索引器：键已存在则修改，不存在则添加（不会抛出异常）
dict["a"] = 2;     // 键 "a" 已存在 → 修改为 2
dict["b"] = 3;     // 键 "b" 不存在 → 添加

建议：

确定键不存在时添加 → 用 Add
不确定是否存在，或需要更新值 → 用索引器
需要先判断再决定 → 用 TryGetValue 或 ContainsKey

三、实际应用场景

场景一：词频统计

csharp

static Dictionary<string, int> WordCount(string text)
{
    var counts = new Dictionary<string, int>();
    // 移除标点符号，转为小写，分割单词
    char[] separators = " .,;!?\"'()[]{}".ToCharArray();
    string[] words = text.ToLower().Split(separators, StringSplitOptions.RemoveEmptyEntries);

    foreach (string word in words)
    {
        // 写法一：使用 ContainsKey
        // if (counts.ContainsKey(word))
        //     counts[word]++;
        // else
        //     counts[word] = 1;

        // 写法二：使用 TryGetValue（更高效）
        if (counts.TryGetValue(word, out int count))
            counts[word] = count + 1;
        else
            counts[word] = 1;
    }

    return counts;
}

string text = "the quick brown fox jumps over the lazy dog the quick brown fox";
var result = WordCount(text);

// 按词频降序输出
foreach (var kvp in result.OrderByDescending(x => x.Value))
    Console.WriteLine($"{kvp.Word}: {kvp.Count}");
// 输出：
// the: 3
// quick: 2
// brown: 2
// fox: 2
// ...

场景二：数据缓存

csharp

public class DataCache
{
    private static Dictionary<int, string> cache = new Dictionary<int, string>();

    public static string GetData(int id)
    {
        // 尝试从缓存获取
        if (cache.TryGetValue(id, out string cachedData))
        {
            Console.WriteLine($"[缓存] 命中 ID={id}");
            return cachedData;
        }

        // 缓存未命中，从数据库读取（模拟）
        Console.WriteLine($"[数据库] 查询 ID={id}");
        string data = $"用户数据-{id}";

        // 存入缓存
        cache[id] = data;
        return data;
    }

    public static void ClearCache() => cache.Clear();
}

// 第一次调用——查数据库
Console.WriteLine(DataCache.GetData(1));  // [数据库] 查询 ID=1
// 第二次调用——命中缓存
Console.WriteLine(DataCache.GetData(1));  // [缓存] 命中 ID=1

场景三：配置管理

csharp

class AppConfig
{
    private Dictionary<string, string> settings = new Dictionary<string, string>
    {
        { "AppName", "MyApplication" },
        { "Version", "1.0.0" },
        { "MaxUsers", "100" },
        { "Database", "Server=localhost;Database=mydb" },
        { "LogLevel", "Info" }
    };

    public string Get(string key, string defaultValue = "")
    {
        return settings.TryGetValue(key, out string value) ? value : defaultValue;
    }

    public void Set(string key, string value)
    {
        settings[key] = value;
    }

    public T Get<T>(string key, T defaultValue = default)
    {
        if (settings.TryGetValue(key, out string value))
        {
            try
            {
                return (T)Convert.ChangeType(value, typeof(T));
            }
            catch
            {
                return defaultValue;
            }
        }
        return defaultValue;
    }
}

// 使用
var config = new AppConfig();
Console.WriteLine(config.Get("AppName"));       // MyApplication
int maxUsers = config.Get("MaxUsers", 50);     // 100（带默认值的泛型版）
bool logDebug = config.Get("DebugMode", false); // false（使用默认值）

四、Hashtable（非泛型哈希表）

Hashtable 位于 System.Collections，可以存储任意类型的键和值。非泛型，有装箱拆箱问题。

csharp

using System.Collections;

Hashtable table = new Hashtable();

// 键和值都可以是任意类型
table.Add("name", "张三");
table.Add("age", 25);         // 值类型装箱
table.Add(100, "数字键");     // 键也可以是数值

// 访问
Console.WriteLine(table["name"]);  // 输出：张三

// 遍历
foreach (DictionaryEntry entry in table)
    Console.WriteLine($"{entry.Key}: {entry.Value}");

// 取出时需要强制转换
string name = (string)table["name"];
int age = (int)table["age"];  // 拆箱

Dictionary 与 Hashtable 对比

对比项	`Dictionary<TKey,TValue>`	`Hashtable`
类型安全	是（编译时检查）	否（运行时转换）
值类型性能	高（无需装箱）	低（装箱拆箱）
null 键	不允许（抛出异常）	允许
null 值	允许（值类型不行）	允许
遍历类型	`KeyValuePair<K,V>`	`DictionaryEntry`
推荐程度	✅ 首选	❌ 仅兼容旧代码

五、常见字典变体

SortedDictionary（按键排序）

csharp

// 自动按键排序的字典（红黑树实现）
SortedDictionary<string, int> sorted = new SortedDictionary<string, int>
{
    { "banana", 3 },
    { "apple", 5 },
    { "cherry", 2 }
};

foreach (var kvp in sorted)
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
// 输出（字母顺序）：
// apple: 5
// banana: 3
// cherry: 2

SortedList（排序列表）

csharp

// 类似 SortedDictionary，但内部使用数组（内存更紧凑）
SortedList<string, int> sortedList = new SortedList<string, int>
{
    { "banana", 3 },
    { "apple", 5 },
    { "cherry", 2 }
};

// 支持按索引访问（SortedDictionary 不支持）
Console.WriteLine(sortedList.GetKeyAtIndex(0));    // apple
Console.WriteLine(sortedList.GetValueAtIndex(0));  // 5

SortedDictionary vs SortedList

对比项	`SortedDictionary`	`SortedList`
内部实现	红黑树	两个数组（键和值）
内存使用	较大	较小
插入/删除性能	O(log n)	O(n)
按索引访问	不支持	支持

ConcurrentDictionary（线程安全）

csharp

using System.Collections.Concurrent;

// 多线程环境下安全的字典
ConcurrentDictionary<string, int> concurrent = new ConcurrentDictionary<string, int>();

concurrent.TryAdd("key1", 1);
concurrent.TryUpdate("key1", 2, 1);  // 原子操作
concurrent.GetOrAdd("key2", k => ComputeValue(k));  // 不存在则添加

六、字典键类型要求

作为键的类型必须正确实现 GetHashCode() 和 Equals()。

csharp

// ✅ 常用键类型（已正确实现）
// string, int, long, Guid, DateTime 等

// ❌ 可变对象作为键（危险！）
Dictionary<List<int>, string> bad = new Dictionary<List<int>, string>();
var key = new List<int> { 1, 2, 3 };
bad[key] = "value";
key.Add(4);  // 修改了键对象，导致字典无法正常工作！

// ✅ 自定义键类
class PersonKey
{
    public string Id { get; set; }
    public string Type { get; set; }

    public override bool Equals(object? obj)
    {
        return obj is PersonKey other && other.Id == Id && other.Type == Type;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(Id, Type);
    }
}

七、Dictionary 的性能优势

集合	查找复杂度	100,000 条数据查找耗时（约）
`List<T>`（遍历）	O(n)	毫秒级
`Dictionary<K,V>`（哈希）	O(1)	微秒级
`SortedDictionary<K,V>`	O(log n)	几十微秒级

csharp

// 验证性能差异
const int size = 100_000;
var list = Enumerable.Range(0, size).ToList();
var dict = Enumerable.Range(0, size).ToDictionary(i => i, i => i);

var sw = Stopwatch.StartNew();
bool found = list.Contains(99999);  // O(n) 遍历查找
sw.Stop();
Console.WriteLine($"List 查找：{sw.ElapsedTicks} ticks");

sw.Restart();
found = dict.ContainsKey(99999);    // O(1) 哈希查找
sw.Stop();
Console.WriteLine($"Dictionary 查找：{sw.ElapsedTicks} ticks");
// 差距可达数百倍！

核心知识点总结

何时使用字典？

场景	说明
通过键快速查找值	O(1) 查找效率
统计计数	词频、投票统计
数据缓存	避免重复计算或查询
配置管理	键值对配置项
映射关系	ID ↔ 名称、编码 ↔ 含义
去重	键必须唯一

注意事项

键必须唯一：重复添加会抛出异常或覆盖
键不可变：作为键的对象不要修改（影响哈希值）
优先使用 TryGetValue：代替 ContainsKey + 索引器（少一次查找）
指定容量：已知数据量时 new Dictionary<K,V>(capacity) 减少扩容
多线程用 ConcurrentDictionary：普通 Dictionary 非线程安全
键类型选择：优先使用 string、int、Guid 等不可变类型

15-集合：字典和哈希表 ​

一、为什么需要字典？ ​

二、Dictionary<TKey, TValue>（泛型字典） ​

1. 创建和初始化 ​

2. 常用成员 ​

3. 基本操作 ​

4. Add 与索引器的区别 ​

三、实际应用场景 ​

场景一：词频统计 ​

场景二：数据缓存 ​

场景三：配置管理 ​

四、Hashtable（非泛型哈希表） ​

Dictionary 与 Hashtable 对比 ​

五、常见字典变体 ​

SortedDictionary（按键排序） ​

SortedList（排序列表） ​

SortedDictionary vs SortedList ​

ConcurrentDictionary（线程安全） ​

六、字典键类型要求 ​

七、Dictionary 的性能优势 ​

核心知识点总结 ​

何时使用字典？ ​

注意事项 ​

15-集合：字典和哈希表

一、为什么需要字典？

二、Dictionary<TKey, TValue>（泛型字典）

1. 创建和初始化

2. 常用成员

3. 基本操作

4. Add 与索引器的区别

三、实际应用场景

场景一：词频统计

场景二：数据缓存

场景三：配置管理

四、Hashtable（非泛型哈希表）

Dictionary 与 Hashtable 对比

五、常见字典变体

SortedDictionary（按键排序）

SortedList（排序列表）

SortedDictionary vs SortedList

ConcurrentDictionary（线程安全）

六、字典键类型要求

七、Dictionary 的性能优势

核心知识点总结

何时使用字典？

注意事项