Эффективная структура данных для хранения/добавления/удаления повторяющихся элементов

У меня есть 2 источника, из которых я читаю данные. Эти данные могут быть дубликатами, и мне нужно обнаружить эти дубликаты, вычитая 2 коллекции друг из друга. В настоящее время я использую List<Map<String, String> duplList, поэтому, когда я вставляю повторяющиеся значения:

Map<String, String> map1 = new HashMap();
map1.put("1", "1");
map1.put("1", "1");
map1.put("1", "1");
duplList.add(map1);

Map<String, String> map2 = new HashMap();
map2.put("1", "1");
map2.put("1", "1");
duplList.add(map2);

И позже вычтите их:

Collection diff1 = CollectionUtils.subtract(map1, map2);
Collection diff2 = CollectionUtils.subtract(map2, map1);

Я получаю объект, который содержит разницу между map1 и map2.
Хотя это работает, мне это кажется не совсем эффективным (поскольку выполняется за время O(n)).

Мне было интересно если есть более эффективный способ добавления и вычитания данных в более эффективную структуру данных.


java data-structures memory-efficient
person ocp1000    schedule 24.04.2016    source источник
comment
Как определить дубликаты? Повторяющиеся ключи или пары ключ-значение? Кроме того, как вы разрешаете конфликты после того, как были найдены дубликаты?   -  person Sergei Lebedev    schedule 24.04.2016
comment
Если я вас правильно понимаю, вы можете добавить дубликаты объектов в Set, используя метод add. Если вызов add с объектом возвращает false, то объект является дубликатом, поэтому сохраните его в отдельной коллекции.   -  person Ilya    schedule 24.04.2016
comment
@SergeiLebedev Дубликаты определяются как одинаковые пары «ключ-значение», поэтому 1->1 является дубликатом, а 1->2 — нет.   -  person ocp1000    schedule 24.04.2016
comment
Если под разницей вы имеете в виду, что вам нужен список элементов, которые не появляются в оба наборах, то лучшее, что вы можете сделать, это O(n). Некоторые структуры данных будут более эффективными, чем другие, что уменьшит постоянные факторы, но асимптотически вы не можете добиться большего, чем O (n).   -  person Jim Mischel    schedule 25.04.2016

Ответы (1)


arrow_upward
0
arrow_downward

Если вы просто хотите, чтобы ваши данные находились в несортированной коллекции, вы можете использовать HashSet, если вы хотите, чтобы они были отсортированы, вы можете использовать TreeSet. Однако для TreeSet требуется класс, который реализует Comparable — если вы просто работаете со строками или целыми числами, все должно быть в порядке. Дополнительную информацию можно найти в Документация по Java: Set

person lukstru    schedule 24.04.2016
comment
Я не упомянул, что мои данные должны быть в формате пары ключ-значение. Будет ли более эффективно хранить его в Set‹Map‹String, String››, чем в List‹Map‹String, String››? - person ocp1000; 24.04.2016