在软件开发中，我们经常需要在各种集合类型中进行选择。.NET 框架为我们提供了丰富的集合类型，如 List<T> 适合按索引访问元素，Dictionary<TKey, TValue> 适合按键快速查找，但有时我们需要同时具备两种能力的集合。本文将介绍 KeyedList<TKey, TValue> 这一强大的混合型集合，它巧妙地结合了列表和字典的优势，提供了更灵活的数据访问方式。
安装方法
要使用 KeyedList，首先需要安装 LuYao.Common NuGet 包：
# 使用 .NET CLI
dotnet add package LuYao.Common
# 或使用 Package Manager Console
Install-Package LuYao.CommonNuGet 包链接：https://www.nuget.org/packages/LuYao.Common
安装后，添加以下命名空间引用：
using LuYao.Collections.Generic;KeyedList 是什么？
KeyedList<TKey, TValue> 是一个泛型集合，同时支持通过索引和键值访问元素。与标准 Dictionary 不同，它允许一个键对应多个值，并且保留了元素的插入顺序。
/// <summary>
/// 提供一个泛型集合，它同时支持通过索引和键值访问元素。
/// </summary>
/// <typeparam name="TKey">用于标识集合中元素的键的类型。</typeparam>
/// <typeparam name="TValue">集合中元素的类型。</typeparam>
public class KeyedList<TKey, TValue> : IList<TValue>, IComparer<KeyedList<TKey, TValue>.Entry>何时使用 KeyedList？
以下场景特别适合使用 KeyedList：
- 需要同时按索引和键访问数据
- 例如，UI 控件绑定时既需要按索引访问也需要按某个属性快速查找
- 保持插入顺序很重要
- 当你需要记住元素添加顺序，但又需要基于某个属性快速查找
- 一个键可能对应多个值
- 标准字典一个键只能对应一个值，而 KeyedList 可以处理多对多的关系
- 频繁按序列位置和属性值访问元素
- 比如实现分页显示但又需要快速查找特定记录
基本用法
1. 创建 KeyedList
// 创建一个 KeyedList，使用 Person 的 Id 属性作为键
var people = new KeyedList<int, Person>(p => p.Id);
// 使用自定义比较器
var customPeople = new KeyedList<string, Person>(
p => p.Name,
StringComparer.OrdinalIgnoreCase // 不区分大小写比较
);2. 添加和访问元素
// 添加元素
people.Add(new Person { Id = 1, Name = "Alice" });
people.Add(new Person { Id = 2, Name = "Bob" });
people.Add(new Person { Id = 3, Name = "Charlie" });
// 按索引访问（像普通列表一样）
Person firstPerson = people[0]; // Alice
// 检查是否包含特定键
bool hasId2 = people.ContainsKey(2); // true
// 获取特定键的第一个元素的索引
int indexOfId2 = people.IndexOfKey(2); // 1
// 读取所有具有相同键的元素（可能有多个）
foreach (var person in people.Read(2))
{
Console.WriteLine(person.Name); // 输出: Bob
}3. 修改元素
// 修改特定索引的元素
people[1] = new Person { Id = 4, Name = "David" };
// 插入元素
people.Insert(1, new Person { Id = 5, Name = "Eve" });
// 移除元素
people.Remove(people[0]); // 移除第一个元素
people.RemoveAt(0); // 移除当前的第一个元素内部工作原理
KeyedList 内部使用两个核心组件：
- 内部列表
_list：存储实际元素，保持插入顺序 - 缓存数组
_cache：存储键和索引的映射，按键排序以支持二分查找
private List<TValue> _list = new List<TValue>();
private Entry[]? _cache;当进行键相关操作时，KeyedList 会惰性构建缓存：
private Entry[] BuildCache()
{
int count = _list.Count;
if (count == 0) return Arrays.Empty<Entry>();
return this._list
.Select((item, index) => new Entry
{
Key = KeySelector(item),
Index = index
})
.OrderBy(e => e.Key, KeyComparer)
.ThenBy(e => e.Index)
.ToArray();
}任何修改操作都会使缓存失效（_cache = null），这样下次访问时会重新构建缓存。
性能特性和复杂度分析
了解 KeyedList 的性能特性对于正确使用它至关重要：
时间复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 按索引访问 | O(1) | 直接访问内部列表 |
| 按键查找（首次） | O(n log n) | 需要先构建缓存 |
| 按键查找（后续） | O(log n) | 使用二分查找 |
| 添加元素 | O(1) | 添加到列表末尾，但使缓存失效 |
| 插入/删除元素 | O(n) | 需要移动元素，并使缓存失效 |
空间复杂度
KeyedList 的空间复杂度为 O(n)，但实际上需要存储：
- 原始元素列表（n 个元素）
- 缓存数组（n 个 Entry 对象，每个包含键和索引）
所以实际使用的空间约为原始数据的两倍。
最佳实践与注意事项
- 避免频繁修改后立即查找
- 每次修改后再查找需要重建缓存，如果可能，尽量批量修改后再进行查找操作
- 键选择器函数的稳定性
- 确保键选择器函数返回稳定的值，如果元素的键值在集合中发生变化，需要重新添加该元素
- 相同键的处理
- KeyedList 允许多个元素具有相同的键，使用
Read(key)方法获取所有匹配元素
- 内存消耗
- 由于维护了额外的缓存，KeyedList 比普通列表消耗更多内存
- 适用场景评估
- 如果只需要按索引访问，使用
List<T> - 如果只需要按键访问且键是唯一的，使用
Dictionary<TKey, TValue> - 如果需要同时兼顾两种访问方式或一个键对应多个值，才考虑使用 KeyedList
示例应用场景
场景一：UI 控件数据绑定
// 人员列表，既需要按位置访问，又需要按ID查找
var employeeList = new KeyedList<int, Employee>(e => e.EmployeeId);
// 填充数据
LoadEmployees().ForEach(e => employeeList.Add(e));
// 绑定到列表控件
dataGridView.DataSource = employeeList;
// 当需要查找特定员工时
void FindEmployee(int id)
{
if (employeeList.ContainsKey(id))
{
int index = employeeList.IndexOfKey(id);
dataGridView.CurrentCell = dataGridView.Rows[index].Cells[0];
}
}场景二：处理重复键的数据
// 订单系统中，一个客户可能有多个订单
var ordersByCustomer = new KeyedList<string, Order>(o => o.CustomerId);
// 添加订单
orders.ForEach(o => ordersByCustomer.Add(o));
// 获取特定客户的所有订单
void ShowCustomerOrders(string customerId)
{
var customerOrders = ordersByCustomer.Read(customerId);
foreach (var order in customerOrders)
{
Console.WriteLine($"订单号: {order.OrderId}, 金额: {order.Amount}");
}
}结论
KeyedList 是一个强大的混合型集合，它融合了列表和字典的优势，为开发者提供了更灵活的数据访问方式。虽然它在某些场景下可能引入额外的性能开销，但在需要同时按索引和键访问元素的情况下，它提供了极大的便利性。
通过理解其内部工作原理、性能特性和适用场景，你可以更好地评估是否在你的项目中使用 KeyedList，以及如何最优地利用它的特性。
希望这篇文章能帮助你理解和有效使用 KeyedList。如有任何问题或建议，欢迎在评论区留言讨论！
