HashSet vs TreeSet vs LinkedHashSet на основе добавления повторяющегося значения

Ответ 1

TreeSet, LinkedHashSet и HashSet в Java - это три реализации Set в структуре коллекции, и, как и многие другие, они также используются для хранения объектов. Основная особенность TreeSet - сортировка, LinkedHashSet - порядок вставки, а HashSet - это общая коллекция для хранения объекта. HashSet реализуется с использованием HashMap в Java, а TreeSet реализуется с помощью TreeMap. TreeSet - это реализация SortedSet, которая позволяет сохранять элементы в отсортированном порядке, определяемом интерфейсом Comparable или Comparator. Comparable используется для сортировки естественного порядка и Comparator для пользовательской сортировки заказов объектов, которые могут быть предоставлены при создании экземпляра TreeSet. В любом случае, прежде чем видеть разницу между TreeSet, LinkedHashSet и HashSet, можно увидеть некоторые сходства между ними:

1) Дубликаты: все три реализуют интерфейс Set, они не могут хранить дубликаты.

2) Безопасность потоков: HashSet, TreeSet и LinkedHashSet не являются потокобезопасными, если вы используете их в многопоточной среде, где по крайней мере один поток изменяет набор, который вам нужно синхронизировать извне.

3) Fail-Fast Iterator: Итератор, возвращаемый TreeSet, LinkedHashSet и HashSet, является отказоустойчивым Iterator. Если Iterator модифицируется после его создания любым способом, отличным от метода remove() Iterators, он будет лучше всего использовать ConcurrentModificationException. читайте больше об отказоустойчивом и надежном Iterator здесь

Теперь посмотрим разницу между HashSet, LinkedHashSet и TreeSet в Java:

Производительность и скорость: первое различие между ними происходит с точки зрения скорости. HashSet является самым быстрым, LinkedHashSet является вторым по производительности или почти похож на HashSet, но TreeSet бит медленнее из-за сортировки, которую он должен выполнять при каждой вставке. TreeSet обеспечивает гарантированное время O (log (n)) для общих операций, таких как добавление, удаление и содержит, в то время как HashSet и LinkedHashSet предлагают постоянную производительность времени, например. O (1) для добавления, содержит и удаляет заданную хэш-функцию, равномерно распределяющую элементы в ведре.

Заказ: HashSet не поддерживает какой-либо заказ, в то время как LinkedHashSet поддерживает порядок вставки элементов, подобный интерфейсу List, и TreeSet поддерживает порядок сортировки или элементы.

Внутренняя реализация: HashSet поддерживается экземпляром HashMap, LinkedHashSet реализуется с использованием HashSet и LinkedList, а TreeSet подкрепляется NavigableMap в Java и по умолчанию использует TreeMap.

null: И HashSet, и LinkedHashSet разрешают null, но TreeSet не разрешает null, но TreeSet не разрешает null и бросает java.lang.NullPointerException, когда вы вставляете null в TreeSet. Поскольку TreeSet использует метод compareTo() соответствующих элементов для сравнения их, который генерирует исключение NullPointerException при сравнении с нулем, вот пример:

TreeSet cities
Exception in thread "main" java.lang.NullPointerException
        at java.lang.String.compareTo(String.java:1167)
        at java.lang.String.compareTo(String.java:92)
        at java.util.TreeMap.put(TreeMap.java:545)
        at java.util.TreeSet.add(TreeSet.java:238)

Сравнение: HashSet и LinkedHashSet использует метод equals() в Java для сравнения, но TreeSet использует метод compareTo() для поддержания порядка. Вот почему compareTo() должен быть согласован с равными в Java. неспособность сделать это, обрывает общий контакт интерфейса Set, то есть он может допускать дубликаты.

Использование может использовать ссылку ниже, чтобы увидеть внутреннюю реализацию http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashSet.java#HashSet.add%28java.lang.Object%29

From the source code 
Hashset hases Hashmap to store the data and LinkedHashSet extends Hashset and hence uses same add method of Hashset But TreeSet uses NavigableMap to store the data

Источник: http://javarevisited.blogspot.com/2012/11/difference-between-treeset-hashset-vs-linkedhashset-java.html#ixzz2lGo6Y9mm

Ответ 2

Это изображение может помочь вам...

http://javaconceptoftheday.com/wp-content/uploads/2015/01/HashSetVsLinkedHashSetVsTreeSet.png

Источник изображения: http://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/

Ответ 3

TL;DR: значения повторений игнорируются этими коллекциями.

Я не видел полного ответа на смелую часть вопроса, что ТОЧНО случается с дубликатами? Переписывает ли он старый объект или игнорирует новый? Рассмотрим этот пример объекта, где одно поле определяет равенство, но есть дополнительные данные, которые могут меняться:

public class MyData implements Comparable {
    public final Integer valueDeterminingEquality;
    public final String extraData;

    public MyData(Integer valueDeterminingEquality, String extraData) {
        this.valueDeterminingEquality = valueDeterminingEquality;
        this.extraData = extraData;
    }

