如何引用引用类型字典键的属性？

Question

我正在开发一个国际象棋引擎，目前正在实现置换表（存储过去移动中已经评估的棋盘位置）。大致思路是，在进行一次移动时，我会检查置换表是否存在相应的位置。如果存在，则跳过昂贵的评估过程，直接从置换表中取出先前计算的结果。如果不存在，则执行所需的计算，再将其添加到置换表中以备将来使用。

对我而言，这听起来像是哈希集或字典的工作。我选择了字典。我想让键表示我棋盘的类，值为遇到该位置的次数的整数计数器。计数的原因是为了检测三次重复和棋局面。如果同一局面出现三次或以上，则玩家可以选择宣布和棋。使用字典而不是哈希集，可以通过将其与我的置换表结合使用，大大简化检测三次重复和棋的过程。

为了做到这一点，我重写了表示棋盘状态的类的Equals()和GetHashCode()方法。它工作得很好，我现在能够追踪游戏之前遇到的所有历史状态。

我的问题是，我需要能够访问字典中键对象的属性。我可以看到是否存在匹配项（使用.ContainsKey(...)方法和我的Equals()/GetHashCode()逻辑），但现在我需要从键中提取前面提到的已计算值（存储为我的棋盘状态对象的公共属性）。

我想到了以下代码：

BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.GetHashCode() == this.GetHashCode());

这个方法虽然可行，但是对我来说感觉很笨拙。转置表的整个目的是为了加速对数百万连续棋盘状态的递归搜索。为每个匹配查询一个字典听起来有些违反直觉。有没有更好的方法来解决这个问题呢？

编辑： 正如所指出的那样，由于有效的棋盘状态数量巨大，我的哈希函数可能不完美。我的Equals（）重写检查第二个交替生成的哈希来减少碰撞的可能性。我的上述 "解决方案" 是有缺陷的，因为它依赖于不完美的哈希。我应该使用：

BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.Equals(this));

我的疏忽造成了这个错误。但我不喜欢查字典。

- Chronicide

---

@Servy 是的，但是根据所示的代码，OP似乎对与哈希码匹配的任何结果都感到满意... - Yahia

他已经实现了自己的哈希码，那么现在也许它是唯一的了？楼主，是这种情况吗？如果是... - Kevin Versfeld

@Servy 我不知道他是否应该对此感到高兴...尽管这有点奇怪... - Yahia

@Yahia 哈希不是完美的，这就是Equals()的用处。我有一个校验和（第二个散列算法），Equals()除了检查校验和之外还检查它。我的Lambda函数确实没有考虑到主哈希的潜在冲突。我没有考虑过这一点。我应该使用Equals。 - Chronicide

@Chronicide，由于您没有创建“100％独特/无冲突哈希”，我的选项将无法工作... - Yahia

Answer 1

一种选择是在字典的值中保存键的引用，以及字典的实际值，例如：

Dictionary<BoardState, Tuple<BoardState, int>>

每当您添加一个对象时，将相同的对象作为键和值添加：

Dictionary<BoardState, Tuple<BoardState, int>> boards = 
    new Dictionary<BoardState,Tuple<BoardState,int>>();
BoardState board = new BoardState();
boards.Add(board, Tuple.Create(board, 1));

另一种选择（可能更好的设计）是将您的棋盘状态对象分成两种不同类型。其中一个确实只表示棋盘的状态（这应该是不可变的），另一个则包含有关该状态的其他信息，包括其发生的时间和任何适用于您特定应用程序的其他可变属性。这将使您无需访问字典键。请保留HTML标签。

- Servy

---

我喜欢将状态分离的想法...虽然这不是最简单的解决方案，但它似乎是正确的方向。 - Chronicide

我还应该注意到，我选择了你的答案，因为你的第一个解决方案不仅回答了我的问题，而且暗示着没有直接访问键属性的简单方法（这就是我自己冗长的方式）。顺便说一下，我特定情况下的另一个解决方案是为置换表运行哈希集，并为三次重复规则运行单独的字典。这有额外的好处，即消歧，其中每个人只负责一件事，而不涉及其他事情。 - Chronicide