。网：如何有效地检查 50,000 个项目的 List<string> 中的唯一性？

Question

在某些库代码中，我有一个可以包含 50,000 个或更多项目的列表。

库的调用者可以调用导致将字符串添加到列表中的方法。如何有效地检查所添加字符串的唯一性？

目前，在添加字符串之前，我会扫描整个列表并将每个字符串与要添加的字符串进行比较。当超过 10,000 个项目时，就会出现规模问题。

我将对此进行基准测试，但对洞察力感兴趣。

• 如果我用 Dictionary<> 替换 List<> ，当列表增长到 10,000 个项目或更多时，ContainsKey() 会明显更快吗？
• 如果我将唯一性检查推迟到添加所有项目之后，会更快吗？那时我需要对照每个其他元素检查每个元素，仍然是 n^^2 操作。

---

编辑

一些基本的基准测试结果。我创建了一个公开 2 个方法的抽象类：填写并扫描。Fill 只是用 n 个项目填充集合（我使用了 50,000 个）。Scan 扫描列表 m 次（我使用了 5000 次）以查看给定值是否存在。然后我为 List 构建了该类的实现，为 HashSet 构建了另一个类的实现。

使用的字符串长度统一为 11 个字符，并通过抽象类中的方法随机生成。

一个非常基本的微基准。

Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180

Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431

因此，对于该长度的字符串，在扫描唯一性时，HashSet 比 List 快大约 25 倍。此外，对于这种大小的集合，在向集合添加项目时，HashSet 比 List 的惩罚为零。

结果很有趣，但无效。为了获得有效的结果，我需要进行预热间隔、多次试验，并随机选择实现。但我相信这只会稍微改变标准。

感谢大家。

编辑2

添加随机化和多次试验后，在这种情况下，HashSet 的性能始终优于 List，约 20 倍。

这些结果不一定适用于可变长度的字符串、更复杂的对象或不同的集合大小。

Answer 1

您应该使用 HashSet<T> 类，它是专门为您正在做的事情而设计的。

Answer 2

使用 HashSet<string> 代替 List<string>, ，那么它应该可以很好地扩展。

Answer 3

从我的测试来看， HashSet<string> 与相比不需要时间 List<string> :)

Answer 4

可能偏离主题，但如果您想以独立于语言的方式扩展非常大的独特字符串集（数百万+），您可以查看 布隆过滤器.

Answer 5

是否 Contains(T) 功能不适合你？

Answer 6

我读到字典 <> 是作为关联数组实现的。在某些语言（不一定与 .NET 相关）中，字符串索引存储为树结构，该结构根据节点中的字符在每个节点处分叉。请参见 http://en.wikipedia.org/wiki/Associative_arrays.

Aho 和 Corasick 在 1973 年设计了类似的数据结构（我认为）。如果您在这样的结构中存储 50,000 个字符串，那么存储多少个字符串并不重要。更重要的是 长度 琴弦的。如果它们的长度大致相同，那么您可能永远不会看到查找速度变慢，因为搜索算法在运行时相对于您正在搜索的字符串的长度是线性的。即使对于红黑树或 AVL 树，搜索运行时间也更多地取决于要搜索的字符串的长度，而不是索引中元素的数量。但是，如果您选择使用哈希函数实现索引键，那么您现在会产生对字符串进行哈希处理的成本（将是 O(m)，m = 字符串长度）以及在索引中查找字符串的成本，这可能约为 O(log(n))，n = 索引中的元素数量。

编辑：我不是 .NET 专家。其他更有经验的人提出了另一种结构。我会相信他们的话而不是我的话。

编辑2：您的分析对于比较独特性有点偏离。如果您使用哈希结构或字典，那么由于我上面发布的推理，它不会是 O(n^2) 操作。如果您继续使用列表，那么您是正确的，它是 O(n^2) *（集合中字符串的最大长度），因为您每次都必须检查列表中的每个元素。