C#时间复杂度Array [T] .Contains(T item)vs HashSet <T> .Contains(T item)

Question

HashSet(T).Contains(T)(继承自ICollection<T>.Contains(T))的时间复杂度为O(1).
所以,我想知道含有整数类成员阵列的复杂性将是什么,因为我努力实现O(1)和不需要存在检查的HashSet(T).Add(T).

由于内置类型是不 在.NET参考源中显示,I 没有机会找到发现了数组的实现IList(T).Contains(T).

任何(进一步)阅读材料或参考将非常感激.

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

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) 操作。如果您没有很多查找要做，那就没有实际意义。

关于此构造函数的文档中的注释：

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