wake-up-neo.net

HashSet vs TreeSet vs LinkedHashSet auf der Grundlage der Addition doppelter Werte

Ich lerne das Herz von Kern-Java, das heißt Collections Ich würde gerne wissen, was intern passiert, wenn wir ein doppeltes Element in HashSet, TreeSet, LinkedHashSet hinzufügen.

Der Wettereintrag wird ersetzt, ignoriert oder eine Ausnahme wird ausgelöst und das Programm wird beendet . Und eine Unterfrage ist: Welche hat die gleiche oder durchschnittliche zeitliche Komplexität für alle ihre Operationen

Ihre Antwort wird sehr geschätzt.

21

TreeSet, LinkedHashSet und HashSet in Java sind eine Drei-Set-Implementierung im Collection-Framework und werden wie viele andere auch zum Speichern von Objekten verwendet. Das Hauptmerkmal von TreeSet ist das Sortieren, LinkedHashSet ist die Einfügungsreihenfolge und HashSet ist nur eine allgemeine Sammlung zum Speichern von Objekten. HashSet wird mithilfe von HashMap in Java implementiert, während TreeSet mithilfe von TreeMap implementiert wird. TreeSet ist eine SortedSet-Implementierung, mit der Elemente in der sortierten Reihenfolge gehalten werden können, die entweder von Comparable oder Comparator definiert wird. Comparable wird für die natürliche Sortierreihenfolge und Comparator für die Sortierreihenfolge von Objekten verwendet, die beim Erstellen der TreeSet-Instanz bereitgestellt werden können. Bevor wir den Unterschied zwischen TreeSet, LinkedHashSet und HashSet sehen, sollten wir einige Ähnlichkeiten zwischen ihnen sehen:

1) Duplikate: Alle drei Implementierungen der Set-Schnittstelle bedeuten, dass sie keine Duplikate speichern dürfen.

2) Thread-Sicherheit: HashSet, TreeSet und LinkedHashSet sind nicht threadsicher, wenn Sie sie in einer Multi-Threading-Umgebung verwenden, in der mindestens ein Thread einen Satz ändert, den Sie für die externe Synchronisierung benötigen.

3) Fail-Fast-Iterator: Iterator, der von TreeSet, LinkedHashSet und HashSet zurückgegeben wird, ist ein Fail-Fast-Iterator. Wenn Iterator nach seiner Erstellung auf eine andere Weise als die remove () - Methode von Iterators geändert wird, wird ConcurrentModificationException mit größter Anstrengung ausgelöst. Lesen Sie hier mehr über ausfallsichere und ausfallsichere Iteratoren

Nun sehen wir den Unterschied zwischen HashSet, LinkedHashSet und TreeSet in Java:

Leistung und Geschwindigkeit: Der erste Unterschied besteht in der Geschwindigkeit. HashSet ist am schnellsten, LinkedHashSet ist an zweiter Stelle bezüglich Performance oder fast ähnlich wie HashSet, TreeSet ist jedoch etwas langsamer, da Sortieroperationen bei jedem Einfügen erforderlich sind. TreeSet bietet garantierte O(log(n)) - Zeit für allgemeine Vorgänge wie Hinzufügen, Entfernen und Enthalten, während HashSet und LinkedHashSet eine konstante Zeitleistung bieten, z. O(1) zum Hinzufügen, Enthalten und Entfernen der angegebenen Hash-Funktion, um Elemente gleichmäßig im Bucket zu verteilen.

Reihenfolge: HashSet behält keine Reihenfolge bei, während LinkedHashSet die Einfügungsreihenfolge von Elementen ähnlich der List-Schnittstelle und TreeSet die Sortierreihenfolge oder Elemente verwaltet.

Interne Implementierung: HashSet wird durch eine HashMap-Instanz gesichert, LinkedHashSet wird mithilfe von HashSet und LinkedList implementiert, während TreeSet von NavigableMap in Java gesichert wird und standardmäßig TreeMap verwendet.

null: Sowohl HashSet als auch LinkedHashSet lassen Null zu, aber TreeSet lässt keine Null zu und wirft Java.lang.NullPointerException aus, wenn Sie Null in TreeSet einfügen. Da TreeSet die compareTo () - Methode der jeweiligen Elemente verwendet, um diese zu vergleichen, wodurch NullPointerException beim Vergleichen mit null ausgelöst wird, folgt ein Beispiel:

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)

Vergleich: HashSet und LinkedHashSet verwenden in Java zum Vergleich die equals () -Methode, TreeSet verwendet jedoch die compareTo () -Methode, um die Reihenfolge zu erhalten. Deshalb sollte compareTo () mit Java gleich sein. Andernfalls unterbrechen Sie den allgemeinen Kontakt der Set-Schnittstelle, d. h. er kann Duplikate zulassen.

Verwenden Sie den Link unten, um die interne Implementierung anzuzeigen 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

Quelle: http://javarevisited.blogspot.com/2012/11/difference-between-reeset-hashset-vs-linkedhashset-Java.html#ixzz2lGo6Y9mm

41
constantlearner
7
user2485429

Ich habe nicht viele harte Daten zu den Unterschieden gefunden, deshalb habe ich einen Benchmark für die 3 Fälle durchgeführt.

Es scheint, dass HashSet beim Hinzufügen etwa viermal schneller als TreeSet ist (unter bestimmten Umständen kann dies je nach den genauen Eigenschaften Ihrer Daten usw. variieren).

# 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

Hier ist der Benchmark-Code:

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());
        }
    }
}
1
Rich

tldr: Wiederholungswerte werden von diesen Sammlungen ignoriert.

Ich habe keine vollständige Antwort auf den mutigen Teil der Frage gesehen, was genau mit Duplikaten passiert? Überschreibt es das alte Objekt oder ignoriert es das neue? Betrachten Sie dieses Beispiel eines Objekts, bei dem ein Feld die Gleichheit bestimmt, es gibt jedoch zusätzliche Daten, die variieren können:

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);
    }
}

Dieser Unit-Test zeigt, dass doppelte Werte von allen 3 Sammlungen ignoriert werden:

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"));
    }
}

Ich habe mir auch die Implementierung von TreeSet angesehen, von der wir wissen, dass sie TreeMap verwendet ... In TreeSet.Java:

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

Anstelle der gesamten Put-Methode von TreeMap wird hier die relevante Suchschleife angezeigt:

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

wenn also cmp == 0 ist, dh wir haben einen doppelten Eintrag gefunden, kehren wir frühzeitig zurück, anstatt am Ende der Schleife ein Kind hinzuzufügen. Der Aufruf von setValue macht eigentlich nichts, da TreeSet hier Dummy-Daten für den Wert verwendet. Wichtig ist, dass sich der Schlüssel nicht ändert. Wenn Sie sich HashMap ansehen, sehen Sie dasselbe Verhalten.

0
Ben B