从字典中检索原始密钥

Question

有没有一种方法可以直接从C＃Dictionary（其中的密钥是引用类型）访问原始密钥对象？我在另一个网站（http://www.pcreview.co.uk/forums/get-original-key-object-dictionary-t3351718.html）上看到过这个问题，并且由于大多数响应者不明白为什么这是一个合理的问题/没有不良的底层设计的症状，所以我在下面给出了背景细节。

我的解决方法，到目前为止有：

（a）中迭代键检查平等，这是O（n）的复杂性:(

（b）中维持的附加实习生池（例如另一个将键映射到自己的字典），这使我们获得了O（1）的复杂性，但需要额外的内存，当项目被添加到字典时需要额外的工作，没有得到这种协调的风险......这些都不是致命的但它并不理想，如果Dictionary <>提供了一种通过密钥检索密钥的方法，则不是必需的。具体来说，我有一个字典< State，List < State >>它代表一个状态图：每个键表示一个状态机的状态，相关的值是从那里直接可到达的邻居状态列表。例如国家可以代表国际象棋棋盘的配置，邻国可以是一次移动中可达到的配置。

我从初始状态开始填充状态图，构造邻居列表，然后递归调用每个邻居的总体例程。在每个阶段，算法检查邻居状态是否已经是字典中的一个关键字（否则我们永远不会完成）。 State是一个重写GetHashCode和Equals方法的引用类型（即一个类）。

语义上，这工作正常。但是现在邻居列表是状态的不同副本，而不是原始副本，所以如果有N个状态，每个状态平均有M个邻居，则我们在内存中有NxM个状态对象，当我们只需要N个状态对象和NxM对状态对象的引用。除了消耗内存占用量之外，它使得相等性测试变慢，因为您无法从Equals（）中的引用等同快捷键中受益。

从评论看来问题不明确，所以这里是一些伪代码来说明它更好地：

public class StateGraphExample 
{ 
    public static void Main() 
    { 
     State initialState = State.GetInitialState(); 
     var graph = new Dictionary<State, List<State>>(); 
     BuildGraph(initialState, graph); 
    } 

    public static void BuildGraph(State state, Dictionary<State, List<State>> graph) 
    { 
     var neighbours = new List<State>(); 

     foreach (State.Move move in state.GetValidMoves()) 
      neighbours.Add(state.ApplyMove(move)); 

     graph[state] = neighbours; 

     foreach (State neighbour in neighbours) 
      if (!graph.ContainsKey(neighbour)) 
       BuildGraph(neighbour, graph); 
    } 

    public class State 
    { 
     //Lots of data members here... 

     public static State GetInitialState() 
     { /* Return State object representing initial state... */ } 

     public class Move 
     { /* Representation of a move that takes us from one State to another... */ } 

     public List<State.Move> GetValidMoves() 
     { /* Return valid moves from this State object... */ } 

     public State ApplyMove(State.Move move) 
     { /* Clones this State object, applies move to it and returns the result... */ } 

     public override int GetHashCode() 
     { /* Compute hash... */ } 

     public override bool Equals(object obj) 
     { /* Test equality... */ } 

     private State Clone() 
     { /* Clone self... */ } 
    } 
} 

Answer 1

您可以创建一个State“池”，然后，当创建，如果已经创建了，则使用现有的。示例：

class Sample : IEquatable<Sample> 
{ 
    private int _params; 
    private Sample(int params) { _params = params; } 

    private static HashSet<Sample> _samples = new HashSet<Sample>(); 

    public static GetSample(int params) 
    { 
    Sample s = new Sample(params); 
    if (!_samples.ContainsKey(s)) 
     _samples.Add(s); 

    return _samples[s]; 
    } 
}