Retrieve original key from dictionary

Question

Is there a way to directly access the original key object from a C# Dictionary (where the key is a reference type)? I've seen this question asked on a different site (http://www.pcreview.co.uk/forums/get-original-key-object-dictionary-t3351718.html) and since most responders didn't understand why this is a reasonable question/not symptomatic of bad underlying design, I give background detail below.

The workarounds I have so far are:

(a) iterate over the keys checking for equality, which is O(n) complexity :(

(b) maintain an additional intern pool (e.g. another Dictionary that maps the keys to themselves). This gets us to O(1) complexity but requires extra memory, extra work when items are added to the dictionary, risk of failing to get this coordination right... none of this is fatal but it's not ideal and would not be necessary if Dictionary<> offered a method to retrieve the key by key.

Specifically, I have a Dictionary< State, List< State>> which represents a state graph: each key represents a state of a state machine and the associated value is a list of neighbour states directly reachable from there. e.g. the state could represent the configuration of a chess board, and the neighbouring states would be the configurations reachable in a single move.

I am populating the state graph by starting from an initial state, constructing the list of neighbours and then recursively calling the population routine for each of those neighbours. At each stage the algorithm checks whether a neighbour state is already a key in the Dictionary (otherwise we'll never finish). State is a reference type (i.e. a class) with overridden GetHashCode and Equals methods.

Semantically, this works fine. But now the lists of neighbours are distinct copies of the states rather than the original copy, so if there are N states with an average of M neighbours each, we have NxM State objects in memory, when we really only want N State objects and NxM references to State objects. Besides blowing up memory footprint it makes equality testing slow because you can't benefit from the reference-equality shortcut in Equals().

From the comments it seems the problem isn't clear, so here is some pseudo-code to illustrate it better:

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

You can create a 'pool' of State, and then, when creating, use existing if one was already created. Sample:

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