O (1) поддерживается в поисках по хэш-сетам при использовании альтернативного компаратора?

Question

Если я определю свой собственный компаратор для универсального HashSet<T> в System.Collections.Generic, и его время выполнения равно O (1), будет ли время поиска хэш-таблицы все еще O (1)?

Я бы подумал, что нет, просто потому, что нет способа установить компаратор.

Answer 1

Причина, по которой время поиска обычного хэш-набора равно O (1), заключается в том, что он использует открытую адресацию для размещения объектов в массиве, так что это не изменится, даже если вы используете свой собственный компаратор.

Answer 2

В лучшем случае в него будет вставлена ​​амортизированная O (1) и поиск O (1).

В худшем случае в него будет вставлена ​​амортизированная O (n) и поиск O (n).

Хороший компаратор поможет сохранить реальный случай ближе к лучшему, чем худший, благодаря хорошему методу хеширования.

Плохой компаратор, ну будет плохо. (Напишите намеренно плохой компаратор, который возвращает одно и то же значение для каждого хеш-кода [допустимый, но бессмысленный], и вы сможете увидеть это поведение O (n)).

Хорошему компаратору может не повезти, но в большинстве случаев реальные случаи достаточно близки к O (1), поэтому мы можем думать о нем как о (1) и не быть направленными далеко.

Edit:

Пропустил немного о том, что "нет способа установить компаратор". Существует, HashSet имеет конструктор, который принимает один.