HashSet против производительности списка

Question

Понятно, что эффективность поиска общего класса HashSet<T> выше, чем общего класса List<T>. Просто сравните ключ на основе хеша с линейным подходом в классе List<T>.

Однако вычисление ключа хеша само по себе может занять несколько циклов ЦП, поэтому для небольшого количества элементов линейный поиск может стать реальной альтернативой HashSet<T>.

Мой вопрос: где безубыточность?

Чтобы упростить сценарий (и быть справедливым), давайте предположим, что класс List<T> использует метод Equals() элемента для идентификации элемента.

Answer 1

Зависит от того, что вы хэшируете. Если ваши ключи целые числа, вам, вероятно, не нужно много элементов, прежде чем HashSet станет быстрее. Если вы вводите ее в строку, она будет медленнее и зависит от входной строки.

Конечно, вы могли бы довольно легко поднять тест?

Answer 2

Зависит от множества факторов ... Реализация списка, архитектура ЦП, JVM, семантика цикла, сложность метода equals и т. Д. двоичные поиски на основе бита обходят линейные поиски, и оттуда разница только увеличивается.

Надеюсь, это поможет!