You need to enable JavaScript to run this app. 如何基于.NET泛型集合实现支持O(1)访问的Table<R,C,V>泛型表结构
优惠活动
大模型
产品
解决方案
定价
更多

如何基于.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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.24 14:06:00