При обработке больших объемов данных я часто обнаруживаю, что делаю следующее:
HashSet<String> set = new HashSet<String> ();
//Adding elements to the set
ArrayList<String> list = new ArrayList<String> (set);
Что-то вроде "демпинга" содержимого набора в списке. Обычно я делаю это, так как элементы, которые я добавляю, часто содержат дубликаты, которые я хочу удалить, и это кажется простым способом их удалить.
Учитывая только эту цель (избегая дубликатов), я мог бы также написать:
ArrayList<String> list = new ArrayList<String> ();
// Processing here
if (! list.contains(element)) list.add(element);
//More processing here
И, следовательно, не нужно "сбрасывать" набор в список. Тем не менее, я бы выполнил небольшую проверку перед вставкой каждого элемента (который я также предполагаю, что HashSet)
Является ли какая-либо из двух возможностей более эффективной?
Набор даст намного лучшую производительность (O(n) против O(n^2) для списка), и это нормально, потому что избегать дубликатов является самой целью набора.
Содержит для HashSet O(1) по сравнению с O(n) для списка, поэтому вы никогда не должны использовать список, если вам часто нужно использовать contains.
ArrayList использует массив для хранения данных. ArrayList.contains будет иметь сложность O (n). Таким образом, по существу, поиск в массиве снова и снова будет иметь сложность O(n^2).
В то время как HashSet использует механизм хеширования для хранения элементов в своих соответствующих ведрах. Операция HashSet будет быстрее для длинного списка значений. Он достигнет элемента в O(1).
Если вам не нужен список, я бы просто использовал Set, и это естественная коллекция для использования, если порядок не имеет значения, и вы хотите игнорировать дубликаты.
Вы можете сделать так, что вам нужен список без дубликатов.
private Set<String> set = new HashSet<>();
private List<String> list = new ArrayList<>();
public void add(String str) {
if (set.add(str))
list.add(str);
}
Таким образом, список будет содержать только уникальные значения, первоначальный порядок вставки сохраняется и операция O (1).
Я сделал тест, поэтому, пожалуйста, проверьте результат:
Для пунктов SAME STRING в HashSet, TreeSet, ArrayList и LinkedList приведены результаты для
Основываясь на вышеприведенных результатах, нет большой разницы в использовании списка массивов против установленного. Возможно, вы можете попробовать изменить этот код и заменить String на свой Object и увидеть отличия...
public static void main(String[] args) {
Set<String> hashSet = new HashSet<>();
Set<String> treeSet = new TreeSet<>();
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
List<String> base = new ArrayList<>();
for(int i = 0; i<5000000; i++){
if(i%100000==0) System.out.print(".");
base.add(UUID.randomUUID().toString());
}
System.out.println("\nBase size : " + base.size());
String item = base.get(25000);
System.out.println("SEARCHED ITEM : " + item);
hashSet.addAll(base);
treeSet.addAll(base);
arrayList.addAll(base);
linkedList.addAll(base);
long ms = System.currentTimeMillis();
System.out.println("hashSet.contains(item) ? " + (hashSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
System.out.println("treeSet.contains(item) ? " + (treeSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
System.out.println("arrayList.contains(item) ? " + (arrayList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
System.out.println("linkedList.contains(item) ? " + (linkedList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
}
Вы можете добавить элементы в список. Затем, для дедуплирования -
HashSet<String> hs = new HashSet<>(); // new hashset
hs.addAll(list); // add all list elements to hashset (this is the dedup, since addAll works as a union, thus removing all duplicates)
list.clear(); // clear the list
list.addAll(hs); // add all hashset elements to the list
Если вам нужен набор с дедушкой, вы можете также использовать addAll() в другом наборе, чтобы он имел только уникальные значения.