Efficient way of retrieving an item from a collection with a mutable key

Question

I have a collection of items Foos that have a property FooPosition, and I need to quickly access Foos by their positions.

For example : retrieve a Foo which is located at X=0 and Y=1.

My first thought was to use a dictionary for that purpose nd to use the FooPosition as dictionary key. I know that every FooPosition in my collection is unique, I don't mind throwing an Exception if it is not the case.

This works well as long as Foos do not move all over the place.

But, as I figured out the hard way, and understood thanks to this and this posts, this does not work anymore if the FooPosition is updated. I shouldn't use mutable keys in a dictionary : the dictionary keeps the FooPosition HashCode in memory but does not update it when the underlying FooPosition is modified. Therefore, calling dic[Position(0,1)] gives me the Foo which was at this position when the dictionary was built.

So, I am now wondering what should I use to retrieve Foos by their positions efficiently.

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?

Thanks for your help

EDIT

As mentioned rightfully in comments, there is a missing part in my question : I have no control over Foo 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.

Therefore, I cannot take take any action in case a move happens because I don't know that a change did happen.

public class FooManager
{
    public void DoSomething(IList<Foo> foos) {
        Dictionary<FooPosition, Foo> fooPositionDictionary = foos.ToDictionary(x => x.Position, x => 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 => 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<FooPosition>
{
    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 && 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);
    }
}

Answer 1

In some sense a dictionary - as any other hash-based data-storage - uses some kind of caching. In this case the hashes are cached. However as for every cache you need some constant data that does not change during the lifetime of that data-storage. If there is no such constant data, there´s no way to efficiently cache that data.

So you end up to store all items in some linear collection - e.g. a List<T>- and iterate that list again and again.