Hat eine HashMap mit String Keys wirklich eine geringere Zeitkomplexität als ein Trie?

Question

Sagen wir, ich möchte ein Wörterbuch von Strings speichern und ich möchte wissen, ob eine Zeichenfolge existiert oder nicht. Ich kann eine Trie oder eine HashMap verwenden. Die HashMap hat eine Zeitkomplexität von O (1) mit einer hohen Wahrscheinlichkeit, während die Trie in diesem Fall eine Zeitkomplexität von O (k) haben würde, wobei k die Länge der Kette ist.

Jetzt ist meine Frage: Hat die Berechnung des Hash-Wertes der Zeichenkette keine Zeitkomplexität von O (k), was die Komplexität der HashMap gleich macht? Wenn nicht, warum?

Die Art, wie ich es sehe ist, dass eine Trie hier weniger Zeitkomplexität als eine HashMap zum Nachschlagen einer Zeichenkette hätte, da die HashMap neben der Berechnung des Hashwertes Kollisionen verursachen könnte. Fehle ich etwas?

Aktualisierung: Welche Datenstruktur würden Sie verwenden, um die Geschwindigkeit beim Erstellen eines Wörterbuchs zu optimieren?

Answer 1

Neben der Komplexität der Implementierung eines Trie werden bei der Implementierung der Methode hashCode bestimmte Optimierungen durchgeführt, die die Buckets in einer Hash-Tabelle bestimmen. Für java.lang.String, eine unveränderliche Klasse, hier ist das, was JDK-8 tut:

public int hashCode() { 
    int h = hash; 
    if (h == 0 && value.length > 0) { 
     char val[] = value; 

     for (int i = 0; i < value.length; i++) { 
      h = 31 * h + val[i]; 
     } 
     hash = h; 
    } 
    return h; 
} 

So ist es zwischengespeichert wird (und ist Thread-sicher). Einmal berechnet, muss der Hash-Code eines Strings nicht neu berechnet werden. Dies erspart Ihnen, die O(k) Zeit im Falle von Hash-Tabelle (oder Hash-Set, Hash-Karte) zu verbringen.

Während ich Wörterbücher implementiere, denke ich, dass Versuche glänzen, wo man eher an möglichen Teilübereinstimmungen als an genauen Übereinstimmungen interessiert ist. Im Allgemeinen funktionieren Hash-basierte Lösungen am besten bei exakten Übereinstimmungen.

Answer 2

Die Zeit Komplexität der Durchführung von Operationen auf eine Hash-Tabelle wird in der Regel in der Anzahl der Hashes und Vergleiche, die durchgeführt werden müssen, gemessen. Erwartungsgemäß sind die Kosten, wenn sie auf diese Weise gemessen werden, O (1), da nach Erwartung nur eine konstante Anzahl von Hashwerten und Vergleichen verwendet werden muss.

Um die Kosten für die Verwendung einer Hash-Tabelle für Strings zu ermitteln, müssen Sie tatsächlich die Kosten dieser Operationen berücksichtigen, die jeweils O (k) für eine Zeichenfolge der Länge k sind. Daher sind die Kosten einer Hashtabellenoperation für eine Zeichenfolge O (1) & middot; O (k) = O (k), passend zu den Trie-Kosten, allerdings nur in Erwartung und mit einem anderen konstanten Faktor.