ImmutableDictionary 枚举顺序

Question

与下面的类似问题已被问到，具体参考此处的字典：Dictionary<TKey, TValue> 的枚举器是否按添加顺序返回键值对？这里：字典枚举顺序

阅读这些内容可以清楚地看出，不应依赖 Dictionary 的枚举顺序。根据字典枚举的非确定性顺序，我最近观察到，当针对 .NET Core 3.1（在分支中）构建测试项目时，单元测试间歇性失败（在构建机器上）。相比之下，针对 .NET Framework 4.7.2（在不同分支上）构建的同一测试项目没有失败。这些观察结果是在许多单独的单元测试执行中得出的。最终，我将失败追溯到数值运算（超过 1/x 的求和），其中值（x）存储在以String. 在单元测试的情况下，求和的顺序会影响结果。计算中已应用修复：使用 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：“aDictionary确实以相同的顺序返回项目（假设您没有触发哈希表的大小调整）”。同样，我知道不应依赖当前的排序行为，但不清楚在什么情况下（例如，使用 .NET Framework、.NET Standard、.NET Core 时）执行之间的排序实际上有所不同。我的问题是：

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

Answer 1

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

这里的问题取决于您使用的密钥类型。如果您使用string密钥类型（我在这里做出有根据的猜测，这就是您正在使用的类型），那么在 .NET Core 中，您将遇到以下问题：同一字符串的哈希码在每个密钥类型上都不同应用程序执行。

你可以在这里读更多关于它的内容

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

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

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

这里的答案是枚举器如何为每种类型工作。对于 Core 中的 Dictionary<TKey,TValue>，本质上有两个集合：哈希值和条目（请参阅本文中的图表）。Dictionary 的枚举使用了条目，并且条目大体上按照添加的顺序出现，因此与哈希函数无关。枚举器代码可以在Dictionary的KeyCollection的自定义枚举器中看到。

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

希望能涵盖它。