Hi,

kann mir mal jemand erklären wie genau Hash-Tabellen funktionieren?
Ich brauche grad eine und finde für C++ keine wirklich brauchbaren die meinen bedürfnissen entsprechen, also dacht ich mir "kann ja nicht so schwer sein so nen ding zu schreiben"..

Aber nach der recherche blick ich grad garnichtmehr durch wie die dinger funktionieren (was auch an der uhrzeit liegen mag..).

Nehmen wir als beispiel mal an das der Key ein Integer ist, dann kann es ja nicht sinn der hash-map sein, einfach den internen array von vorn nach hinten durchzurennen und zu schauen ob der key gefunden wurde, oder?
Das ding ist doch schon irgendwie optimiert.. oder?


Aya~

Hi nochmal,

ok hab es jetzt doch noch verstanden und umgesetzt, allerdings habe ich noch ein kleines problem..

Man muß ja irgendeinen hash-Wert erzeuge anhand dessen das ganze dann in die tabelle einsortiert wird.
Gibt es da irgendeine tolle möglichkeit sowas für alle möglichen typen zu machen?

Also so das egal ob der key ein integer, string oder record ist immer eine eindeutige zahl daraus generiert wird..?
Oder muß man da für jeden typ ne eigene hash-wert generierung basteln...?

Aya~

Und nochmal ich,

jetzt hab ich mir die letzte frage auchnoch selbst beantwortet

Hier sind einige gute Hash funktionen:
http://www.fantasy-coders.de/projects/gh/html/x435.html

Die hab ich eingebaut und nu klappt alles wie es soll

Aya~

Hallo,

warum nimmst du nicht einfach die std::map?
Du brauchst nur "map.h" includieren und kannst dir jede beliebige Hashtabelle definieren, z.B.

typedef std::map< string, double > myMap;
myMap m;

Zuweisungen funktionieren dann ganz einfach so : m["abcde"] = 4.0.

Viele Grüße
dj3hut1

Hi,

weil laut einiger quellen im internet die std::map nicht auf jedem system standardmäßig vorhanden ist, bzw probleme mit manchen compilern macht..

Aber so wie ich es jetzt hab klappt es ja und ist aus eigener hand = ist mir eh lieber

Aya~

Hi ...

du solltest wo du kannst die STL Typen verwenden, da diese wirklich gut optimiert sind.
Eine eigene Klasse zu schreiben ist hier aber auch nicht so verkehrt.
Die STL map ist nämlich gar keine richtige hash_map wenn ich mich recht erinnere. Ich glaube die benutzt eine Baumstruktur zum anordnen und finden der keys.
Allerdings gibt es die hash_map, diese ist aber nur eine Extension und gehört damit nicht zum C++ Standard, trotzdem kann man sie mit fast jedem Compiler benutzen.
Du solltest dir also mal anschaun ob du die hash_map (unter gcc <ext/hash_map.h>) verwenden kannst für deine Zwecke.

Und wenn du irgendwelche Klassen o.ä. im C++ Standard vermisst lohnt sich auch immer ein Blick in die Boost Library (auch wenn die keine hash_map hat ).

Gruß
Shai

_________________
Der Mensch hat neben dem Trieb der Fortpflanzung und dem zu essen und zu trinken zwei Leidenschaften: Krach zu machen und nicht zuzuhören. (Kurt Tucholsky)
Schwabbeldiwapp, hier kommt die Grütze. (Der Quästor)

Na ja, das seh ich anders.. ich versuche soweit wie möglich komplett auf fremd-libs zu verzichten und alles selbst zu machen.
Das mag zwar hier und da mal nicht ganz so extrem performant optimiert sein wie Boost oder STL, aber dafür weiß ich genau was da passiert. Und sollte die performance mal irgendwo ein problem werden kann ich ja immernoch umstellen auf Boost/STL.

Wenn ich überall sofort nach fertigen lösungen suche bleibt für mich der lern effekt auf der strecke..

Ist ja im grunde das gleiche wie mit ner 3D Engine, es gibt da genug super gut optimierte etc.. wieso aber wollen wir alle unsere eigene schreiben?

Aya

std::map läuft überall, std:hashmap läuft nicht überall, es ist sogar nur in einigen compilern drin, da es ein hp standard ist.
Hashfunktionen werden in der Regel in C++ snippets angeboten aber die daraus folgenden Hashtables werden in der Regel selber geschrieben, ich kenne kein C++ Projekt wo nicht eigene Templates für Hashtables dabei sind. Die teile in der STL sind einfach viel zu lahm.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

ganz entscheidend ist, das die hashfunktion zu den daten passen muss, es ist ein unterschied ob man text, ints, floats oder objekte hashen will.

_________________
Lumina plattform unabhängige GLSL IDE