Warum ist Laufzeit der contains()-Methode bei HashSets O(1)?
Habe aufgeschrieben: HashSets verwenden Hashtabelle (also ne HashMap), um Hashwerte und Elemente OHNE Duplikate zu speichern.
HashMaps enthalten Hashwerte der Schlüssel, um Elemente zu finden
Aber wie kommt man nun bei der contains()-Methode des HashSets auf O(1)?
Ich würde mir nämlich vorstellen, dass das folgende passiert:
Man übergibt als Parameter das Element, das überprüft werden soll, ob es sich im Set befindet. Dieses Element steht in einer Hashtabelle mit Hashwerten drin. Also wird nun die Hashtabelle durchsucht, ob das Element darin ist. Aber müsste dazu nicht die ganze Tabelle durchgegangen werden, Element für Element, bis das jeweilige Element gefunden wurde?
Wie kommt man dann zu O(1), also dass das Element quasi auf Anhieb angesteuert werden kann, falls es sich im Set befindet? Wie muss ich mir das vorstellen?
lg Kath
3 Antworten
Wenn man 1000 Einträge in einer Liste hat, braucht man im Durchschnitt 500 Zugriffe, um einen bestimmten Eintrag zu finden.
In einer Hashtabelle mit 25 Keys hat man 25 Listen mit (im Idealfall) je 40 Einträgen, braucht also im Durchschnitt 20 Zugriffe.
Man hat so die 500 durch 25 geteilt, am Laufzeitverhalten aber sonst nichts geändert.
Wie man auf O(1) kommt, würde mich auch interessieren.
Das stimmt, die Hashtabelle ist normalerweise ein Array, zumal deren Größe ja von vornherein bekannt ist.
Das Problem ist, wenn mehrere Einträge den selben Hashwert haben, also in dasselbe Element des Arrays einzutragen sind. Dazu braucht man Listen oder eine andere Implementierung, die das O(n) hier einbringt.
(zumindest meiner Meinung nach)
ich glaube, das wird quasi stark vereinfacht betrachtet, also wenn die Hashfunktion so gut ist, dass keine Hashwerte doppelt vorkommen. Somit ist es eher O(1)...
einfach gesagt es ist die gleiche prozedur wie bei arrays. das auslesen eines indexes bei einem array läuft in der art genauso
Nun, es ist ein bisschen gelogen – es kann länger dauern, aber normalerweise tut es das nicht.
Grundsätzlich ist eine Hash-Tabelle ein Array, das alle Schlüssel enthält, nach denen gesucht werden soll. Die Position jedes Schlüssels im Array wird durch die Hash-Funktion bestimmt, die jede Funktion sein kann, die immer dieselbe Eingabe auf dieselbe Ausgabe abbildet. Wir nehmen an, dass die Hash-Funktion O(1) ist.
Wenn wir also etwas in die Hash-Tabelle einfügen, verwenden wir die Hash-Funktion (nennen wir es h), um den Ort zu finden, an dem es abgelegt werden soll, und fügen es dort ein. Jetzt fügen wir eine andere Sache ein, hashen und speichern. Und ein anderer. Jedes Mal, wenn wir Daten einfügen, dauert es O (1) Zeit, um sie einzufügen (da die Hash-Funktion O (1) ist).
Das Nachschlagen von Daten ist dasselbe. Wenn wir einen Wert x finden wollen, müssen wir nur h(x) herausfinden, das uns sagt, wo sich x in der Hash-Tabelle befindet. Wir können also auch jeden beliebigen Hash-Wert in O(1) nachschlagen.
Nun zur Lüge: Das Obige ist eine sehr schöne Theorie mit einem Problem: Was ist, wenn wir Daten einfügen und an dieser Position des Arrays bereits etwas ist? Es gibt keine Garantie dafür, dass die Hash-Funktion nicht dieselbe Ausgabe für zwei verschiedene Eingaben erzeugt (es sei denn, Sie haben eine perfekte Hash-Funktion, aber diese sind schwierig zu erstellen). Daher müssen wir beim Einfügen eine von zwei Strategien wählen:
Speichern Sie mehrere Werte an jeder Stelle im Array (sagen wir, jeder Array-Slot hat eine verknüpfte Liste). Wenn Sie jetzt nachschlagen, ist es immer noch O(1), um an die richtige Stelle im Array zu gelangen, aber möglicherweise eine lineare Suche in einer (hoffentlich kurzen) verknüpften Liste. Dies wird als "separate Verkettung" bezeichnet.
Wenn Sie feststellen, dass etwas bereits vorhanden ist, hashen Sie es erneut und suchen Sie einen anderen Ort. Wiederholen Sie dies, bis Sie eine leere Stelle finden, und legen Sie sie dort ab. Das Nachschlageverfahren kann den gleichen Regeln folgen, um die Daten zu finden. Jetzt ist es immer noch O (1), um zum ersten Ort zu gelangen, aber es gibt eine möglicherweise (hoffentlich kurze) lineare Suche, die Sie um den Tisch herum hüpfen lassen müssen, bis Sie die gesuchten Daten gefunden haben. Dies wird als "offene Adressierung" bezeichnet.
Grundsätzlich sind beide Ansätze immer noch größtenteils O (1), aber mit einer hoffentlich kurzen linearen Sequenz. Wir können für die meisten Zwecke annehmen, dass es O(1) ist. Wenn die Hash-Tabelle zu voll wird, können diese linearen Suchen immer länger werden, und dann ist es an der Zeit, einen „Re-Hash“ durchzuführen, was bedeutet, eine neue Hash-Tabelle mit viel größerer Größe zu erstellen und alle Daten wieder darin einzufügen .
Nun, es ist ein bisschen gelogen – es kann länger dauern, aber normalerweise tut es das nicht.
Grundsätzlich ist eine Hash-Tabelle ein Array, das alle Schlüssel enthält, nach denen gesucht werden soll. Die Position jedes Schlüssels im Array wird durch die Hash-Funktion bestimmt, die jede Funktion sein kann, die immer dieselbe Eingabe auf dieselbe Ausgabe abbildet. Wir nehmen an, dass die Hash-Funktion O(1) ist.
Wenn wir also etwas in die Hash-Tabelle einfügen, verwenden wir die Hash-Funktion (nennen wir es h), um den Ort zu finden, an dem es abgelegt werden soll, und fügen es dort ein. Jetzt fügen wir eine andere Sache ein, hashen und speichern. Und ein anderer. Jedes Mal, wenn wir Daten einfügen, dauert es O (1) Zeit, um sie einzufügen (da die Hash-Funktion O (1) ist).
Das Nachschlagen von Daten ist dasselbe. Wenn wir einen Wert x finden wollen, müssen wir nur h(x) herausfinden, das uns sagt, wo sich x in der Hash-Tabelle befindet. Wir können also auch jeden beliebigen Hash-Wert in O(1) nachschlagen.
Nun zur Lüge: Das Obige ist eine sehr schöne Theorie mit einem Problem: Was ist, wenn wir Daten einfügen und an dieser Position des Arrays bereits etwas ist? Es gibt keine Garantie dafür, dass die Hash-Funktion nicht dieselbe Ausgabe für zwei verschiedene Eingaben erzeugt (es sei denn, Sie haben eine perfekte Hash-Funktion, aber diese sind schwierig zu erstellen). Daher müssen wir beim Einfügen eine von zwei Strategien wählen:
Speichern Sie mehrere Werte an jeder Stelle im Array (sagen wir, jeder Array-Slot hat eine verknüpfte Liste). Wenn Sie jetzt nachschlagen, ist es immer noch O(1), um an die richtige Stelle im Array zu gelangen, aber möglicherweise eine lineare Suche in einer (hoffentlich kurzen) verknüpften Liste. Dies wird als "separate Verkettung" bezeichnet.
Wenn Sie feststellen, dass etwas bereits vorhanden ist, hashen Sie es erneut und suchen Sie einen anderen Ort. Wiederholen Sie dies, bis Sie eine leere Stelle finden, und legen Sie sie dort ab. Das Nachschlageverfahren kann den gleichen Regeln folgen, um die Daten zu finden. Jetzt ist es immer noch O (1), um zum ersten Ort zu gelangen, aber es gibt eine möglicherweise (hoffentlich kurze) lineare Suche, die Sie um den Tisch herum hüpfen lassen müssen, bis Sie die gesuchten Daten gefunden haben. Dies wird als "offene Adressierung" bezeichnet.
Grundsätzlich sind beide Ansätze immer noch größtenteils O (1), aber mit einer hoffentlich kurzen linearen Sequenz. Wir können für die meisten Zwecke annehmen, dass es O(1) ist. Wenn die Hash-Tabelle zu voll wird, können diese linearen Suchen immer länger werden, und dann ist es an der Zeit, einen „Re-Hash“ durchzuführen, was bedeutet, eine neue Hash-Tabelle mit viel größerer Größe zu erstellen und alle Daten wieder darin einzufügen .
Meiner Meinung nach ist das Suchen in einer Hashtabelle immer noch O(n).
Die Suchzeit wird im Vergleich zu einer einfachen Tabelle zwar durch die Anzahl der Hashkeys geteilt, das ändert aber nichts am prinzipiellen Laufzeitverhalten.
In unserer Klausur müssen wir begründen, warum in einem HashSet die contains()-Methode ne Laufzeit von O(1) hat...
Warum wird es durch die Anzahl der Hashkeys geteilt? Was genau wird durch diese Anzahl geteilt?
Ich glaube der Punkt ist, dass Hashtabellen nicht mit Listen, sondern mit Arrays vergleichbar sind...