    @Override
    public boolean equals(Object o) {
        return valueDeterminingEquality.equals(((MyData) o).valueDeterminingEquality);
    }

    @Override
    public int hashCode() {
        return valueDeterminingEquality.hashCode();
    }

    @Override
    public int compareTo(Object o) {
        return valueDeterminingEquality.compareTo(((MyData)o).valueDeterminingEquality);
    }
}

Этот unit test показывает, что дублирующиеся значения игнорируются всеми тремя коллекциями:

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.*;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

@RunWith(Parameterized.class)
public class SetRepeatedItemTest {
    private final Set<MyData> testSet;

    public SetRepeatedItemTest(Set<MyData> testSet) {
        this.testSet = testSet;
    }

    @Parameterized.Parameters
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][] {
                { new TreeSet() }, { new HashSet() }, { new LinkedHashSet()}
        });
    }

    @Test
    public void testTreeSet() throws Exception {
        testSet.add(new MyData(1, "object1"));
        testSet.add(new MyData(1, "object2"));
        assertThat(testSet.size(), is(1));
        assertThat(testSet.iterator().next().extraData, is("object1"));
    }
}

Я также изучил реализацию TreeSet, который, как мы знаем, использует TreeMap... В TreeSet.java:

public boolean add(E var1) {
    return this.m.put(var1, PRESENT) == null;
}

Вместо того, чтобы показывать метод TreeMap целиком, вот соответствующий цикл поиска:

parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
        t = t.left;
else if (cmp > 0)
        t = t.right;
else
    return t.setValue(value);
} while (t != null);

поэтому, если cmp == 0, т.е. мы нашли повторяющуюся запись, мы возвращаемся раньше, а не добавляем ребенка в конец цикла. Вызов setValue на самом деле ничего не делает, потому что TreeSet использует фиктивные данные для значения здесь, важно то, что ключ не изменяется. Если вы посмотрите в HashMap, вы увидите то же поведение.

Ответ 4

Я не нашел много жестких данных о различиях, поэтому я провел тест для трех случаев.

Похоже, что HashSet примерно в 4 раза быстрее, чем TreeSet при добавлении (при определенных обстоятельствах это, вероятно, будет меняться в зависимости от точных характеристик ваших данных и т.д.).

# Run complete. Total time: 00:22:47

Benchmark                                                     Mode  Cnt  Score   Error  Units
DeduplicationWithSetsBenchmark.deduplicateWithHashSet        thrpt  200  7.734 ▒ 0.133  ops/s
DeduplicationWithSetsBenchmark.deduplicateWithLinkedHashSet  thrpt  200  7.100 ▒ 0.171  ops/s
DeduplicationWithSetsBenchmark.deduplicateWithTreeSet        thrpt  200  1.983 ▒ 0.032  ops/s

Вот эталонный код:

package my.app;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class DeduplicationWithSetsBenchmark {

    static Item[] inputData = makeInputData();

    @Benchmark
    public int deduplicateWithHashSet() {
        return deduplicate(new HashSet<>());
    }

    @Benchmark
    public int deduplicateWithLinkedHashSet() {
        return deduplicate(new LinkedHashSet<>());
    }

    @Benchmark
    public int deduplicateWithTreeSet() {
        return deduplicate(new TreeSet<>(Item.comparator()));
    }

    private int deduplicate(Set<Item> set) {
        for (Item i : inputData) {
            set.add(i);
        }
        return set.size();
    }

    public static void main(String[] args) throws RunnerException {

        // Verify that all 3 methods give the same answers:
        DeduplicationWithSetsBenchmark x = new DeduplicationWithSetsBenchmark();
        int count = x.deduplicateWithHashSet();
        assert(count < inputData.length);
        assert(count == x.deduplicateWithLinkedHashSet());
        assert(count == x.deduplicateWithTreeSet());


        Options opt = new OptionsBuilder()
            .include(DeduplicationWithSetsBenchmark.class.getSimpleName())
            .forks(1)
            .build();

        new Runner(opt).run();
    }

    private static Item[] makeInputData() {
        int count = 1000000;
        Item[] acc = new Item[count];
        Random rnd = new Random();

        for (int i=0; i<count; i++) {
            Item item = new Item();
            // We are looking to include a few collisions, so restrict the space of the values
            item.name = "the item name " + rnd.nextInt(100);
            item.id = rnd.nextInt(100);
            acc[i] = item;
        }
        return acc;
    }

    private static class Item {
        public String name;
        public int id;

        public String getName() {
            return name;
        }

        public int getId() {
            return id;
        }

        @Override
        public boolean equals(Object obj) {
            Item other = (Item) obj;

            return name.equals(other.name) && id == other.id;
        }

        @Override
        public int hashCode() {
            return name.hashCode() * 13 + id;
        }

        static Comparator<Item> comparator() {
            return Comparator.comparing(Item::getName, Comparator.naturalOrder())
                .thenComparing(Item::getId, Comparator.naturalOrder());
        }
    }
}