Какова сложность времени поиска HashSet(IEqualityComparer)?

В C#.NET мне нравится использовать HashSet из-за их предполагаемого времени O(1) сложность поиска. Если у меня есть большой набор данных, которые будут запрошены, я часто предпочитаю использовать HashSet вместо списка, поскольку на этот раз это сложно.

Что меня смущает, так это конструктор для HashSet, который принимает IEqualityComparer в качестве аргумента:

http://msdn.microsoft.com/en-us/library/bb359100.aspx

В ссылке выше, в примечаниях отмечается, что «конструктор - это операция O (1)», но если это так, мне любопытно, выполняется ли поиск по-прежнему O (1).

В частности, мне кажется, что если бы я написал компаратор для передачи в конструктор HashSet, всякий раз, когда я выполняю поиск, код компаратора должен был бы выполняться для каждого ключа, чтобы проверить, чтобы увидеть если бы было совпадение. Это будет не O(1), а O(n).

Создает ли реализация внутренне таблицу поиска по мере добавления элементов в коллекцию?

В общем, как я могу получить информацию о сложности структур данных .NET?