nicht angemeldet
Guten Tag zusammen,
ich versuche im Moment (eigentlich nur aus reinem Interesse), einen Algorithmus zu
implementieren, der es ermöglicht, eine Hash-Tabelle in einer Datei zu speichern. Dazu
nutze ich eine Hash-Funktion von Bob Jenkins, die Hash-Werte berechnet, die regelmäßig im
32-Bit-Bereich verteilt sind, so dass sich die Duplikate in Grenzen halten. Allerdings habe
ich ein Problem dabei: ich habe mir überlegt, dass ich die Hash-Tabelle in den ersten
2^32 * Größe des Datentyps Byte der Datei die Tabelle Speichere, wobei ich die Zuordnung
Hash-Sume => Wert indirekt machen wollte. Das heisst: ich wollte die Hash-Summe direkt
umsetzen in eine Position in der Datei. An dieser Position steht allerdings dann nur ein
»Pointer«, also eine Positions-Beschreibung zu den zugeordneten Daten. Ist das dort
gespeicherte Muster ein 0-Muster, so ist der Eintrag unbesetzt.
Daraus ergibt sich allerdings ein ziemliches Problem: bei einer Tabellen-Größe von 32 Bit
ergeben sich maximal 4294967296 Einträge. Speichere ich die Daten-»Pointer« auch als
32-Bit-Werte, so ergibt sich für die physikalische Größe der Hashtabelle etwa 16GB. Setze
ich die Hashtabelle jedoch kleiner an, so muss ich, wenn mehr Werte gespeichert werden als
die Hashtabelle gross ist, unter Umständen die komplette Datei reorganisieren (Daten weiter
nach unten schieben), was wiederum eine Menge Aufwand ist.
Meine Frage ist nun: gibt es da keinen besseren Weg? Ich glaube nicht, dass z. B.
Hash-Indizes von Datenbanken so arbeiten.
Freundliche Grüße,
Surak