Как работают HashSets в Java?

Ответ 1

Во-первых, HashSet, в отличие от ArrayList является Set: он не может содержать дубликаты, а ArrayList может - поэтому они построены для разных целей. Он также не гарантирует упорядочение - опять же, в отличие от списка.

Второй - a HashSet построен на структуре данных хеш-таблицы, которая позволяет O(1) искать время для элемента.

Обратите внимание, что много раз < <20 > медленнее, тогда ArrayList - если вы хотите итерации на элементах, например, обычно делаете это в ArrayList будет быстрее, чем в HashSet [из-за плохой производительности кеша хэш, среди прочих причин]

Ответ 2

A HashSet на самом деле a HashMap, где значение всегда одно и то же.

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

HashSet просто содержит ключи, поэтому .contains(..) - O(1). Это и remove(..) являются единственными операциями a HashSet быстрее, чем ArrayList (что является O (n)). Итерация такая же, добавление одно и то же.

Ответ 3

Это две разные структуры данных.

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

Аррайалист также работает O(1) для доступа, так как он также поддерживается массивом. Но только для случайного доступа и вставки.

поиск хотя есть O(N) Работа для ArrayList, так как вы должны искать через все elemements в списке, чтобы добраться до значения в отличие от HashSet, где вы просто преобразовать ключ и доступ к массиву. Поиск в HashSet равен O(1)

Ответ 4

На самом деле, например, повторение и добавление в ArrayList происходит быстрее.

И черт возьми, вы даже не можете сортировать HashSet.

Но самым быстрым из всех является NoOp. Нет ничего просто удаленно так же быстро, как NoOp. Конечно, это не так много, NoOp. Но это действительно быстро!

Вам нужно быть более точным в том, что вы считаете "быстрее, чем".