为什么 Dart 中的 HashSet<int> 比 HashSet<String> 慢很多？

Question

我注意到HashSet<int>在开发 Flutter 项目时执行速度非常慢。我在 a 中有大约 20,000 个整数Set，检查set.contains()花了很长时间。但是当我使用toString()将所有项目转换为字符串时，它的执行速度快了 1000 倍。

然后，我尝试使用 1000 万个随机整数创建一个最小的可重现代码，但无法重现该问题。事实证明，这些数据的某些特殊之处导致了速度极其缓慢。我在这个问题的末尾附上了测试代码（和数据）。

如何重现：

首先，单击“添加整数”按钮将 14790 个整数添加到集合中。然后单击“query int”（runs set.contains(123)）和“query string”（runs set.contains('123')）。观察到： 1. 两个操作都超级慢；2. int版本比string版本慢。图片：

然后点击“清除项目”，再点击“添加字符串”来添加toString()数据的版本。然后再次单击“query int”和“query string”，注意它变得快了多少。图片：

最后，单击“添加整数”和“添加字符串”以创建混合集（条目数量是两倍）。观察到该版本的查询时间减少了一半int，好像更快的字符串有助于“淡化”问题。图片：

我有几个朋友在不同的机器（intel i5、apple M1、snapdragon）上运行相同的测试代码，时间不同但结论是相同的。

这里没有答案：

以下是我考虑过的一些事情，但它们无法解释更多测试中发生的情况。

1. 也许int需要拳击，但string已经是一个物体了？

这可能不是这里的问题。对于 100 万个随机生成的值，整数的执行速度比字符串更快。

2. string是不可变的，因此它们的哈希值可以被缓存？

我不知道它们是否被缓存，但这并不能解释使用 100 万个随机生成的值观察到的结果。

3. inthash导致了很多冲突？

我尝试打印.hashCode数据集中的所有整数和字符串，并验证它们都是唯一的。

测试代码：

对于 StackOverflow 来说，包含数据的完整测试代码太长，我将其放在这里https://pastebin.com/raw/4fm2hKQB。

所以是的，我迷路了，如果有人能帮助我理解发生了什么，我将不胜感激！

Answer 1

我在 Dart repo 中评论了这个问题。为了完整起见，我将在这里提及评论的“答案”部分。

HashSet和的实现LinkedHashSet假设这些key.hashCode值是“好的”散列码，它们合理地分布在整数范围内，以便较低的 N 位不会冲突或几乎冲突而在散列表中“聚集”。不幸的int.hashCode是没有这个属性，因为它实际上是恒等函数。

当所有键的低位相同（或只有几个可能值）时，就会出现问题，因此采用较低的 N 位会给出相同的有效哈希码值。% 1000这只是@ch271828n 提到的示例的二次方版本。

@ch271828n 提到使用不同的 hashCode。这可能是最好的短期解决方案。LinkedHashSet(hashCode: dispersedHashCode)与这样的东西一起使用：

int dispersedHashCode(e) { // untested!
  int hash = e.hashCode;
  // Odd number with 30%-50% of the bits set in an irregular pattern.
  hash *= 0x1736B4D29;
  hash += hash >>> 20;
  // maybe do it again to let bits higher that 20 influence the low bits.
  return hash;
}

理想情况下，类似的东西应该内置到核心库的哈希结构中。这可能需要很长时间，因为实际上，具有简单解决方法的性能问题可能会优先于安全错误、不正确的行为错误、没有解决方法的性能问题以及使客户能够执行以下操作的新功能否则是不可能或很难做到的。

一种完全不同的方法是使用有序集，例如SplayTreeSet.

Answer 2

我也在考虑哈希冲突问题。

int hash 导致了很多冲突？我尝试打印数据集中所有整数和字符串的 .hashCode，并验证它们都是唯一的。

那么，“全部唯一”并不意味着“没有冲突”。对于哈希集，bin 的数量远小于 hashcode 的数量。例如，假设您有一个包含 1000 个 bin 的哈希集，并且从 hashCode 到 bin 索引的映射很简单bin index := hashCode % 1000，并且假设您的数据具有像 0、1000、2000、3000 等这样的 hashCode。在这种人工情况下，您的数据具有所有唯一的 hashCode，但它们都属于 1000 个 bin 中的第一个 bin。巨大的碰撞！

调试是否是hashcode问题的简单方法：用 .rerun 程序LinkedHashSet(hashCode: (e) => some_other_hash_approach(e), equals: ...)。通过使用这样一个新的哈希集，您可以测试其他 hashCode 生成函数。如果某些hashCode生成函数没有导致同样极慢的速度，那么很可能是因为原来的hashCode函数导致了冲突。

此外，您甚至可以对 int 和 String 情况使用相同的 hashCode 方法。然后您可以保证这两种情况具有完全相同的碰撞行为。这样就很容易看出碰撞是否是原因，或者是无关的。

另一种调试方法：查看 的 C++ 源代码LinkedHashSet，看看它使用什么算法将数据分配给 bin。然后检查是否发生上述碰撞。

第三种调试方法：将纯 Dart 程序编译为可执行文件，然后使用分析器perf来运行它。然后你可以看到哪些代码最热并且消耗最多的时间。您可能需要 Dart 原生 C++ 代码的调试符号，该符号应该是可获取的。