C#字典
HasTable
Hashtable 通常称为哈希表，它表示键/值对的集合，这些键/值对根据键的哈希代码进行组织。它的每个元素都是一个存储在DictionaryEntry对象中的键/值对。键不能为空引用，但值可以。
命名空间：System.Collections
是一种基于哈希算法实现的键值对集合类，提供高效的查找、插入和删除操作。作为非泛型集合，Hashtable 的键和值均为 object 类型，适用于需要快速存储和检索数据的场景。
Hash算法: 对任意内容进行算法计算,返回一个整数(哈希值), 内容不相等, hash算法得到哈希值可能一样 (hash冲突,碰撞)
HashTable解决hash冲突, 使用开放寻址法, 计算下标处有元素, 元素key与添加元素key不一样, 下标加增量得到新的下标, 判断新下标是否有元素, 如果没有, 添加在该位置, 如果有继续往后查找
虽然 Hashtable 仍然可用，但在新项目中通常建议使用泛型的 Dictionary<K, V>，因为它避免装箱和拆箱操作，提供更好的类型安全和性能。
Dictionary<K,V>
1、Dictionary概念及特征
1.1、Dictionary概念
Dictionary<K, V>是.NET框架中的泛型集合类，属于System.Collections.Generic命名空间。它以键值对的形式存储数据，每个键必须唯一，但值可以重复。
1.2、Dictionary特征
- 类型安全：通过泛型避免装箱拆箱操作
- 高效查找：基于哈希表实现，平均O(1)时间复杂度
- 动态扩容：容量不足时自动扩展
- 键唯一性：确保每个键在字典中只出现一次
2、Dictionary底层原理
2.1、Dictionary采用哈希表架构，使用两个核心数组
主要由以下部分组成：
- 桶数组(Bucket Array)：存储条目的索引
- 条目数组(Entry Array)：实际存储键值对的数据结构
- 空闲链表：管理空闲位置的链表
private struct Entry {public uint hashCode; // 哈希码的低31位public int next; // 指向链表中下一个条目的索引public TKey key; // 键public TValue value; // 值
}
private int[] _buckets; // 桶数组，存储条目索引
private Entry[] _entries; // 条目数组
private int _count; // 已存储的键值对数量
private int _freeList; // 空闲条目链表的起点
private int _freeCount; // 空闲条目数量
private int _version; //版本
-
buckets数组：存储指向entries的索引
-
entries数组：存储实际的KeyValuePair数据
-
哈希计算:
- 对键调用
GetHashCode()获取哈希值 - 使用
hashCode & 0x7FFFFFFF确保为正数 - 取模运算确定桶位置：
bucketIndex = hashCode % buckets.Length
- 对键调用
-
冲突处理：使用链地址法(拉链法)解决哈希冲突
- 使用链地址法解决哈希冲突
- 每个桶中的条目通过
next字段形成链表
-
扩容机制：负载因子超过0.72时触发扩容
2.2、Dictionary整体架构设计解析
1、双数组存储结构
Dictionary采用数组作为底层存储，核心由桶数组（Bucket Array）与条目数组（Entry Array）协同构成。桶数组存储条目索引，条目数组存放实际键值对，分离设计实现高效寻址。
2、O(1)查询效率保障
独立的buckets数组通过哈希值直接定位下标，避免遍历整个数据集，将查询时间复杂度稳定在常数级别，即使数据量激增也能保持极速响应。
2.3、Dictionary初始化机制深度剖析
1、无参构造的懒加载策略
无参构造初始容量设为3，但数组内存延迟至首次Add操作才分配，避免空字典的内存浪费，优化启动性能。
2、指定容量的立即初始化
传入capacity参数的构造函数在实例化瞬间完成数组分配，适用于预知数据规模的场景，减少运行时扩容开销。
3、构造方法底层源码
无参
添加元素
有参
初始容量
推荐： 数据规模确定则使用有参构造指定容量；数据规模不确定则使用无参构造
2.4、Entry节点结构与哈希冲突解决
2.4.1、Entry节点结构
2.4.2、为什么会有hash冲突？
2.4.3、处理hash冲突
Dictionary采用链地址法解决冲突，将哈希值相同的Entry以链表形式存储于同一桶位置。相较于开放寻址法，链表结构在冲突严重时仅需遍历短链，删除操作无需重新探测，实现更简洁高效。
即：
链表长度直接影响查询性能，当元素数量超过容量与负载因子乘积时触发扩容。扩容后重新哈希所有元素，分散链表长度，将平均查找时间恢复至O(1)水平，维持字典高效运转。
3、基础语法与操作
3.1、创建与初始化
// 基本声明与实例化
Dictionary<string, int> dict1 = new Dictionary<string, int>();
// 集合初始化器 (C# 3.0+)
Dictionary<string, int> dict2 = new Dictionary<string, int>
{{ "Alice", 30 },{ "Bob", 25 }
};
// 索引器初始化 (C# 6.0+)
Dictionary<string, int> dict3 = new Dictionary<string, int>
{["Alice"] = 30,["Bob"] = 25
};
// 指定初始容量优化性能
Dictionary<string, int> dict4 = new Dictionary<string, int>(100);
性能提示： 预估数据量并指定初始容量可以减少扩容次数，提升性能。
3.2、添加元素
在 Dictionary<TKey, TValue> 中，可以通过 Add() 方法 或 索引器 [] 向字典中添加键值对。
1、使用Add()方法添加
Dictionary<int, string> dict = new Dictionary<int, string>();dict.Add(1, "Apple");
dict.Add(2, "Banana");
特点：
- 用于向字典中添加新的键值对。
- 键必须唯一。
- 如果添加的键已经存在，则会 抛出异常 ArgumentException。
2、使用索引器 [] 添加
dict[1] = "Apple";
dict[2] = "Banana";
dict["alice"] = 18;
特点：
- 如果键 不存在 → 添加新的键值对。
- 如果键 已经存在 → 更新对应的值。
3.3、访问元素
在 Dictionary<TKey, TValue> 中，可以通过 键（Key） 来访问对应的值（Value）。
1、使用索引器 [] 访问
Dictionary<int, string> dict = new Dictionary<int, string>();
dict.Add(1, "Apple");
dict.Add(2, "Banana");
string value = dict[1];
Console.WriteLine(value);
特点：
- 使用
dict[key]获取对应的值。 - 如果 键不存在，程序会抛出 KeyNotFoundException 异常。
2、使用 TryGetValue() 方法
string value;
if (dict.TryGetValue(1, out value))
{Console.WriteLine(value);
}
else
{Console.WriteLine("键不存在");
}
特点：
- 返回值是
bool- true → 找到键
- false → 没找到
- 如果找到，值会通过 out 参数返回。
3、检查键值是否存在，ContainsKey() ContainsValue()
bool hasAlice = dict1.ContainsKey("Alice");bool hasAge30 = dict1.ContainsValue(30);
3.4、修改与删除
在 Dictionary<TKey, TValue> 中，可以通过 Remove()、Clear() 方法以及索引器 [] 来修改或删除元素。
1、修改元素
通过 索引器 [] 根据键修改对应的值。
Dictionary<int, string> dict = new Dictionary<int, string>();
dict.Add(1, "Apple");
dict.Add(2, "Banana");
// 修改 value
dict[1] = "Orange";
说明：
- 如果 key 存在 → 修改对应的 value
- 如果 key 不存在 → 会新增一个键值对
2、删除元素
使用 Remove() 方法根据键删除元素。
dict.Remove(1);
说明：
- 根据 key 删除对应的键值对。
- 返回值是 bool
- true → 删除成功
- false → 键不存在
3、清空字典
使用 Clear() 方法删除字典中的所有元素。
dict.Clear();
说明：
- 清空整个
Dictionary - 删除所有键值对
3.5、遍历字典
可以使用foreach循环遍历字典中的所有键值对，或者分别遍历键和值。
// 遍历键值对foreach (KeyValuePair<string, int> kvp in dict1) Console.WriteLine($"{kvp.Key}: {kvp.Value}");// 简化写法foreach (var kvp in dict1) Console.WriteLine($"{kvp.Key}: {kvp.Value}");// 只遍历键foreach (string name in dict1.Keys) Console.WriteLine(name);// 只遍历值foreach (int age in dict1.Values) Console.WriteLine(age);
4、与Hashtable的区别
5、了解扩展方法
扩展方法是 C# 的一个特性，它允许在不修改原有类源码的情况下，为已有类型添加新的方法。
也就是说，可以像调用实例方法一样调用这个新方法，但实际上它是一个 静态方法。
基本特点
- 必须定义在静态类（static class）中
- 方法必须是 static
- 第一个参数必须使用 this 修饰
- 第一个参数表示要扩展的类型
// OrderBY() 扩展方法 升序
// 根据key进行升序
var items = dict.OrderBy(kv => kv.Key);
foreach (var item in items) Console.WriteLine($"{item.Key}:{item.Value}");
// OrderByDescending() 扩展方法 降序
// 根据Value进行降序
items = dict.OrderByDescending(kv => kv.Value);
foreach (var item in items) Console.WriteLine($"{item.Key}:{item.Value}");