ImmutableDictionary枚举顺序 [英] ImmutableDictionary enumeration order

问题描述

有人提出了与以下类似的问题，具体参考了此处的Dictionary:字典枚举顺序

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

阅读这些内容很明显，不应该依赖Dictionary的枚举顺序.与字典的不确定性枚举顺序一致，最近我观察到针对.NET Core 3.1(在分支中)构建测试项目时，单元测试在构建机器上间歇性失败(在构建机器上).相反，针对.NET Framework 4.7.2(在不同分支上)构建的同一测试项目没有失败.这些观察结果涉及许多单独的单元测试执行.最终，我将故障追溯到数值运算(总和超过1/x)，其中数值(x)存储在以 String 键控的ImmutableDictionary中.对于单元测试，求和顺序会影响结果.一个修复程序已应用于计算:使用ImmutableSortedDictionary.

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.

一个简化的代码段展示了 ImmutableDictionary 中的键的不同顺序(针对.NET Core 3.1进行编译并多次执行以观察不同的枚举):

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()));
}

但是，正如在回答有关 Dictionary 的问题中指出的那样:一个 Dictionary 确实会以相同的顺序返回项目(假设您不会触发调整大小为哈希表").同样，我知道不应依赖当前的排序行为，但尚不清楚在什么情况下(例如，使用.NET Framework，.NET Standard，.NET Core时)，执行之间的排序实际上是不同的.我的问题是:

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:

为什么ImmutableDictionary(在.NET Framework 4.7.2中)在执行之间以相同的顺序返回项目，而ImmutableDictionary(在.NET Core 3.1中)却始终以不同的顺序返回项目?

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?

推荐答案

因为"string"的哈希函数.NET Core中的内容是不确定的.

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

这里的问题取决于您使用的密钥类型.如果您使用 string 作为密钥类型(在这里我正在做一个有根据的猜测，那就是您正在使用的)，那么在.NET Core中您会遇到哈希码的问题相同的字符串在每个应用程序执行中都是不同的.

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.

您可以详细了解此处

在.NET Framework中，相同的字符串在每次执行时生成相同的哈希码，因此在枚举过程中它们的顺序始终保持不变.

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

针对您的情况，您可以尝试切换到一种类型，在该类型中，您可以通过类型本身(例如int)来提供确定性哈希函数，或者为类型提供自定义哈希函数.

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.

尽管原始问题中还有一个后续问题-为什么Dictionary< string，x>是为什么?确定性地枚举，但ImmutableDictionary< string，x>如果两者都以字符串为键，并且在每次应用程序执行时字符串生成不同的哈希值，则将不确定地枚举.

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.

答案是枚举器对每种类型的工作方式.对于字典< TKey，TValue>.在Core中，基本上有两个集合，即散列和条目(请参阅此

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.

但是对于ImmutableDictionary，枚举遵循哈希值(请参阅在ImmutableDictionary中调用的HashBucket.Enumerator).因此，在Framework中，字符串一致地进行哈希处理，一切都很好，而哈希保留了它们的顺序.现在，在Core中，使用字符串键，每次运行的哈希值都不同，它们的求值位置不同，因此顺序也不同.

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.

希望能掩盖它.

这篇关于ImmutableDictionary枚举顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！