Какую коллекцию я должен использовать в этом случае?

Question

В этом случае, мне нужно сохранить группу элементов в коллекции x. Я не хочу вставлять элемент в x, если он уже существует (без дубликатов). Мне также не нужен порядок вставки. Размер x сильно различается (может быть очень маленьким на < 10 предметов или до десяти тысяч).

Хотя никакие дубликаты и никакие пункты заказа не используют Set, мне нужно быстро и быстро выполнять все пункты после того, как я построил x и выполнить операции, используя их (но не меняя их). Будет ли Set по-прежнему лучшим вариантом?

Я был бы признателен за любое направление - стоит ли дороже проверить, содержит ли List элемент перед каждой вставкой (во избежание дублирования) или для перебора членов Set? Любые советы по передовым методам/эффективности и стоимости будут действительно оценены, спасибо.

Answer 1

Это значительно дороже, если у вас есть элемент List.

Перебор Set немного медленнее, чем итерация по List, но не массово, так и только постоянным множителем, в то время как проверка удержания элемента в List стоит линейное время на каждый элемент и делает все это квадратичная ,

Answer 2

Использование набора для построения x после построения x u может просто скопировать содержимое в массив или любой другой тип, чтобы улучшить временную сложность за счет сложности пространства.

Answer 3

Если вам нужно быстро проверить, существует ли элемент, HashSet - это, безусловно, лучший выбор, так как он использует HashMap, поэтому каждый поиск - O (1). Хотя список для этого поиска очень дорог, так как он проверяет все элементы один за другим.

И когда вам нужно перебрать все элементы, это не имеет никакого значения при использовании List и Set.

Стоит отметить, что HashSet будет использовать больше памяти, но 10s тысяч не должны создавать проблемы.

Итак, HashSet является явным победителем для вашего дела.

Answer 4

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

Требуется O(n) для поиска, как правило, следует избегать в этом случае.

Answer 5

Предлагаю вставить данные на карту, чтобы избежать дублирования элементов, а затем преобразовать карту в список.

Если вы используете Java 8 вы можете сделать что-то вроде этого

List<Object> result = map.entrySet().stream() 
      .map(x -> x.getKey()) 
      .collect(Collectors.toList());