C# Time complexity of Array[T].Contains(T item) vs HashSet<T>.Contains(T item)

Question

HashSet(T).Contains(T) (inherited from ICollection<T>.Contains(T)) has a time complexity of O(1).
So, I'm wondering what the complexity of a class member array containing integers would be as I strive to achieve O(1) and don't need the existence checks of HashSet(T).Add(T).

Since built-in types are not shown in the .NET reference source, I have no chance of finding found the array implementation of IList(T).Contains(T).

Any (further) reading material or reference would be very much appreciated.

Answer 1

You can see source code of Array with any reflector (maybe online too, didn't check). IList.Contains is just:

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

And Array.IndexOf calls Array.IndexOf<T>, which, after a bunch of consistency checks, redirects to

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

And that one finally does:

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

So just loops over array with average complexity O(N). Of course that was obvious from the beginning, but just to provide some more evidence.