Welche ist schneller, Hash-Lookup-oder Binär-Suche?
https://stackoverflow.com/questions/360040
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wenn Sie eine statische Gruppe von Objekten gegeben (statisch in dem Sinne, dass es einmal selten geladen, wenn überhaupt ändert), in welche die gleichzeitige Abfragen wiederholt benötigt mit optimaler Leistung, die besser ist, ein HashMap oder ein Array mit einer binären Suche einige mit benutzerdefinierte Komparator?
Ist die Antwort eine Funktion des Objekts oder Strukturtyp? Hash und / oder Gleich Funktion Leistung? Hash Einzigartigkeit? Listengröße? Hashset Größe / set Größe?
Die Größe der Menge, die ich an kann von 500k bis 10m überall suchen bin sein - einhüllen, dass die Informationen nützlich ist
.Während ich für eine C # Antwort suchen, denke ich, die wahre mathematische Antwort liegt nicht in der Sprache, so dass ich bin auch nicht, dass Tag. Wenn jedoch C # bestimmte Dinge bewusst sein, dass die Informationen gewünscht werden.
Lösung
Ok, ich werde versuchen, kurz zu sein.
C # kurze Antwort:
Testen Sie die zwei verschiedene Ansätze.
NET gibt Ihnen die Tools, um Ihren Ansatz mit einer Zeile Code zu ändern. verwenden System.Collections.Generic.Dictionary sonst und sicher sein, es mit einer großen Zahl als Anfangskapazität zu initialisieren, oder Sie werden den Rest Ihres Lebens passieren Gegenstände aufgrund des Jobs GC zu tun hat, das Einfügen alte Eimer Arrays zu sammeln.
Lange Antwort:
Eine Hash-Tabelle hat nahezu konstant Lookup Zeiten und in einer Hash-Tabelle in der realen Welt zu einem Elemente bekommen erfordert nicht nur einen Hash zu berechnen.
Um zu einem Element, Ihre Hash-Tabelle wird so etwas wie dies tun:
- Holen Sie sich den Hash-Wert des Schlüssels
- Holen Sie sich den Eimer Nummer für diesen Hash (in der Regel die Map-Funktion wie folgt aussieht Eimer = hash% bucketsCount)
- die Artikel Kette Traverse (im Grunde ist es eine Liste von Elementen, die gemeinsam nutzen die gleichen Eimer, die meisten Hash-Tabellen verwenden Dieses Verfahren der Handhabung bucket / hash Kollisionen), die an das beginnt Eimer und vergleichen Sie jede Taste mit der einer der Artikel, den Sie versuchen, hinzufügen / löschen / update / überprüfen, ob enthalten sind.
Lookup mal davon abhängen, wie „gut“ (wie spärlich ist der Ausgang) und schnell ist Ihre Hash-Funktion, die Anzahl der Schaufeln Sie verwenden, und wie schnell sind der Schlüssel Vergleich, es ist nicht immer die beste Lösung.
Eine bessere und tiefere Erklärung: http: //en.wikipedia. org / wiki / Hash_table
Andere Tipps
Für sehr kleine Sammlungen der Unterschied vernachlässigbar sein wird. Am unteren Ende des Bereichs (500k Artikel) Sie werden beginnen, um einen Unterschied zu sehen, wenn Sie viele Lookups tun. Eine binäre Suche wird O (log n) sein, während ein Hash-Lookup O (1) sein, abgeschrieben . Das ist nicht das gleiche wie wirklich konstant, aber Sie würden immer noch eine ziemlich schrecklich Hash-Funktion zu schlechter Leistung zu erhalten als eine binäre Suche haben müssen.
(Wenn ich "schrecklich Hash" sage, meine ich so etwas wie:
hashCode()
{
return 0;
}
Ja, es extrem schneller selbst, sondern bewirkt, dass Ihre Hashzuordnung eine verknüpfte Liste zu werden.)
ialiashkevich schrieb einige C # -Code ein Array und ein Wörterbuch mit den beiden Methoden zu vergleichen, aber es verwendet Lange Werte für Schlüssel. Ich wollte etwas testen, die eine Hash-Funktion während der Lookup tatsächlich ausführen würden, so modifizierte ich diesen Code. Habe ich es String-Werte zu verwenden, und ich Refactoring die bevölkern und Lookup-Abschnitte in ihre eigenen Methoden, so dass es einfacher ist, in einem Profiler zu sehen. Ich ließ auch in dem Code, die Langen Wert verwendet, nur als Vergleichspunkt. Schließlich habe ich die benutzerdefinierten binäre Suchfunktion befreien und verwendet, um die man in der Array Klasse.
Hier ist der Code:
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
Hier sind die Ergebnisse mit verschiedenen Größen von Sammlungen. (Die Zeiten sind in Millisekunden).
500000 Lange Werte ...
Bevölkern Lange Wörterbuch: 26
Bevölkern Lange Array: 2
Suchen Lange Wörterbuch: 9
Suchen Lange Array: 80500000 String-Werte ...
Bevölkern String Array: 1237
Bestücken Sie String-Wörterbuch: 46
Sort String Array: 1755
Suchen String-Wörterbuch: 27
Suchen String Array: 15691000000 Lange Werte ...
Bevölkern Lange Wörterbuch: 58
Bevölkern Lange Array: 5
Suchen Lange Wörterbuch: 23
Suchen Lange Array: 1361000000 String Werte ...
Bevölkern String Array: 2070
Bestücken Sie String-Wörterbuch: 121
Sort String Array: 3579
Suchen String-Wörterbuch: 58
Suchen String Array: 32673000000 Lange Werte ...
Bevölkern Lange Wörterbuch: 207
Bevölkern Lange Array: 14
Suchen Lange Wörterbuch: 75
Suchen Lange Array: 4353000000 String Werte ...
Bevölkern String Array: 5553
Bestücken Sie String-Wörterbuch: 449
Sort Array String: 11695
Suche String-Wörterbuch: 194
Suchen String Array: 1059410000000 Lange Werte ...
Bevölkern Lange Wörterbuch: 521
Bevölkern Lange Array: 47
Suchen Lange Wörterbuch: 202
Suchen Lange Array: 118110000000 String Werte ...
Bevölkern String Array: 18119
Bestücken Sie String-Wörterbuch: 1088
Sort Array String: 28174
Suche String-Wörterbuch: 747
Suchen String Array: 26503
Und zum Vergleich, hier ist der Profiler-Ausgang für den letzten Lauf des Programms (10 Millionen Datensätze und Lookups). Ich hob die entsprechenden Funktionen. Sie ziemlich eng mit den Stoppuhr Zeitmetriken stimmen oben.
Sie sehen, dass die Wörterbuch-Lookups sind viel schneller als binäre Suche, und (wie erwartet) die Differenz ist umso ausgeprägter, je größer die Sammlung. Also, wenn Sie eine angemessene Hashfunktion (ziemlich schnell mit wenigen Kollisionen) haben, ein Hash-Lookup sollte in diesem Bereich für Sammlungen binären Such schlagen.
Die Antworten von Bobby, Bill und Corbin sind falsch. O (1) ist nicht langsamer als O (log n) für eine feste / n beschränktes:
log (n) konstant ist, so ist es auf der konstanten Zeit abhängig ist.
Und für eine langsame Hash-Funktion, je von md5 gehört?
Der Standard-String-Hashing-Algorithmus berührt wahrscheinlich alle Zeichen und kann leicht 100-mal langsamer sein als der Durchschnitt vergleicht für langen String-Schlüssel. Kenne ich schon.
Sie könnten in der Lage sein (teilweise) eine Radix verwenden. Wenn Sie in 256 ungefähr gleiche Größe Blöcke aufteilen können, sind Sie bei 2k 40k binäre Suche suchen. Das ist wahrscheinlich viel bessere Leistung bieten.
[Bearbeiten] Zu viele Menschen stimmen auf, was sie nicht verstehen.
String vergleicht für binäre Suche sortiert Sets haben eine sehr interessante Eigenschaft: sie langsamer bekommen, je näher sie an das Ziel zu bekommen. Zunächst werden sie auf dem ersten Zeichen brechen, am Ende nur auf dem letzten. eine konstante Zeit für sie unter der Annahme ist falsch.
Die einzige vernünftige Antwort auf diese Frage lautet: Es hängt davon ab. Es hängt von der Größe der Daten, die Form Ihrer Daten, die Hash-Implementierung, Ihre binären Such Implementierung und wo Ihre Daten leben (auch wenn es nicht in der Frage erwähnt wird). Ein paar andere Antworten sagen, so viel, so konnte ich diese einfach löschen. Allerdings könnte es schön zu teilen, was ich von Feedback zu meiner ursprünglichen Antwort gelernt habe.
- Ich schrieb: " Hash-Algorithmen sind O (1), während binäre Suche O (log n) ." - Wie in den Kommentaren erwähnt, Notation Schätzungen Komplexität Big O, nicht beschleunigen. Das ist absolut wahr. Es ist erwähnenswert, dass wir in der Regel Komplexität verwenden, um ein Gefühl eines Algorithmus Zeit und Platzbedarf zu erhalten. So, während es töricht ist die Komplexität zu übernehmen ist streng die gleiche wie Geschwindigkeit, Komplexität Schätzen ohne Zeit und Raum in der Rückseite Ihres Geistes ungewöhnlich ist. Meine Empfehlung:. Vermeiden Big O-Notation
- Ich schrieb: „ So wie n gegen unendlich ...“ - Es geht um das Dümmste, was ich in einer Antwort enthalten haben könnte. Infinity hat nichts mit dem Problem zu tun. Sie erwähnen eine Obergrenze von 10 Millionen. Ignorieren Unendlichkeit. Da die Kommentatoren weisen darauf hin, sehr große Zahlen werden alle möglichen Probleme mit einem Hash erstellen. (Sehr große Zahlen machen nicht binäre Suche einen Spaziergang im Park auch nicht.) Meine Empfehlung: nicht unendlich erwähnen, wenn Sie unendlich bedeuten .
- Auch aus den Kommentaren: passen Standard-String-Hashes (? Sie Strings Hashing Sind Sie nicht erwähnt.), Datenbankindizes sind oft b-Bäume (zum Nachdenken). Meine Empfehlung: Sehen Sie alle Optionen. Betrachten wir andere Datenstrukturen und Ansätze ... wie ein altmodischer trie (zum Speichern und Abrufen strings) oder ein R-tree (für räumliche Daten) oder a MA-FSA (Minimal Azyklisches Finite State Automaton - kleiner Speicherplatzbedarf).
Kommentare gegeben, könnte man davon ausgehen, dass Menschen, die Hash-Tabellen verwenden, werden gestört. Sind Hash-Tabellen rücksichtslos und gefährlich? Sind diese Leute verrückt?
Es stellte sich heraus, dass sie nicht. So wie binäre Bäume auf bestimmte Dinge gut sind (in Ordnung Daten Traversal, Speichereffizienz), Hash-Tabellen haben ihre Zeit als auch zu glänzen. Insbesondere können sie bei der Verringerung der Zahl der sehr gut liest benötigt, um Ihre Daten zu holen. Ein Hash-Algorithmus kann eine Position erzeugen und direkt auf mich im internen Speicher oder auf der Festplatte springen, während binäre Suchdaten bei jedem Vergleich lesen, um zu entscheiden, was als nächstes zu lesen. Jede Lese hat das Potential für eine Cache-Miss, die eine Größenordnung (oder mehr) langsamer als ein CPU-Befehl.
Das ist nicht zu sagen, Hash-Tabellen sind besser als binäre Suche. Sie sind nicht. Es ist auch nicht zu deuten darauf hin, dass alle Hash und binäre Such Implementierungen gleich sind. Sie sind nicht. Wenn ich einen Punkt haben, dann ist es dies: beide Ansätze gibt es für einen Grund. Es liegt an Ihnen zu entscheiden, welche für Ihre Bedürfnisse am besten ist.
Original Antwort:
Hash-Algorithmen sind O (1), während binäre Suche O (log n) ist. So wie n gegen unendlich geht, verbessert die Hash-Leistung auf binäre Relativ Suche. Ihre Laufleistung variieren in Abhängigkeit von n, Ihre Hash Implementierung und Ihre binäre Such Umsetzung.
Interessante Diskussion über O (1) . Paraphrasiert:
O (1) bedeutet nicht unmittelbar. Es bedeutet, dass die Leistung nicht ändern, wenn die Größe von n wächst. Sie können einen Hash-Algorithmus entwerfen das ist so langsam niemand es benutzen würde, und es wäre immer noch O (1) sein. Ich bin ziemlich sicher, dass .NET / C # leidet nicht an kostspie Hashing jedoch;)
Wenn Ihr Satz von Objekten ist wirklich statisch und unveränderlich, können Sie einen perfekte Hash verwenden können, um erhalten O (1) Leistung garantiert. Ich habe gperf ein paar Mal erwähnt, obwohl ich nie Gelegenheit gehabt haben, es zu benutzen ich selbst.
Hashes sind in der Regel schneller, obwohl Binärsuchen besser Worst-Case-Eigenschaften haben. Ein Hash-Zugang ist in der Regel eine Berechnung einen Hash-Wert zu erhalten, die „Eimer“ ein Datensatz in sein wird, um zu bestimmen, und so wird die Leistung hängt in der Regel ab, wie gleichmäßig die Datensätze verteilt sind, und die Methode verwendet, um den Eimer zu suchen. Eine schlechte Hash-Funktion mit einer linearen Suche durch die Eimer (ein paar Eimer mit einer ganzen Menge von Datensatz zu verlassen) wird in einer langsamen Suche führen. (Auf der dritten Seite, wenn Sie einen Datenträger gerade lesen, anstatt Speicher sind die Hash-Buckets wahrscheinlich zusammenhängend sein, während der binäre Baum ziemlich garantiert nicht-lokalen Zugriff.)
Wenn Sie in der Regel schnell wünschen, verwenden Sie den Hash. Wenn Sie wirklich begrenzte Leistung garantiert werden sollen, können Sie mit dem binären Baum gehen.
Überrascht niemand erwähnt Cuckoo Hashing, die garantiert O (1) und im Gegensatz zu perfekten Hashing bietet der Lage ist, den gesamten Speicher mit ihm teilt, wo so perfekt Hashing mit garantierten O kann am Ende (1), aber verschwenden desto größer Teil ihrer Zuteilung. Der Nachteil? Einführungszeit kann sehr langsam sein, zumal die Anzahl der Elemente erhöht, da alle die Optimierung während des Einführungsphase durchgeführt werden.
Ich glaube, einige Version davon in Router-Hardware für IP-Lookups verwendet wird.
Siehe Link-Text
Wörterbuch / Hashtable wird mit mehr Speicher und mehr Zeit, um Array Vergleich zu füllen dauert. Aber Suche erfolgt schneller durch Wörterbuch anstatt Binäre Suche innerhalb des Arrays.
Hier sind die Zahlen für 10 Millionen von Int64 Gegenstände zu suchen und zu bevölkern. Dazu ein Beispielcode können Sie selbst ausführen.
Wörterbuch Speicher: 462.836
Array Speicher: 88376
Populate Wörterbuch: 402
Bestücken Array: 23
Suchen Wörterbuch: 176
Suchen Array: 680
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace BinaryVsDictionary
{
internal class Program
{
private const long Capacity = 10000000;
private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue);
private static readonly long[] Arr = new long[Capacity];
private static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Dict.Add(i, i);
}
stopwatch.Stop();
Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Arr[i] = i;
}
stopwatch.Stop();
Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = Dict[i];
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = BinarySearch(Arr, 0, Capacity, i);
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds);
Console.ReadLine();
}
private static long BinarySearch(long[] arr, long low, long hi, long value)
{
while (low <= hi)
{
long median = low + ((hi - low) >> 1);
if (arr[median] == value)
{
return median;
}
if (arr[median] < value)
{
low = median + 1;
}
else
{
hi = median - 1;
}
}
return ~low;
}
}
}
Ich vermute stark, dass in einem Problem der Größe eingestellt ~ 1M, Hashing schneller wäre.
Nur für die Zahlen:
eine binäre Suche erfordern würde ~ 20 vergleicht (2 ^ 20 == 1 M)
ein Hash-Lookup würde 1-Hash-Berechnung auf dem Suchschlüssel benötigen und möglicherweise eine Handvoll danach vergleicht mögliche Kollisionen zu lösen
Edit: die Zahlen:
for (int i = 0; i < 1000 * 1000; i++) {
c.GetHashCode();
}
for (int i = 0; i < 1000 * 1000; i++) {
for (int j = 0; j < 20; j++)
c.CompareTo(d);
}
Zeiten: c = "abcde", d = "rwerij" Hash-Code: 0,0012 Sekunden. Vergleichen: 2,4 Sekunden.
Disclaimer: Eigentlich im Vergleich zu einem binären Lookup einen Hash-Lookup-Benchmarking könnte besser sein, als dieser nicht-ganz-relevanten Test. Ich bin nicht einmal sicher, ob GetHashCode wird unter der Motorhaube memoized
Ich würde sagen, dass es in erster Linie auf der Leistung der Hash-abhängig und Methoden vergleichen. Wenn zum Beispiel String-Schlüssel verwendet, sind sehr lang, aber zufällig, ein Vergleich wird immer ein sehr schnelles Ergebnis liefern, aber eine Standard-Hash-Funktion wird die gesamte Zeichenfolge verarbeiten.
Aber in den meisten Fällen die Hash-Karte sollte schneller sein.
Ich frage mich, warum niemand erwähnt perfekt Hashing .
Es ist nur relevant, wenn Ihr Datensatz für eine lange Zeit festgelegt ist, aber was sie tut es die Daten analysieren und eine perfekte Hash-Funktion konstruieren, die keine Kollisionen gewährleistet.
Recht ordentlich, wenn Ihr Datensatz konstant ist, und die Zeit, die Funktion ist klein im Vergleich zur Anwendung der Laufzeit zu berechnen.
Es hängt davon ab, wie Sie behandeln Duplikate für Hash-Tabellen (wenn überhaupt). Wenn Sie nicht möchten Raute-Taste Duplikate (keine Hash-Funktion ist perfekt) zu ermöglichen, bleibt es O (1) für die Primärschlüsselsuche aber hinter für den „richtigen“ Wert suchen können teuer sein. Die Antwort ist dann, theorically die meiste Zeit, Hashes sind schneller. YMMV je nachdem, welche Daten Sie dort setzen ...
Hier es beschrieben ist, wie Hashes gebaut werden und weil die Universum des Schlüssels ist recht groß und Hash-Funktionen gebaut werden als „sehr injektiv“, so dass Kollisionen selten die Zugriffszeit für eine Hash-Tabelle geschehen ist nicht O (1) eigentlich ... es ist etwas, basierend auf einigen Wahrscheinlichkeiten. Aber, ist es vernünftig zu sagen, dass die Zugriffszeit eines Hash ist fast immer weniger als die Zeit O (log_2 (n))
Natürlich Hash ist am schnellsten für eine so große Datenmenge an.
Eine Möglichkeit, es zu beschleunigen, noch mehr, da selten die Daten ändern, ist programmatisch Ad-hoc-Code zu erzeugen, um die erste Schicht der Suche nach einer riesigen Switch-Anweisung zu tun (wenn Ihr Compiler kann damit umgehen), und dann Zweig aus den resultierenden Eimern zu suchen.
Die Antwort hängt davon ab. Lets denken, dass die Anzahl der Elemente ‚n‘ sehr groß ist. Wenn Sie schreiben eine bessere Hash-Funktion, die weniger Kollisionen gut sind, dann ist Hashing das beste.
Hinweis, dass
Die Hash-Funktion wird nur einmal beim Suchen ausgeführt, und es leitet an dem entsprechenden Eimer. So ist es kein großer Aufwand, wenn n hoch ist.
Problem in Hashtable:
Aber das Problem in Hash-Tabellen, wenn die Hash-Funktion ist nicht gut (mehr Kollisionen geschehen), dann ist die Suche nicht O (1). Es neigt dazu, zu O (n), weil in einem Eimer Suche eine lineare Suche ist. Kann sein, schlimmer als ein binärer Baum.
Problem in Binärbaum:
In Binärbaum, wenn der Baum nicht ausgeglichen ist, es neigt auch dazu, zu O (N). Wenn Sie zum Beispiel 1,2,3,4,5 in einen binären Baum eingefügt, die eher eine Liste sein würden.
So,
Wenn Sie eine gute Hash-Methodik sehen, verwenden Sie eine Hash-Tabelle
Wenn nicht, sollten Sie besser einen binären Baum verwendet wird.
Dies ist ein Kommentar zu Bills Antwort, weil seine Antwort obwohl seine falsch so viele upvotes selbst hat. Also musste ich diese veröffentlichen.
Ich sehe viele Diskussionen über das, was ist die schlimmste Fall Komplexität einer Lookup in hashtable, und was als abgeschrieben Analyse / was nicht. Überprüfen Sie bitte den Link unten
Hash-Tabelle Laufzeitkomplexität (Einfügen, Suchen und Löschen)
worst case Komplexität ist O (n) und nicht O (1), im Gegensatz zu dem, was Bill sagt. Und so sein O (1) Komplexität nicht planmäßig abgeschrieben, da diese Analyse kann nur für den schlimmsten Fällen verwendet werden (auch seine eigene Wikipedia-Link sagt so)
Diese Frage ist komplizierter als der Umfang der reinen Leistung des Algorithmus. Wenn wir die Faktoren entfernen, die binäre Suchalgorithmus mehr Cache-freundlich ist, ist der Hash-Lookup im allgemeinen Sinne schneller. Der beste Weg, um gedacht ist, ein Programm zu erstellen und die Compiler-Optimierungsoptionen deaktivieren, und wir konnten feststellen, dass das Hash-Lookup schneller seine Algorithmus Zeiteffizienz gegeben ist, ist O (1) im allgemeinen Sinne.
Aber wenn Sie die Compiler-Optimierung ermöglichen, und versuchen, den gleichen Test mit kleineren Anzahl der Proben sagen weniger als 10.000, die binäre Suche besser als den Hash-Lookup durch Vorteile seiner Cache freundliche Datenstruktur nehmen.
