ImmutableDictionary 枚举顺序 [英] ImmutableDictionary enumeration order
问题描述
一个与下面类似的问题已经被问到，具体参考这里的字典:做字典的枚举器
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 问题的回答所述:a 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.
您可以阅读有关它的更多信息这里
You can read more about it here
在 .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
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.
然而，对于 ImmutableDictionary，枚举遵循散列(请参阅 ImmutableDictionary 中调用的 HashBucket.Enumerator).所以在框架中，字符串一致地散列，一切都很好，散列保留了它们的顺序.但是现在在 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屋！
