Does calling IEnumerable.Cast<T>() changes the underlying type to something else, or the underlying type preserved?

Question

Say I have ISet<T> _set = new HashSet<T>();

Now if I do: _set.Cast<TInterface>().Contains(obj, comparer); (where T implements TInterface), do I loose the O(1) benefit of the HashSet<T>?

In other words - does .Cast<T>()ing changes the underlying type (HashSet<T> in this case) to something else, or the underlying type preserved?

Answer 1

Logically, a HashSet<T> uses an internal hash-table based on the hashing logic of the comparer that it was created with, so of course it's not possible to do an element-containment test on it with a different comparer and expect O(1) performance.

---

That said, let's look at things in a bit more detail for your specific scenario:

The Cast<T> method looks like this (from reference-source):

  public static IEnumerable<TResult> Cast<TResult>(this IEnumerable source) {
            IEnumerable<TResult> typedSource = source as IEnumerable<TResult>;
            if (typedSource != null) return typedSource;
            if (source == null) throw Error.ArgumentNull("source");
            return CastIterator<TResult>(source);
        }

As you can see, if the source implements IEnumerable<TResult> it just returns the source directly. Since IEnumerable<> is a covariant interface, this test will pass for your use case (assuming the concrete type implements the interface type) and the hash-set will be returned directly - a good thing as there's still hope of its internal hash-table being used.

However, the overload of Contains you are using looks like this:

 public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource> comparer)
        {
            if (comparer == null) comparer = EqualityComparer<TSource>.Default;
            if (source == null) throw Error.ArgumentNull("source");
            foreach (TSource element in source)
                if (comparer.Equals(element, value)) return true;
            return false;
        }

As you can see, it always loops through the collection to linear-search, which is O(n).

So the entire operation is going to be O(n) regardless.

Answer 2

_set.Cast<TInterface>() will return an IEnumerable<TInterface> so _set.Cast<TInterface>().Contains(obj, comparer); doesn't invokes HashSet.Contains, rather it invokes Enumerable.Contains extension method.

So obviously you don't get O(1) operation anymore.

If you need O(1) you again need to create a HashSet out of it.

   var newSet = new HashSet(_set.Cast<TInterface>(),comparer);
   newSet.Contains();

Answer 3

The Cast method returns an IEnumerable so the Contains method will operate on the IEnumerable rather than the HashSet. So I think you'd loose the benefit of HashSet. Why don't you do the cast in the compared instead?