HashSet vs ArrayList содержит производительность

При обработке больших объемов данных я часто обнаруживаю, что делаю следующее:

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)

Является ли какая-либо из двух возможностей более эффективной?

Ответ 1

Набор даст намного лучшую производительность (O(n) против O(n^2) для списка), и это нормально, потому что избегать дубликатов является самой целью набора.

Содержит для HashSet O(1) по сравнению с O(n) для списка, поэтому вы никогда не должны использовать список, если вам часто нужно использовать contains.

Ответ 2

ArrayList использует массив для хранения данных. ArrayList.contains будет иметь сложность O (n). Таким образом, по существу, поиск в массиве снова и снова будет иметь сложность O(n^2).

В то время как HashSet использует механизм хеширования для хранения элементов в своих соответствующих ведрах. Операция HashSet будет быстрее для длинного списка значений. Он достигнет элемента в O(1).

Ответ 3

Если вам не нужен список, я бы просто использовал 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).

Ответ 4

Я сделал тест, поэтому, пожалуйста, проверьте результат:

Для пунктов SAME STRING в HashSet, TreeSet, ArrayList и LinkedList приведены результаты для

50.000 UUIDs
- ПОИСК ОТДЫХА: e608c7d5-c861-4603-9134-8c636a05a42b (индекс 25.000)
- hashSet.contains(item)? TRUE 0 мс
- treeSet.contains(item)? TRUE 0 мс
- arrayList.contains(item)? ИСТИНА 2 мс
- linkedList.contains(item)? ИСТИНА 3 мс
5.000.000 UUIDs
- ИСКАТЬ ДЕТАЛЬ: 61fb2592-3186-4256-a084-6c96f9322a86 (индекс 25.000)
- hashSet.contains(item)? TRUE 0 мс
- treeSet.contains(item)? TRUE 0 мс
- arrayList.contains(item)? ИСТИНА 1 мс
- linkedList.contains(item)? ИСТИНА 2 мс
5.000.000 UUIDs
- ПОИСКОВЫЙ ДЕТЕКТОР: db568900-c874-46ba-9b44-0e1916420120 (индекс 2.500.000)
- hashSet.contains(item)? TRUE 0 мс
- treeSet.contains(item)? TRUE 0 мс
- arrayList.contains(item)? ИСТИНА 33 мс
- linkedList.contains(item)? ИСТИНА 65 мс

Основываясь на вышеприведенных результатах, нет большой разницы в использовании списка массивов против установленного. Возможно, вы можете попробовать изменить этот код и заменить 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");
    }

Ответ 5

Вы можете добавить элементы в список. Затем, для дедуплирования -

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() в другом наборе, чтобы он имел только уникальные значения.