Wird es eine Instanz geben, in der die Suche nach einem Schlüsselwort in einer linearen Liste schneller ist als eine Hash-Tabelle?Hash-Tabelle vs. lineare Liste
Ich würde im Grunde gerne wissen, ob es einen Randfall gibt, wo die Suche nach einem Schlüsselwort in einer linearen Liste schneller als eine Hash-Tabelle-Suche sein wird.
Danke!
Ja, in den Fällen einer sehr kleinen Anzahl von Elementen. Denken Sie darüber nach, wie ein Hash funktioniert. Er muss den Hash berechnen, um einen Bucket zu finden, und dann die Liste in diesem Bucket durchsuchen. Außerdem könnte es ein komplexer Multi-Level-Hash usw. sein. Sie können also sogar den Punkt erreichen, an dem das Durchsuchen einer linearen Liste mehr Arbeit bringt als der Hash-Lookup-Algorithmus.
Eine andere Instanz wäre, wenn das Element, das Sie suchen, immer am Anfang oder am Anfang einer Liste steht. Je nachdem, was Sie tun, könnte es passieren.
Es gibt andere, aber das sollte Ihnen helfen, darüber nachzudenken.
Immer noch nicht verwirrt werden. Der Hash ist normalerweise, was Sie wollen.
Suchen in einer Hash-Tabelle ist nicht immer konstant Zeit in der Realität. Wenn die Hash-Funktion schlecht mit den Daten übereinstimmt, können viele Kollisionen auftreten, und im Extremfall, dass jedes Datenelement denselben Hash-Wert hat, sieht das Ergebnis ähnlich aus wie eine lineare Suche. Abhängig von den Details funktioniert diese effektive lineare Suche möglicherweise langsamer als eine lineare Suche über die Daten in einem Array. (ZB open addressing mit einer quadratischen Probing-Sequenz, die die Prozessor-Caches schlecht nutzt, könnte durchaus langsamer als eine lineare Suche über ein Array sein.)
Hier ist ein Beispiel für einen realen Fall, in dem alle Schlüssel landeten der gleiche Eimer: Java bug 4669519.