У меня есть набор объектов, которые гарантированно отличаются друг от друга (в частности, индексируются уникальным идентификатором целочисленного числа). Я также точно знаю, сколько из них (и число не изменится), и задалось вопросом, может ли Array иметь значительное преимущество по сравнению с HashSet для хранения/извлечения указанных элементов.
На бумаге Array гарантирует постоянную вставку времени (поскольку я знаю размер раньше времени) и поиск, но код для HashSet выглядит намного чище и добавляет некоторую гибкость, поэтому мне интересно, теряю ли я что- разумно используя его, по крайней мере, теоретически.
Зависит от ваших данных;
HashSet предоставляет метод O(1) contains(), но не сохраняет порядок.
ArrayList содержит() is O(n), но вы можете управлять порядком записей.
Array, если вам нужно вставить что-либо между ними, наихудший случай может быть O (n), так как вам придется переместить данные и освободить место для вставки. В Set вы можете напрямую использовать SortedSet which too has O(n) too but with flexible operations.
Я считаю, что Set более гибкий.
Для корпоративного программного обеспечения Масштабируемый, поддерживаемый и чистый код намного лучше. Поэтому я иду на HashSet.
Выбор зависит от того, что вы хотите с ним сделать.
Если это то, что упоминается в вашем вопросе:
У меня есть коллекция объектов, которые гарантированно различаются (в частности, индексируются с помощью уникального целочисленного 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).
Есть еще много операций, которые вы можете сделать, поэтому совершенно бессмысленно обсуждать производительность, не зная, что вы хотите сделать.
теоретически, и в качестве учебного пособия SCJP6 говорится: D
массивы быстрее, чем коллекции, и, как сказано, большинство коллекций зависят в основном от массивов (Карты не считаются Collection, но они включены в структуру Collections)
если вы гарантируете, что размер ваших элементов не изменится, зачем застревать в объектах, построенных на объектах (коллекции, созданные на массивах), в то время как вы можете напрямую использовать корневые объекты (массивы)
Похоже, вам понадобится HashMap, который отображает id для подсчета. В частности,
HashMap<Integer,Integer> counts=new HashMap<Integer,Integer>();
counts.put(uniqueID,counts.get(uniqueID)+1);
Таким образом, вы получаете амортизацию O (1), добавляет, содержит и извлекает. По сути, массив с уникальным идентификатором, связанным с каждым объектом, является HashMap. Используя HashMap, вы получаете дополнительный бонус от необходимости управлять размером массива, не имея необходимости сопоставлять ключи с индексом массива самостоятельно и постоянным временем доступа.