ImmutableDictionary enumeration order

Question

A similar question to the below has been asked with specific reference to Dictionary here: Does the Enumerator of a Dictionary<TKey, TValue> return key value pairs in the order they were added? and here: Dictionary enumeration order

Reading these it is clear that the ordering of enumeration of Dictionary should not be relied upon. In line with the non-deterministic order of enumeration of a Dictionary, I recently observed unit tests failing intermittently (on a build machine) when a test project was built targeting .NET Core 3.1 (in a branch). In contrast, the same test project built targeting .NET Framework 4.7.2 (on a different branch) had no failures. These observations were over many separate unit test executions. Eventually I traced the failures to numerical operations (summation over 1/x) where the values (x's) were stored in an ImmutableDictionary keyed with a String. In the case of the unit test the order of summation affected the result. A fix has been applied to the calculations: the use of an ImmutableSortedDictionary.

A cut-down code snippet that demonstrates the different ordering of keys in ImmutableDictionary is here (compile targeting .NET Core 3.1 and execute multiple times to observe the different enumeration):

static void Main(string[] args)
{
    var dict = ImmutableDictionary<string,double>.Empty;
    for (int i = 0; i < 10; i++)
    {
        dict = dict.Add(i.ToString(),i);
    }
            
    Console.WriteLine("Keys collection: " + string.Join(", ",dict.Keys.ToList()));
    Console.WriteLine("Keys during enumeration: " +string.Join(", ", dict.Select(c => c.Key).ToList()));
}

However, as noted in answers to questions about Dictionary: "a Dictionary does return items in the same order (assuming that you don't trigger a resize of the hashtable)". Again, I understand that the current ordering behaviour should not be relied upon but it isn't clear in what situations (e.g. when using .NET Framework, .NET Standard, .NET Core) the ordering actually differs between executions. My question is:

Why does an ImmutableDictionary (in .NET Framework 4.7.2) return items in the same order between executions but an ImmutableDictionary (in .NET Core 3.1) consistently return items in a different order?

Answer 1

Because the hash function for "string" in .NET Core is non-deterministic.

The issue here depends on the key type that you're using. If you're using string for the key type (I'm making an educated guess here that that's what you're using), in .NET Core you'll run into the issue that the hash code for the same string is different on each application execution.

You can read more about it here

In .NET Framework the same strings generated the same hash codes on each execution, so their order always remained the same during enumeration.

For your situation, you could try switching to a type where either you have a deterministic hash function either by the type itself (eg int) or supplying a type with a custom hash function.

There is a follow up question though in the original question - why is it that Dictionary<string,x> enumerates deterministically, but ImmutableDictionary<string,x> enumerates non deterministically, if both are keyed on strings, and strings generate different hashes on each application execution.

The answer here is how the enumerator works for each type. For the Dictionary<TKey,TValue> in Core, there are essentially two collections, the hashes, and the entries (see the diagrams in this article). The enumeration of Dictionary uses the entries, and by and large the entries appear in the order they were added, so it has nothing to do with the hashing function. The enumerator code you can see in the custom enumerator of KeyCollection of Dictionary here.

However for the ImmutableDictionary, the enumeration follows the hashes (see the HashBucket.Enumerator that is called in the ImmutableDictionary). So in Framework, where strings hashed consistently, everything was fine, the hashes retained their order. Now in Core though, using a string key, the hashes are different on each run, they evaluate to different positions, their order is hence different.

Hope that covers it.

Answer 2

Lists are deterministic in order, but dictionaries are not. So solve the issue, you can make a hybrid of the two:

public class DeterministicThing<TKey, TValue> :
    IEnumerable<KeyValuePair<TKey, TValue>>
    where TKey : notnull
{
    private readonly ImmutableList<KeyValuePair<TKey, TValue>> kvpList;
    private readonly ImmutableDictionary<TKey, TValue> kvpDictionary;

    public DeterministicThing(IEnumerable<KeyValuePair<TKey, TValue>> kvps)
    {
        kvpList = kvps.ToImmutableList();
        kvpDictionary = kvps.ToImmutableDictionary(pair => pair.Key, pair => pair.Value);
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() => kvpList.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => kvpList.GetEnumerator();
    public TValue this[TKey key] => kvpDictionary[key];

    public int Count => kvpList.Count;
}