Вставка коллекции Java: Set vs. List

Question

Я думаю о наполнении коллекции большим количеством уникальных предметов. Какова стоимость вставки в Set (скажем, HashSet) по сравнению со списком (скажем, ArrayList)?

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

Answer 1

Не существует «удаления дубликатов», такого как сравнение со всеми существующими элементами.Если вы вставляете в хэш-набор, это действительно словарь элементов по хэш-коду.Там нет дублирования проверки, если нет уже элементов с таким же хэш-кодом.Учитывая разумную (хорошо распределенную) хеш-функцию, это не так уж и плохо.

Как заметил Уилл, из-за структуры словаря HashSet, вероятно, немного медленнее, чем ArrayList (если вы не хотитевставить «между» существующими элементами).Это также немного больше.Я не уверен, что это существенная разница.

Answer 2

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

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

Какой тип списка?
Кроме того, подумайте, какой список использовать. LinkedLists быстрее при добавлении, удалении элементов.

ArrayLists быстрее при произвольном доступе (for циклы и т. Д.), Но это можно обойти, используя Iterator LinkedList. ArrayLists на намного быстрее в: list.toArray().

Answer 3

Вы правы: заданные структуры по своей природе более сложны для распознавания и устранения дубликатов.Важность этих накладных расходов для вашего случая должна быть проверена с помощью эталонного теста.

Еще одним фактором является использование памяти.Если ваши объекты очень маленькие, накладные расходы памяти, вносимые заданной структурой, могут быть значительными.В самом крайнем случае (TreeSet<Integer> против ArrayList<Integer>) для заданной структуры может потребоваться более чем в 10 раз больше памяти.

Answer 4

Если целью является уникальность элементов, вы должны использовать реализацию интерфейса java.util.Set .Класс java.util.HashSet и java.util.LinkedHashSet имеет O ( alpha ) (близкий к O (1) в лучшем случае) сложности длявставка, удаление и содержит проверку.

ArrayList имеют O ( n ) для объекта (не индекса) содержит проверку (вы должны прокрутить весь список) и вставку (есливставка не в конце списка, вам нужно сдвинуть весь массив подчеркивания).

Вы можете использовать LinkedHashSet, который сохраняет порядок вставки и имеет такую ​​же потенциальность, как HashSet (занимает тольконемного больше памяти).

Answer 5

Список Java:

Если у вас нет такого требования, что вы должны хранить дубликаты или нет. Тогда вы можете использовать список вместо Set.

Список - это интерфейс в среде Collection. Что расширяет интерфейс коллекции. и ArrayList, LinkedList является реализацией интерфейса List.

Когда использовать ArrayList или LinkedList

ArrayList: Если у вас есть такое требование, чтобы в вашем приложении в основном работали с данными. Тогда вы должны пойти на ArrayList. потому что ArrayList реализует интерфейс RtandomAccess, который является интерфейсом маркера. Из-за интерфейса Marker ArrayList имеет возможность доступа к данным за O (1) раз. и вы можете использовать ArrayList поверх LinkedList, где вы хотите получать данные в соответствии с порядком вставки.

LinkedList: Если у вас есть такое требование, что вашей основной работой является вставка или удаление. Тогда вы должны использовать LinkedList поверх ArrayList. потому что в LinkedList вставка и удаление происходят за время O (1), тогда как в ArrayList это время O (n).

Java Set:

Если в вашем заявлении есть требование, что вам не нужны дубликаты. Тогда вам следует перейти на Set вместо List. Потому что Set не хранит дубликаты. Потому что Сет работает по принципу Хеширования. Если мы добавим объект в Set, то сначала он проверяет hashCode объекта в корзине, если он находит любой hashCode, присутствующий в нем, тогда он не будет добавлять этот объект.

Answer 6

Я не думаю, что вы можете судить просто о стоимости создания коллекции. Другие вещи, которые вы должны принять во внимание:

• Заказан ли входной набор данных? Есть ли требование, чтобы структура выходных данных сохраняла порядок вставки?
• Существует ли требование, чтобы структура выходных данных была упорядочена (или переупорядочена) на основе значений элементов?
• Будет ли впоследствии изменена структура выходных данных? Как?
• Требуется ли, чтобы выходная структура данных была без дубликатов, если впоследствии добавляются другие элементы?
• Знаете ли вы, сколько элементов может находиться во входном наборе данных?
• Можете ли вы измерить размер входного набора данных? (Или это предоставляется через итератор?)
• Имеет ли значение использование пространства?

Все это может повлиять на ваш выбор структуры данных.

Answer 7

Вы должны сравнить конкретные реализации (например, HashSet с ArrayList), потому что абстрактные интерфейсы Set / List на самом деле ничего не говорят вам о производительности.

Вставка вHashSet - довольно дешевая операция, если hashCode() объекта, который нужно вставить, вменяемый.Он все равно будет немного медленнее, чем ArrayList, потому что его вставка - это простая вставка в массив (при условии, что вы вставляете в конец, и все еще остается свободное место; я не учитываю изменение размера внутреннего массива, потому что применяется та же самая стоимость)до HashSet)