Вопрос по java, collections, set – HashSet против TreeSet против LinkedHashSet на основе добавления повторяющегося значения

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

У меня нетне видел полного ответа на выделенную жирным шрифтом часть вопроса, что именно происходит с дубликатами? Перезаписывает ли старый объект старый или игнорирует новый? Рассмотрим пример объекта, в котором одно поле определяет равенство, но есть дополнительные данные, которые могут различаться:

public class MyData implements Comparable {
    public final Int,eger 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);
    }
}

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

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 testSet;

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

    @Parameterized.Parameters
    public static Collection 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, вы 'увидим такое же поведение.

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

1) Дубликаты: все три инструмента «Установить интерфейс» означают, что им не разрешается хранить дубликаты.

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

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

Теперь давайтеВидим разницу между 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 неt позволить 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 () для поддержания порядка. Тот's, почему 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

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

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

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

Похоже, что 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 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 comparator() {
            return Comparator.comparing(Item::getName, Comparator.naturalOrder())
                .thenComparing(Item::getId, Comparator.naturalOrder());
        }
    }
}