title: Efficient way of retrieving an item from a collection with a mutable key
body: <p>I have a collection of items <em>Foos</em> that have a property <em>FooPosition</em>, and I need to quickly access <em>Foos</em> by their positions.</p>
  <p>For example : retrieve a <em>Foo</em> which is located at X=0 and Y=1.</p>
  <p>My first thought was to use a dictionary for that purpose nd to use the FooPosition as dictionary key.  I know that every <em>FooPosition</em> in my collection is unique, I don't mind throwing an Exception if it is not the case.</p>
  <p>This works well as long as <em>Foos</em> do not move all over the place.</p>
  <p>But, as I figured out the hard way, and understood thanks to <a href="https://stackoverflow.com/questions/55531617/does-c-sharp-dictionary-store-only-the-reference-of-the-object-or-the-full-copy">this</a> and <a href="https://stackoverflow.com/questions/3007296/c-sharp-dictionary-and-mutable-keys">this</a> posts, this does not work anymore if the <em>FooPosition</em> is updated. <strong>I shouldn't use mutable keys in a dictionary</strong> : the dictionary keeps the <em>FooPosition</em> HashCode in memory but does not update it when the underlying <em>FooPosition</em> is modified. Therefore, calling dic[Position(0,1)] gives me the <em>Foo</em> which was at this position when the dictionary was built.</p>
  <p>So, I am now wondering what should I use to retrieve <em>Foos</em> by their positions efficiently.</p>
  <p>By efficiently I mean not going all across the whole collection every time I query for a Foo by its position. Is there a suitable structure which would accomodate mutable keys?</p>
  <p>Thanks for your help</p>
  <p><strong>EDIT</strong></p>
  <p>As mentioned rightfully in comments, there is a missing part in my question : I have no control over <em>Foo</em> Moves. The software is actually connected to another software (Excel via VSTO) via a COM Protocol which changes the FooPosition (Excel Ranges) without notifying the change.</p>
  <p>Therefore, I cannot take take any action <em>in case a move happens</em> because I don't know that a change did happen.</p>
  <pre><code>public class FooManager
  {
      public void DoSomething(IList&lt;Foo&gt; foos) {
          Dictionary&lt;FooPosition, Foo&gt; fooPositionDictionary = foos.ToDictionary(x =&gt; x.Position, x =&gt; x); //I know that position is unique
  
          //Move Foos all around the place by changing their positions. 
  
          FooPosition queryPosition = new FooPosition(0, 1);
  
          fooPositionDictionary.TryGetValue(queryPosition, out var foo1); //DOES NOT WORK
          var foo2 = foos.FirstOrDefault(x =&gt; x.Position == queryPosition); //NOT EFFICIENT
  
          //Any better idea?
      }
  }
  
  public class Foo
  {
      public string Name { get; set; }
      public FooPosition Position { get; set; }
  }
  
  public class FooPosition : IEquatable&lt;FooPosition&gt;
  {
      public int X { get; set; }
      public int Y { get; set; }
  
      public FooPosition(int x, int y)
      {
          X = x;
          Y = y;
      }
  
      public void MoveBy(int i)
      {
          X = X + i;
          Y = Y + i;
      }
  
      public bool Equals(FooPosition other)
      {
          if (ReferenceEquals(null, other)) return false;
          if (ReferenceEquals(this, other)) return true;
          return X == other.X &amp;&amp; Y == other.Y;
      }
  
      public override bool Equals(object obj)
      {
          if (ReferenceEquals(null, obj)) return false;
          if (ReferenceEquals(this, obj)) return true;
          if (obj.GetType() != this.GetType()) return false;
          return Equals((FooPosition) obj);
      }
  
      public override int GetHashCode()
      {
          unchecked
          {
              return (X * 397) ^ Y;
          }
      }
  
      public static bool operator ==(FooPosition left, FooPosition right)
      {
          return Equals(left, right);
      }
  
      public static bool operator !=(FooPosition left, FooPosition right)
      {
          return !Equals(left, right);
      }
  }
  </code></pre>