Почему мы используем ArrayList, когда мы могли бы использовать Set для добавления уникальных значений?

Question

Я нашел эффективный код для добавления уникальных элементов, используя следующий подход:

int[] values = { -5, -3, -1, 0, 3, 6 };

List<Integer> list=new ArrayList<Integer>();

for(int val : values)

{

   if(!list.contains(val))

   list.add(val);

}

Я мог бы выполнить ту же работу, используя HashSet вместо ArrayList.Это помогло бы мне, не беспокоясь о том, что значение уже существует в списке.Почему использование Hashset неэффективный подход?

Answer 1

A HashSet не реализует интерфейс List.И значения в Set не индексируются.Мы не можем получить значение из Set.

Так что, если вам просто нужно хранилище для уникальных значений, вы можете смело использовать реализацию Set.Если вам нужно сохранить порядок вставки или если вам нужны какие-либо другие функции List реализаций и уникальности, то используйте метод из вашего вопроса: украсьте существующую реализацию List и добавьте функциональность, чтобы отклонять дубликаты.

Вы спрашивали об эффективности: ArrayList поддерживается массивом и довольно быстро.Но временная сложность для contains() - это O (n) - для итерации нам нужно рассмотреть каждый элемент в худшем случае.

HashSet более или менее является полным декоратором HashMapнемного тяжелее по сравнению с array.Но сложность времени для contains равна O (1) - проверка выполняется в постоянное время, независимо от того, сколько элементов находится внутри карты.

Если вы просто хотите выполнить итерацию - специализированная реализация Listдолжно быть немного быстрее - оба имеют временную сложность O (n) для итерации (не удивительно), но чтение из массива легче, чем чтение с карты.

Answer 2

На самом деле, HashSet - это намного лучший подход, чем ArrayList. Ваш код работает в O (n) для HashSet и O (n²) для ArrayList.

Но следует помнить одну вещь: элементы в HashSet не хранятся в каком-либо определенном порядке. Если вы хотите сохранить порядок и с быстрым поиском, используйте LinkedHashSet. (Однако все имеет свою стоимость; в этом случае LinkedHashSet использует больше памяти, чем HashSet.)

Answer 3

Это так.Предпосылка для вашего вопроса ошибочна.

Используйте гуава , и это проще:

Set set = Sets.newTreeSet( values ); // или HashSet