如何基于.NET泛型集合实现支持O(1)访问的Table<R,C,V>泛型表结构
实现思路说明
- 你选择字典嵌套字典的方向完全正确,要达成行键、列键O(1)访问的性能要求,双层哈希字典是最优实现方案:外层字典以行键
R为索引,存储对应行的内层列字典Dictionary<C, V>,查找时先通过R定位到行的内存地址,再通过C定位到具体值,两步哈希查找的平均时间复杂度均为O(1),完全符合要求。 - 你之前写的
Dictionary<Dictionary<FootballTeam, Tournament>, HashSet<int>>嵌套方式存在根本缺陷:Dictionary是可变引用类型,没有内置值相等比较逻辑,无法稳定作为字典键使用,会导致内容完全相同的键因为实例引用不同被识别为不同条目,直接出现查找失败的问题。
通用Table<R,C,V>结构实现
核心是把双层字典的访问逻辑封装成独立的泛型类,提供符合直觉的使用接口,核心代码如下:
public class Table<R, C, V> { // 核心存储:外层键为行键R,值为对应行的列键-值映射字典 private readonly Dictionary<R, Dictionary<C, V>> _rowStore; private readonly IEqualityComparer<R> _rowKeyComparer; private readonly IEqualityComparer<C> _colKeyComparer; public Table() : this(EqualityComparer<R>.Default, EqualityComparer<C>.Default) { } public Table(IEqualityComparer<R> rowKeyComparer, IEqualityComparer<C> colKeyComparer) { _rowKeyComparer = rowKeyComparer; _colKeyComparer = colKeyComparer; _rowStore = new Dictionary<R, Dictionary<C, V>>(_rowKeyComparer); } // 双参数索引器,支持直接通过[行键, 列键]读写值,使用体验和二维表一致 public V this[R rowKey, C colKey] { get { if (!_rowStore.TryGetValue(rowKey, out var rowDict)) throw new KeyNotFoundException($"不存在对应行键: {rowKey}"); if (!rowDict.TryGetValue(colKey, out var value)) throw new KeyNotFoundException($"当前行下不存在对应列键: {colKey}"); return value; } set { // 行不存在时自动创建新的列字典,无需手动初始化 if (!_rowStore.TryGetValue(rowKey, out var rowDict)) { rowDict = new Dictionary<C, V>(_colKeyComparer); _rowStore[rowKey] = rowDict; } rowDict[colKey] = value; } } // 安全读取方法:键不存在时返回false,不抛出异常 public bool TryGet(R rowKey, C colKey, out V value) { value = default; if (!_rowStore.TryGetValue(rowKey, out var rowDict)) return false; return rowDict.TryGetValue(colKey, out value); } // 行/单元格删除能力 public bool RemoveRow(R rowKey) => _rowStore.Remove(rowKey); public bool RemoveCell(R rowKey, C colKey) { if (!_rowStore.TryGetValue(rowKey, out var rowDict)) return false; return rowDict.Remove(colKey); } // 遍历能力:支持获取所有行、某行下的所有列 public IEnumerable<R> GetAllRows() => _rowStore.Keys; public IEnumerable<C> GetColumnsInRow(R rowKey) { if (!_rowStore.TryGetValue(rowKey, out var rowDict)) throw new KeyNotFoundException($"不存在对应行键: {rowKey}"); return rowDict.Keys; } }
前置必要修正:自定义实体的键比较逻辑
你之前写的FootballTeam、Tournament类如果要作为Table的键使用,必须重写Equals和GetHashCode方法,不然会走.NET默认的引用相等判断——哪怕两个对象的所有字段完全一致,只要是不同的实例,就会被识别为不同的键,导致存进去的值读不出来。
修正后的实体类示例:
public class FootballTeam { public string Title { get; set; } public string City { get; set; } public int FoundationYear { get; set; } public FootballTeam(string title, string city, int foundationYear) { Title = title; City = city; FoundationYear = foundationYear; } // 字段完全一致才判定为同一个队 public override bool Equals(object? obj) { return obj is FootballTeam team && Title == team.Title && City == team.City && FoundationYear == team.FoundationYear; } // 用所有参与相等判断的字段计算哈希值 public override int GetHashCode() => HashCode.Combine(Title, City, FoundationYear); public override string ToString() => $"{Title} ({City}, {FoundationYear}年建队)"; } public class Tournament { public string Title { get; set; } public bool International { get; set; } public int FoundationYear { get; set; } public Tournament(string title, bool international, int foundationYear) { Title = title; International = international; FoundationYear = foundationYear; } public override bool Equals(object? obj) { return obj is Tournament tourn && Title == tourn.Title && International == tourn.International && FoundationYear == tourn.FoundationYear; } public override int GetHashCode() => HashCode.Combine(Title, International, FoundationYear); public override string ToString() => $"{Title} ({(International ? "国际赛事" : "国内赛事")}, {FoundationYear}年创办)"; }
演示用例:足球队夺冠年份表
按照需求创建Table<FootballTeam, Tournament, HashSet<int>>实例,填充测试数据:
// 初始化表实例 var championRecordTable = new Table<FootballTeam, Tournament, HashSet<int>>(); // 复用已定义的测试实体 var dynamoKyiv = new FootballTeam("Dinamo", "Kyiv", 1927); var ukraineTopLeague = new Tournament("乌克兰顶级联赛", false, 1992); var uefaChampions = new Tournament("欧洲冠军联赛", true, 1955); // 写入单元格值:基辅迪纳摩在乌超的夺冠年份 championRecordTable[dynamoKyiv, ukraineTopLeague] = new HashSet<int> {1993, 1994, 1995, 2020, 2021}; // O(1)时间复杂度读取值 var dynamoLeagueTitles = championRecordTable[dynamoKyiv, ukraineTopLeague]; Console.WriteLine($"基辅迪纳摩在乌超的夺冠年份:{string.Join("、", dynamoLeagueTitles)}"); // 安全读取不存在的单元格 if (championRecordTable.TryGet(dynamoKyiv, uefaChampions, out var championTitles)) { Console.WriteLine($"基辅迪纳摩在欧冠的夺冠年份:{string.Join("、", championTitles)}"); } else { Console.WriteLine("基辅迪纳摩从未获得过欧冠冠军"); }
Table结构的常见应用场景
- 电商定价:
Table<Product, Region, decimal>,行键为商品,列键为销售区域,值为对应区域的商品定价 - 成绩管理:
Table<Student, Course, int>,行键为学生,列键为课程,值为对应课程的考试得分 - 服务监控:
Table<DateOnly, Service, long>,行键为日期,列键为微服务名称,值为对应日期下服务的总请求量 - 多环境配置:
Table<DeployEnv, ConfigKey, string>,行键为部署环境(开发/测试/生产),列键为配置项名称,值为对应配置的实际取值
内容的提问来源于stack exchange,提问作者Sviatoslav
相关产品推荐
相关产品推荐

