字典使用元组作为键比嵌套字典慢，为什么？

Question

我已经测试了使用（int，int，string）元组作为键和使用嵌套字典Dictionary>>作为键来检索、更新和删除值的速度。

我的测试结果显示，元组字典要慢得多（检索58％，更新69％，删除200％）。我没有预料到这一点。嵌套字典需要进行更多的查找，那么为什么元组字典会慢那么多呢？

我的测试代码：

    public static object TupleDic_RemoveValue(object[] param)
    {
        var dic = param[0] as Dictionary<(int did, int eid, string name), string>;
        var keysToRetrieve = param[2] as List<(int did, int eid, string name)>;

        foreach (var key in keysToRetrieve)
        {
            dic.Remove(key);
        }

        return dic;

    }


    public static object NestedDic_RemoveValue(object[] param)
    {
        var dic = param[1] as Dictionary<int, Dictionary<int, Dictionary<string, string>>>;
        var keysToRetrieve = param[2] as List<(int did, int eid, string name)>;


        foreach (var key in keysToRetrieve)
        {
            if (dic.TryGetValue(key.did, out var elementMap) && elementMap.TryGetValue(key.eid, out var propertyMap))
                propertyMap.Remove(key.name);
        }

        return dic;

    }

测试额外信息： 该字典包含总共10,000条条目。键是递增的：([0-100]，[0-100]，“Property [0-100]”)。 在单个测试中，检索了100个键（其中10%不在字典中），更新了100个值（其中10％是新的）或删除了100个键（其中10％开始时不在字典中）。检索、更新和删除分别进行了3次测试。每次测试执行1000次。我比较了平均执行时间和中位数执行时间。

- Coder14

---

元组的HashCode()是如何计算的 - 它的成本比计算3个单独的int，int，string的HashCodes()更高吗？您使用了什么样本大小进行测量，用什么时间来计时？也许将所示代码扩大到一个真正的最小完整可验证示例。有3个字典可以更快地将数据切割成更小的分区进行搜索，而不是只有一个巨大的字典 - 因此后者在设计上可能更快。最好将元组与非匿名类进行比较，这比您所做的更公平。 - Patrick Artner

在执行的测试中添加了更多信息。我们目前在代码中使用嵌套字典。我们正在考虑在可能的情况下使用元组字典，但是由于这些字典操作在某些情况下成为应用程序的瓶颈，因此可能会变得明显较慢。 - Coder14

Answer 1

在字典中进行查找依赖于两个因素。首先是一个项目的哈希码，它用于将项目分成桶。两个不同的键可以具有相同的哈希码，因此一旦找到潜在匹配项，将对每个具有该哈希码的项调用Equals，直到找到完全匹配的项为止。 ValueTuple 的哈希码实现（对于元数为2+ *）将元组中每个项的 EqualityComparer.Default.GetHashCode 结果传递给一个名为 ValueTuple.CombineHashCodes 的内部方法，该方法又调用了 System.Numerics.Hashing.HashHelpers.Combine。元组中的项越多，则对这两个 Combine 方法的嵌套调用就越多。相比之下，普通int 的GetHashCode 只是直接返回该值。

对我来说，你后面的例子更快是有道理的。正如评论中指出的那样，还要将搜索所需的数据划分为更小的分区。每次查找都必须调用GetHashCode，并在找到潜在匹配项后调用Equals。在第一种情况下，似乎有更高的哈希冲突的几率，这意味着需要调用更多的Equals（在此情况下，只是对元组中的每个项目调用 EqualityComparer.Default.Equals ）。

最终，它取决于分析（而且是“正确”的分析- Release Mode，调用jitting，足够的迭代等）以及您的特定用例。

如果性能在您的用例中非常重要（例如，在一个紧密循环的查找中），可能最好使用自己的类型和哈希码/等价实现，而不是ValueTuple 。但再次强调，这取决于分析。

*请注意，对于1-arity元组有一个特殊情况。 HashHelpers.Combine ValueTuple Int32.GetHashCode

- pinkfloydx33