Array[T].Contains(T item) 与 HashSet.Contains(T item) 的 C# 时间复杂度

Question

HashSet(T).Contains(T) (继承自 ICollection<T>.Contains(T) )的时间复杂度为 O(1)。
所以，我想知道包含整数的类成员数组的复杂性是多少，因为我努力实现 O(1) 并且不需要 existence checks的 HashSet(T).Add(T) .

自 built-in types 没有显示在 .NET 引用源中，我没有机会找到找到了 IList(T).Contains(T) 的数组实现.

任何(进一步的)阅读 Material 或引用将不胜感激。

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) .当然，这从一开始就很明显，但只是为了提供更多证据。