C#中Array[T].Contains(T item)和HashSet[T].Contains(T item)的时间复杂度对比

Question

HashSet(T).Contains(T)（从ICollection<T>.Contains(T)继承）的时间复杂度为O(1)。
因此，我想知道一个包含整数的类成员数组的复杂度是什么，因为我想要实现O(1)，并且不需要HashSet(T).Add(T)的存在检查。

由于内置类型在.NET参考源中未显示，我没有机会找到找到了IList(T).Contains(T)的数组实现。

任何（进一步）阅读材料或参考资料将非常感激。

- Noel Widmer

---

顺便说一句，Contains 是在 ICollection<T> 上，而不是 IList<T>。 - James Thorpe

@JamesThorpe 真的吗？https://msdn.microsoft.com/de-de/library/bb336401(v=vs.110).aspx - Noel Widmer

是的。IList<T> 继承自 ICollection<T>。 - James Thorpe

@JamesThorpe 更有可能他是想问 List<T>，而不是 ICollection<T>。 - piojo

@piojo 即使对于 List<T>，Contains 方法仍然定义在 ICollection<T> 接口上 - 我只是简短地评论了问题中的粗体文本。 - James Thorpe

Answer 1

你可以使用任何反编译工具（甚至可能是在线的，没有验证）来查看Array的源代码。而IList.Contains只是：

Array.IndexOf(this,value) >= this.GetLowerBound(0);

而 Array.IndexOf 调用 Array.IndexOf<T>，在进行一系列的一致性检查之后，重定向到

EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count)

并且那个最终做到了：

int num = startIndex + count;
for (int index = startIndex; index < num; ++index)
{
  if (this.Equals(array[index], value))
      return index;
}
return -1;

因此，只需使用平均复杂度为O(N)的循环遍历数组即可。当然，这一点从一开始就是显而易见的，但只是为了提供更多证据。

- Evk

Answer 2

.Net Framework的数组源代码（直到v4.8）可以在参考源中找到，并且可以使用ILSpy进行反编译。

在参考源中，您可以在第2753行和2809行找到：

// -----------------------------------------------------------
// ------- Implement ICollection<T> interface methods --------
// -----------------------------------------------------------

...

[SecuritySafeCritical]
bool Contains<T>(T value) {
    //! Warning: "this" is an array, not an SZArrayHelper. See comments above
    //! or you may introduce a security hole!
    T[] _this = JitHelpers.UnsafeCast<T[]>(this);
    return Array.IndexOf(_this, value) != -1;
}

而 IndexOf 最终会使用这个IndexOf，这是一个O(n)的算法。

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int endIndex = startIndex + count;
    for (int i = startIndex; i < endIndex; i++) {
        if (Equals(array[i], value)) return i;
    }
    return -1;
}

这些方法都在同一个源文件中的一个特殊类SZArrayHelper中，正如第2721行所解释的那样，这就是您正在寻找的实现。

// This class is needed to allow an SZ array of type T[] to expose IList<T>,
// IList<T.BaseType>, etc., etc. all the way up to IList<Object>. When the following call is
// made:
//
//   ((IList<T>) (new U[n])).SomeIListMethod()
//
// the interface stub dispatcher treats this as a special case, loads up SZArrayHelper,
// finds the corresponding generic method (matched simply by method name), instantiates
// it for type <T> and executes it.

关于实现O(1)的时间复杂度，你应该转换为HashSet：

var lookupHashSet = new HashSet<T>(yourArray);
...
var hasValue = lookupHashSet.Contains(testValue);

当然，这种转换是O(n)的操作。如果你没有很多查找要做，那么它就是无意义的。

请注意，从文档中可以得知这个构造函数：

如果集合包含重复项，则集合将包含每个唯一元素的一个。不会抛出任何异常。因此，结果集的大小与集合的大小不相同。

- Frédéric

---

我在初始化期间添加了所有项目，因此根本不需要使用数组。但是知道它支持构造函数还是很好的 :) - Noel Widmer

Answer 3

你实际上可以看到 List<T> 的源代码，但你需要在网上查找。这里是一个来源。

任何纯列表/数组的 bool Contains(T item) 检查都是 O(N) 复杂度，因为每个元素都需要被检查。.NET 也不例外。（如果你设计了一种数据结构，它表现为一个列表，但也包含了一个布隆过滤器辅助数据结构，那就是另一回事了。）

- piojo