Каков эффективный и элегантный способ добавления одного элемента в неизменяемый набор?

У меня есть неизменяемый набор (отлитый как Set<Integer>), который потенциально содержит много элементов. Мне нужна коллекция, содержащая элементы из этого набора плюс один дополнительный элемент. У меня есть kludgy код на месте, чтобы скопировать набор, а затем добавить элемент, но я ищу правильный путь, который сохраняет все как можно эффективнее.

У меня есть Guava, хотя я не требую его использования.

Ответы

Ответ 1

Не уверен в производительности, но вы можете использовать Guava ImmutableSet.Builder:

import com.google.common.collect.ImmutableSet

// ...
Set<Integer> newSet = new ImmutableSet.Builder<Integer>()
                                .addAll(oldSet)
                                .add(3)
                                .build();

Конечно, вы также можете написать себе вспомогательный метод:

public static <T> Set<T> setWith(Set<T> old, T item) {
  return new ImmutableSet.Builder<T>().addAll(old).add(item).build();
}

// ...
Set<Integer> newSet = setWith(oldSet, 3);

Ответ 2

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

Ответ 3

У вас есть три варианта.

  • Используйте изменяемый набор.
  • Проверить, что элемент еще не присутствует, если не создать копию набора и добавить элемент.
  • Создайте набор оберток, который включает в себя предыдущий набор и элемент.

Иногда a BitSet является лучшим выбором, чем Set<Integer> в зависимости от распределения ваших значений.

Ответ 4

Вы можете рассмотреть Sets.union(). Строительство будет быстрее, но медленнее.

public static <T> Set<T> setWith(Set<T> old, T item) {
  return Sets.union(old, Collections.singleton(item);
}

(com.google.common.collect.Sets и java.util.Collections)

Ответ 5

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

Ответ 6

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

Для добавления элемента в дерево B + требуется O (log (n)) время и инкрементное распределение, а не O (n), когда вы получаете с ImmutableSet.builder().addAll(...).add(...).build(). Это означает, что построение набора из n добавочных добавок - O (n * log (n)), а не O (sqr (n)).

В этом ответе есть указатель на библиотеку jdbm, поэтому стоит посмотреть jdbm:jdbm.