我有一个很大的整数列表，它们发送到我的网络服务。我们的业务规则规定这些值必须是唯一的。找出是否有任何重复项的最有效方法是什么？我不需要知道这些值，我只需要知道其中 2 个值是否相等。
起初我在考虑使用整数的通用列表和 list.Exists() 方法，但这是 O(n);
然后我在考虑使用 Dictionary 和 ContainsKey 方法。但是，我只需要键，不需要值。我认为这也是一个线性搜索。
是否有更好的数据类型可用于在列表中查找唯一性？还是我坚持线性搜索？
问问题
236 次
5 回答
15
使用HashSet<T>：
HashSet 类提供高性能的集合操作。集合是不包含重复元素且其元素没有特定顺序的集合
HashSet<T>甚至公开了一个接受IEnumerable<T>. 通过将您传递List<T>给HashSet<T>'s构造函数，您最终将获得对 new 的引用，该引用HashSet<T>将包含与原始List<T>.
于 2009-08-21T20:30:11.063 回答
1
听起来像是Hashset的工作......
于 2009-08-21T20:30:14.467 回答
0
如果您使用的是框架 3.5，则可以使用该HashSet集合。
否则最好的选择是Dictionary. 每个项目的价值都会被浪费，但这会给你最好的表现。
如果您在将项目添加到 HashSet/Dictionary 时检查重复项，而不是事后对其进行计数，那么在存在重复项的情况下，您将获得比 O(n) 更好的性能，因为您不必在找到第一个重复项后继续查找.
于 2009-08-21T20:32:41.090 回答
0
如果数字集是稀疏的，那么正如其他人建议的那样，使用 HashSet。
但是，如果这组数字大部分是按顺序排列的，偶尔会有间隙，那么如果将数字集存储为一个排序数组或 begin,end 对的二叉树会更好。然后，您可以搜索以找到具有小于搜索键的最大开始值的对，并与该对的结束值进行比较以查看它是否存在于集合中。
于 2009-08-21T21:40:52.513 回答
0
怎么办：
list.Distinct().Count() != list.Count()
我想知道这个的表现。我认为它和 O(n) 一样好，但代码更少并且仍然易于阅读。
于 2009-08-22T16:24:14.670 回答