C# 检查值的最佳方法是多次存在于列表中

Question

我有一个整数列表，我想多次知道一个值存在于我的列表中。

执行此操作的最佳方法是什么？

使用 LookUp 或 dictionary 或 HashMap 或...捕获数据？

例子:

List<int> samples = {5,4,6,2,1}
// if(2 exist in samples) do something ...
// if(3 exist in samples) do something ...
// if(5 exist in samples) do something ...
// if(8 exist in samples) do something ...
// if(13 exist in samples) do something ...
// if ....

Answer 1

您可以将它们存储在 HashSet 中并检查值是否存在 O(1) :

var unique = new HashSet<int>(){ 5,4,6,2,1};
var hasValue = unique.Contains(1);

然后检查:

if (unique.Contains(2)) 
    // do something ...

此外，HashSet<T>防止存储重复项，因此速度非常快。

更新:

List<T>将使用 O(N) 进行搜索。为什么？因为 Big O Notation 应该考虑时间复杂度的最坏情况。假设我们有以下列表:

var numbers = new List<int> { 5, 4, 6, 2, 1 };

我们想找到号码1 .所以Contains() List<T>的方法|必须遍历整个数组，直到找到数字 1 .所以我们有 O(N) .

LinkedList<T>将使用 O(N) 进行搜索。为什么？原因同List<T> .然而，LinkedList<T>引擎盖下没有数组，它有一个类，该类具有指向下一个元素的指针，下一个元素具有指向下一个元素的指针，依此类推。我们必须遍历所有元素才能找到一个项目。

HashSet<T>将使用 O(1) 进行搜索。为什么？原因是HashSet<T>引擎盖下不会遍历数组。它将运行内部方法 InternalGetHashCode它返回数组中数字的位置。 You can see the source code here.

此外，关于 How can hashset.contains be O(1) with this implementation? 有一个很好的回答