Hashset vs. Treeset

Question

Ich habe Bäume schon immer geliebt, so schön O(n*log(n)) und ihre Sauberkeit. Allerdings hat mich jeder Software-Ingenieur, den ich kenne, gefragt, warum ich eine TreeSet . Mit einem CS-Hintergrund glaube ich nicht, dass es so wichtig ist, was Sie verwenden, und ich habe keine Lust, mit Hash-Funktionen und Buckets herumzuspielen (im Fall von Java ).

In welchen Fällen sollte ich eine HashSet über eine TreeSet ?

Answer 1

Auch nach 11 Jahren dachte niemand daran, eine sehr wichtig Unterschied.

Glauben Sie, dass, wenn HashSet ist gleich TreeSet ist dann auch das Gegenteil der Fall? Werfen Sie einen Blick auf diesen Code:

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.add("a");
hashSet.add("A");
System.out.println(hashSet.equals(treeSet));
System.out.println(treeSet.equals(hashSet));

Versuchen Sie, die Ausgabe zu erraten, und fahren Sie dann mit dem Mauszeiger über das Snippet, um zu sehen, wie die tatsächliche Ausgabe aussieht. Sind Sie bereit? Hier ist es:

falsch
wahr

Das ist richtig, sie haben keine Äquivalenzrelation für einen Komparator, der mit Gleichen unvereinbar ist. Der Grund dafür ist, dass ein TreeSet verwendet einen Komparator zur Bestimmung der Gleichwertigkeit, während HashSet verwendet equals . Intern verwenden sie HashMap y TreeMap daher sollten Sie dieses Verhalten bei den genannten Map の方もそうですね。

Ursprünglich beantwortet

Answer 2

Nachricht bearbeiten ( vollständige Überarbeitung ) Wenn die Reihenfolge keine Rolle spielt, dann ist das der Fall. Beide sollten Log(n) ergeben - es wäre von Nutzen zu sehen, ob eine der beiden Methoden mehr als fünf Prozent schneller ist als die andere. HashSet kann O(1) ergeben. Ein Test in einer Schleife sollte zeigen, ob dies der Fall ist.

Answer 3

Es wurden viele Antworten gegeben, die auf technischen Erwägungen beruhen, insbesondere in Bezug auf die Leistung. Meiner Meinung nach ist die Wahl zwischen TreeSet y HashSet Angelegenheiten.

Ich würde aber eher sagen, dass die Wahl von folgenden Faktoren bestimmt werden sollte konzeptionell erste Überlegungen.

Wenn für die Objekte, die Sie bearbeiten müssen, eine natürliche Reihenfolge keinen Sinn macht, dann verwenden Sie nicht TreeSet .
Es handelt sich um eine sortierte Menge, da sie Folgendes implementiert SortedSet . Das bedeutet, dass Sie die Funktion überschreiben müssen compareTo was mit dem übereinstimmen sollte, was die Funktion equals . Wenn Sie zum Beispiel eine Menge von Objekten einer Klasse namens Student haben, dann glaube ich nicht, dass ein TreeSet wäre sinnvoll, da es keine natürliche Reihenfolge zwischen den Schülern gibt. Man kann sie nach ihrem Notendurchschnitt ordnen, aber das ist keine "natürliche Ordnung". Funktion compareTo würde nicht nur 0 zurückgeben, wenn zwei Objekte denselben Schüler repräsentieren, sondern auch, wenn zwei verschiedene Schüler dieselbe Note haben. Für den zweiten Fall, equals würde false zurückgeben (es sei denn, Sie entscheiden sich dafür, dass letzteres true zurückgibt, wenn zwei verschiedene Schüler die gleiche Note haben, was dazu führen würde, dass equals Funktion eine irreführende, um nicht zu sagen eine falsche Bedeutung haben).
Bitte beachten Sie diese Konsistenz zwischen equals y compareTo ist optional, wird aber dringend empfohlen. Andernfalls wird der Vertrag der Schnittstelle Set gebrochen ist, so dass Ihr Code für andere Menschen irreführend ist und möglicherweise zu unerwartetem Verhalten führt.

この enlace könnte eine gute Informationsquelle für diese Frage sein.

Answer 4

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?

    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}