Hashmap und map
-
Hi,
Wo ist der Unterschied zw. einer std::map und einer hash_map wie sie z.B. bei STL-Port dabei ist.
thx
-
std::map ist als baum implementiert
std::hash_map als hash-table
-
aha, danke.
Also ich habe mich ein wenig informiert und habe gelesen das eine hash_map schneller ist, wozu brauche ich dann eigentlich noch eine normale map wenn ich eine hash_map haben kann ?
thx
-
eine Hashtable hat im Worstcase einen O(n) Lookup, ein balancierter Suchbaum immer O(log n)
-
Ha. Ich habe einen Hash implementiert, der im worst case ebenfalls o(log n) braucht. Leider ist er trotzdem etwas langsamer, als beispielswiese der SGi-Hash. Verschiedene Zeitmessungen bei denen alle möglichen für einen Hash üblichen Funktionen verwendet wurden zeigten, das mein Hash im durchschnitt etwas 1,5 mal so lang brauchte
Die Hash-Map verwendet kleine Bäume zum speichern der Daten. Sollte die Hash-Funktion also für mehrere Daten den selben Index ausspuken wirds 'ne Suchaktion mit o(log n).Eigentlich liegt der Unterschied in der Verwendung. Wenn man die Daten sortiert Braucht, verwendet man eine Map, wenn die Reihenfolge egal ist einen Hash.
-
hash_map ist kein Standard-C++, d.h. es ist nicht zwingend bei jedem Compiler dabei.