從字典中檢索原始密鑰

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]; 
    } 
}