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

У меня есть набор объектов, которые гарантированно отличаются друг от друга (в частности, индексируются уникальным идентификатором целочисленного числа). Я также точно знаю, сколько из них (и число не изменится), и задалось вопросом, может ли Array иметь значительное преимущество по сравнению с HashSet для хранения/извлечения указанных элементов.

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

Ответ 1

Зависит от ваших данных;

HashSet предоставляет метод O(1) contains(), но не сохраняет порядок.

ArrayList содержит() is O(n), но вы можете управлять порядком записей.

Array, если вам нужно вставить что-либо между ними, наихудший случай может быть O (n), так как вам придется переместить данные и освободить место для вставки. В Set вы можете напрямую использовать SortedSet which too has O(n) too but with flexible operations.

Я считаю, что Set более гибкий.

Ответ 2

Для корпоративного программного обеспечения Масштабируемый, поддерживаемый и чистый код намного лучше. Поэтому я иду на HashSet.

Ответ 3

Выбор зависит от того, что вы хотите с ним сделать.

Если это то, что упоминается в вашем вопросе:

У меня есть коллекция объектов, которые гарантированно различаются (в частности, индексируются с помощью уникального целочисленного ID). Я также точно знаю , сколько из них есть

Если это то, что вам нужно сделать, вам не нужны ни те, ни другие. Существует метод size() в Collection, для которого вы можете получить его размер, что означает , сколько из них есть в коллекции.

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

Во-первых, я считаю, что есть справедливое сравнение, вы должны рассмотреть возможность использования ArrayList вместо Array, для которого вам не нужно иметь дело с перераспределением.

Затем он становится выбором ArrayList vs HashSet, который довольно прямолинейный:

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

После того, как вы решили использовать List или Set, это выбор реализации List/Set, обычно для списков, вы выбираете ArrayList и LinkedList, тогда как для Sets вы выбираете между HashSet и TreeSet.

Все зависит от того, что вы хотели бы сделать с этой коллекцией данных. Они выполняют разные действия при разных действиях.

Например, индексированный доступ в ArrayList равен O (1), в HashSet (хотя и не значимый) O (n) (только для вашего интереса, в LinkedList есть O (n), в TreeSet есть O (nlogn ))

Для добавления нового элемента, как ArrayList, так и HashSet - операция O (1). Вставка в середине - это O (n) для ArrayList, хотя это не имеет смысла в HashSet. Оба будут страдать от перераспределения, и обе они нуждаются в O (n) для перераспределения (HashSet обычно медленнее в перераспределении, поскольку он включает вычисление хеша для каждого элемента снова).

Чтобы определить, существует ли в коллекции определенный элемент, ArrayList - это O (n), а HashSet - O (1).

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

Ответ 4

теоретически, и в качестве учебного пособия SCJP6 говорится: D

массивы быстрее, чем коллекции, и, как сказано, большинство коллекций зависят в основном от массивов (Карты не считаются Collection, но они включены в структуру Collections)

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

Ответ 5

Похоже, вам понадобится HashMap, который отображает id для подсчета. В частности,

HashMap<Integer,Integer> counts=new HashMap<Integer,Integer>();
counts.put(uniqueID,counts.get(uniqueID)+1);

Таким образом, вы получаете амортизацию O (1), добавляет, содержит и извлекает. По сути, массив с уникальным идентификатором, связанным с каждым объектом, является HashMap. Используя HashMap, вы получаете дополнительный бонус от необходимости управлять размером массива, не имея необходимости сопоставлять ключи с индексом массива самостоятельно и постоянным временем доступа.