Does Linq Contains() check for HashSet?

Question

Sometimes a HashSet is exposed through a property as an IEnumerable.

It is well known that for enumerable.Count() the code checks if it is a collection, so it doesn't enumerate the whole list, but takes a shortcut.

Is there any similar check for using the Linq version of enumerable.Contains(x) and HashSets?

The shortcut for `Count()` is a property. How would a property properly return a boolean for a dynamic expression? — Travis J, Aug 12 '14 at 22:25
why don't you look at yourself: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs — Selman Genç, Aug 12 '14 at 22:25
what do you mean exactly?....if calling contains(x) in a query will only check part of the list? — terrybozzio, Aug 12 '14 at 22:26
@TravisJ He means that `Enumerable.Count()` checks to see if the object is of type `ICollection` and if so returns `ICollection.Count` as an optimization. If it's not it has to enumerate the enumerable in order to count the items. — cdhowie, Aug 12 '14 at 22:26
@cdhowie - Yes I understood that aspect, but how does that relate to `Contains`? — Travis J, Aug 12 '14 at 22:27
It appears that at least [Mono does do this](https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Linq/Enumerable.cs#L605). (Set types should implement `ICollection`, and so this would call the set's implementation of `ICollection.Contains()`.) I would not be surprised if MS.NET did this too. — cdhowie, Aug 12 '14 at 22:27
@TravisJ `ICollection` also has a `Contains` method that can implement specialized logic, for example in the case of a `HashSet` it can perform the test in average O(1) time, versus enumerating the elements until a match is found. — cdhowie, Aug 12 '14 at 22:28
I wouldn't think it does that because HashSet is a collection of unique objects, so it needs to know what objects already exist in the collection. I would think that Contains would check the map of already inserted objects. Best bet is to check the reference source. — Maurice Reeves, Aug 12 '14 at 22:28
@MauriceReeves I can't make heads or tails of your statements. — cdhowie, Aug 12 '14 at 22:29
It's alright, per the answer below, my supposition was wrong. What I was trying to say was that HashSet is a collection of unique objects, so I would have guessed that HashSet had overloaded Contains and not used the method from ICollection. — Maurice Reeves, Aug 12 '14 at 22:40

score 18 · Accepted Answer · answered Aug 12 '14 at 22:27

18

From the reference source, yes it does, though not directly:

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value) {
    ICollection<TSource> collection = source as ICollection<TSource>;
    if (collection != null) return collection.Contains(value);
    return Contains<TSource>(source, value, null);
}

If the source enumerable implements ICollection<T> (and HashSet<T> does), then it uses the collection's Contains method.

answered Aug 12 '14 at 22:27

p.s.w.g

146,324
30
291
331

2

+1 but I would point out that it *does not* check for `HashSet` *specifically* (as that is the question that was asked) but that it will check for `ICollection`, and therefore accomplish the same thing without needing to have specialized knowledge of `HashSet`. – cdhowie Aug 12 '14 at 22:30

score 1 · Answer 2 · answered Aug 13 '14 at 02:42

1

Note also it is documented to look for ICollection<T> (see Remarks).

answered Aug 13 '14 at 02:42

Mark Hurd

10,665
10
68
101

Does Linq Contains() check for HashSet?

2 Answers2

Linked