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

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

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

12 голосов | спросил donnyton 10 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 10 Sep 2013 00:55:24 +0400 2013, 00:55:24

5 ответов


0

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

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

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

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

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

ответил JNL 10 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 10 Sep 2013 00:59:30 +0400 2013, 00:59:30
0

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

ответил auhuman 10 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 10 Sep 2013 01:39:47 +0400 2013, 01:39:47
0

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

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

  

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

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

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

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

Тогда он стал выбором ArrayList vs HashSet, что довольно просто:

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

После того, как вы приняли решение использовать List или Set, тогда это выбор реализации List /Set, обычно для Lists вы выбираете из 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).

Вы по-прежнему можете выполнять множество операций, поэтому бессмысленно обсуждать вопросы производительности, не зная, что вы хотите сделать.

ответил Adrian Shum 18 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 18 Sep 2013 11:44:08 +0400 2013, 11:44:08
0

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

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

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

ответил Ahmed Adel Ismail 10 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 10 Sep 2013 01:43:37 +0400 2013, 01:43:37
0

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

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

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

ответил anguyen 18 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 18 Sep 2013 10:19:59 +0400 2013, 10:19:59

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132