Dictionary ordering of custom comparable keys is not deterministic

[Euan-McVie]

Describe the bug

We have dictionaries where the key has custom equality and hashcode (actually they are automatic via record but the issue is the same)

When verifying the order of the keys sometimes swaps. I have been unable to work out why when the input object to verify is the same as some rusn are the expected way around and others are not.

The resulting comparison is non-deterministic resulting in flaky tests.

Note that we are actually using json and immutable dictionaries, but I can see the issue with a simple repro using a plain dictionary.

Minimal Repro

I can see that that the existing test DictionaryOrderNonComparable is only validating when created alphabetically.

To recreate update the DictionaryOrderNonComparable test to provide Foo2 before Foo1.

Not sure if multiple runs are required as it always happens when I run an equivalent locally, but our full object tests it is flaky and sometimes does pass with no code changes.

public class VerifyImmutableDictionaryTests
{
    [Fact]
    public Task DictionaryOrderNonComparable()
    {
        var dictionary = new Dictionary<NonComparableKey, string>
        {
            [new("Foo2")] = "Bar",
            [new("Foo1")] = "Bar",
        };

        return Verify(dictionary);
    }

    private sealed class NonComparableKey(string member)
    {
        public override string ToString() =>
            member;

        public override int GetHashCode() =>
            member.GetHashCode(StringComparison.InvariantCulture);
    }
}

Verified:

{
  Foo1: Bar,
  Foo2: Bar
}

Received:

{
  Foo2: Bar,
  Foo1: Bar
}