Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Fr Jul 18, 2025 08:11

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 9 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Hash Tabellen
BeitragVerfasst: Do Jul 10, 2008 03:35 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
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~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 05:45 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
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~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 06:22 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
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~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 06:50 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 27, 2005 12:44
Beiträge: 393
Wohnort: Berlin
Programmiersprache: Java, C++, Groovy
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 06:57 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
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~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 10:01 
Offline
DGL Member
Benutzeravatar

Registriert: Di Sep 06, 2005 18:34
Beiträge: 362
Wohnort: Hamburg
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)


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 10:48 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
Shaijan hat geschrieben:
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 ;) ).

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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 20:08 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2623
Wohnort: Berlin
Programmiersprache: Go, C/C++
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Jul 10, 2008 21:32 
Offline
DGL Member
Benutzeravatar

Registriert: So Jun 04, 2006 12:54
Beiträge: 263
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


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 9 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.009s | 16 Queries | GZIP : On ]