调用IEnumerable.Cast <T>()会将基础类型更改为其他类型,还是保留基础类型？

Question

说我有 ISet<T> _set = new HashSet<T>();

现在,如果我这样做:( _set.Cast<TInterface>().Contains(obj, comparer);哪里有T工具TInterface),我是否会放弃它的O(1)好处HashSet<T>？

换句话说 - 是否.Cast<T>()将基础类型(HashSet<T>在本例中)更改为其他类型,或保留基础类型？

Answer 1

逻辑上,a HashSet<T>使用基于其创建的比较器的哈希逻辑的内部哈希表,因此当然不可能使用不同的比较器对其进行元素包含测试并期望O(1)性能.

也就是说,让我们根据您的具体情况更详细地看一下事情:

该Cast<T>方法看起来像这样(来自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);
        }

如您所见,如果源实现IEnumerable<TResult>它只是直接返回源.由于IEnumerable<>是一个协变接口,这个测试将通过您的用例(假设具体类型实现接口类型)并且哈希集将直接返回 - 这是一件好事,因为仍然希望使用其内部哈希表.

但是,您使用的Contains的重载看起来像这样:

 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;
        }

正如您所看到的,它总是在集合中循环到线性搜索,即O(n).

所以无论如何整个操作都是O(n).