Java HashSet vs Array Performance

Question

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

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

Answer 1

В зависимости от ваших данных;

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

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

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

Я считаю Набор более гибким.

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

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

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

вам нужен список или Set? Они предназначены для разных целей: списки предоставляют вам индексированный доступ, а итерация - в порядке индекса. В то время как 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).

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