c# - 与平面数组相比，.Net 中的简单字典查找速度较慢

Question

我发现与平面数组访问相比，字典查找可能会非常慢。知道为什么吗？我正在使用 Ants Profiler 进行性能测试。这是重现问题的示例函数:

    private static void NodeDisplace()
    {
        var nodeDisplacement = new Dictionary<double, double[]>();

        var times = new List<double>();
        for (int i = 0; i < 6000; i++)
        {
            times.Add(i * 0.02);
        }
        foreach (var time in times)
        {
            nodeDisplacement.Add(time, new double[6]);
        }

        var five = 5;
        var six = 6;
        int modes = 10;
        var arrayList = new double[times.Count*6];
        for (int i = 0; i < modes; i++)
        {
            int k=0;
            foreach (var time in times)
            {
                for (int j = 0; j < 6; j++)
                {

                    var simpelCompute = five * six;  // 0.027 sec
                    nodeDisplacement[time][j] = simpelCompute;  //0.403 sec
                    arrayList[6*k+j] = simpelCompute;  //0.0278 sec
                }

                k++;
            }
        }
    }

注意到平面数组访问和字典访问之间的相对大小了吗？考虑到数组索引操作 (6*k+j)，平面数组比字典访问 (0.403/0.0278) 快大约 20 倍。

虽然听起来很奇怪，但字典查找占用了我大部分时间，我必须对其进行优化。

Answer 1

是的，我并不感到惊讶。字典的要点是它们用于查找任意键。考虑对于单个数组取消引用必须发生什么:

• 检查边界
• 将索引乘以元素大小
• 为指针添加索引

非常非常快。现在进行字典查找(非常粗略；取决于实现):

• 可能检查 key 是否无效
• 获取 key 的哈希码
• 为该哈希码找到正确的位置(可能是“mod prime”操作)
• 可能取消对数组元素的引用以查找该槽的信息
• 比较哈希码
• 如果哈希码匹配，比较是否相等(并可能继续下一个哈希码匹配)

如果您有可以很容易用作数组索引的“键”(例如，连续的整数，或者可以很容易地映射到连续的整数) ) 那么那将非常非常快。这不是哈希表的主要用例。它们适用于不能以这种方式轻松映射的情况 - 例如按字符串查找，或按任意 double 值 (而不是均匀分布的 double ，因此可以轻松映射到整数)。

我会说您的标题具有误导性 - 不是字典查找速度慢，而是当数组是更合适的方法时，它们快得离谱。