c# - ImmutableDictionary 枚举顺序

Question

在此处具体引用词典时，已提出与以下类似的问题:Does the Enumerator of a Dictionary<TKey, TValue> return key value pairs in the order they were added?在这里:Dictionary enumeration order

阅读这些很明显，不应该依赖 Dictionary 的枚举顺序。根据字典枚举的不确定顺序，我最近观察到当针对 .NET Core 3.1(在分支中)构建测试项目时，单元测试间歇性地(在构建机器上)失败。相比之下，针对 .NET Framework 4.7.2(在不同的分支上)构建的同一测试项目没有失败。这些观察是在许多单独的单元测试执行中进行的。最终，我追踪到数值运算(对 1/x 求和)的失败，其中值 (x's) 存储在以 String 键控的 ImmutableDictionary 中。在单元测试的情况下，求和的顺序会影响结果。已对计算应用修复:使用 ImmutableSortedDictionary。

演示 ImmutableDictionary 中键的不同排序的简化代码片段位于此处(编译目标 .NET Core 3.1 并执行多次以观察不同的枚举):

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 时)执行之间的排序实际上有所不同。我的问题是:

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

Answer 1

因为 .NET Core 中“字符串”的哈希函数是不确定的。

此处的问题取决于您使用的 key 类型。 如果您使用 string 作为 key 类型(我在这里做出有根据的猜测，这就是您正在使用的类型)，在 .NET Core 中您将遇到哈希码的问题对于相同的字符串在每次应用程序执行时都是不同的。

您可以阅读更多相关信息 here

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

对于您的情况，您可以尝试切换到一种类型，您可以通过类型本身(例如 int)或提供具有自定义哈希函数的类型来获得确定性哈希函数。

虽然在原始问题中有一个后续问题 - 为什么 Dictionary 确定性枚举，但 ImmutableDictionary 非确定性枚举，如果两者都以字符串为键，并且字符串生成不同每个应用程序执行的哈希值。

这里的答案是枚举器如何针对每种类型工作。对于 Core 中的 Dictionary，本质上有两个集合，即哈希和条目(参见 article 中的图表)。 Dictionary 的枚举使用条目，并且大体上条目按添加的顺序出现，因此它与哈希函数无关。在Dictionary here的KeyCollection的自定义枚举器中可以看到枚举器代码.

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

希望涵盖它。