Dictionary<string, int> 是否保留插入顺序？

Question

我使用C#已经有10多年了，但今天我发现Dictionary<string, int>保留了插入顺序？据我所知，Dictionary内部是使用哈希表实现的，所以内部排列应该没有特定的顺序，但是下面的测试代码似乎显示遍历时的顺序和插入的顺序是一模一样的？

        const int N = 1000000;

        List<string> ss = new List<string>();
        Dictionary<string, int> dict = new Dictionary<string, int>();

        for (int i = 0; i < N; ++i)
        {
            var s = string.Empty;
            for (int j = 0; j < 15; ++j)
                s += (char)('a' + UnityEngine.Random.Range(0, 26));

            //ss.add(s);
            ss.Add(new string(s));

            //dict[s] = UnityEngine.Random.Range(0, 1024);
            dict.Add(s, UnityEngine.Random.Range(0, 1024));
        }

        int same = 0;

        var keys = dict.Keys.ToArray();

        for (int i = 0; i < N; ++i)
        {
            if (keys[i] == ss[i])
                ++same;
        }

        Debug.Log($"N={N}, same={same}");
        
        // the output is : N=1000000, same=1000000

现在我想知道我的测试代码是否有问题？

谁能确认DictionaryC#中的遍历顺序是插入顺序？

可靠吗？

Answer 1

我查看了实现Dictionary<TKey, TValue>（通过在 Visual Studio 中将文本光标单击 Alt-F12 ）。我不完全理解；但是，我注意到使用两个数组来存储条目：Dictionary<string, int>

private int[]? _buckets;
private Entry[]? _entries;

确实是_buckets通过哈希码访问的。即，这就是哈希表。通过调试，我注意到条目以随机顺序添加到 中_buckets，但以顺序顺序添加到 中_entries。_buckets包含一个索引_entries。这解释了为什么可以按照条目添加到字典中的顺序检索条目。

此行为是由于实现细节造成的。因此，我不会依赖它，因为未来版本中的实现可能会发生变化。事实上，Dictionary<TKey, TValue>过去的实施方式已经发生了变化。另外，我不知道这个顺序是否始终维持，或者是否存在可能被打破的情况。

测试设置：.NET 8.0 控制台应用程序/C# 12

public static void Test()
{
    const int N = 1000000;

    List<string> list = [];
    Dictionary<string, int> dict = [];
    Type type = dict.GetType();

    for (int i = 0; i < N; ++i) {
        string s = String.Empty;
        for (int j = 0; j < 4; ++j) {
            s += (char)('a' + Random.Shared.Next(26));
        }
        list.Add(s);
        dict[s] = i; // Adding i simplifies analysis, as _entries[i].value now reflects the order.

        // Retrieve the dictionary's private fields at every iteration, since they are reallocated when they are resized.
        int[]? _buckets = (int[]?)type.GetField("_buckets", BindingFlags.Instance | BindingFlags.NonPublic)?.GetValue(dict);
        object? _entries = type.GetField("_entries", BindingFlags.Instance | BindingFlags.NonPublic)?.GetValue(dict);
    } // <<< place a breakpoint here and inspect _buckets and _entries.

    int same = 0;
    string[] keys = dict.Keys.ToArray();
    for (int i = 0; i < keys.Length; ++i) {
        if (keys[i] == list[i]) {
            ++same;
        }
    }

    Console.WriteLine($"N={keys.Length}, same={same}");
}