Hashtable-Implementierung: Einträge direkt adressieren



  • Ich implementiere gerade zu Lernzwecken eine einfache DHT in C99. Ich habe verstanden, dass der Sinn einer Hashtable darin besteht, die Einträge der Datenstruktur schnell anzuspringen, ohne diese Eintrag für Eintrag durchsuchen und jeweils die Schlüssel mit dem gesuchten Schlüssel vergleichen zu müssen.

    Nun kann ich eine einfache Hashfunktion schreiben, welche mit Multiplikation, Addition und Modulo einen mehr oder weniger guten Hash, innerhalb eines vorgegebenen Wertebereichs, erzeugen kann. Ein Array kann ich so verwenden, dass die Speicherstellen darin jeweils den Hashwerten entspricht, ich also den Index des Arrays als direkte Zugriffsmethode für den gesuchten Wert nutze.

    Das funktioniert alles, wenn auch nicht sehr kollissionsfrei, für kleine Arrays (z.B. mit bis zu 1000 Einträgen). Nun frage ich mich aber wie eine "richtige" Hashtable das direkte ansprechen des Zieleintrags löst. Schließlich kann man für einen viel längeren Hash nicht ewig lange Arrays anlegen. Auch funktioniert die Index-Methode nicht für alphanumerische Hashwerte (myhashtable[14ffab]).
    Wer kann mir sagen wie man das in C noch lösen könnte?

    Viele Grüße,

    Solevita



  • Solevita schrieb:

    Das funktioniert alles, wenn auch nicht sehr kollissionsfrei, für kleine Arrays (z.B. mit bis zu 1000 Einträgen). Nun frage ich mich aber wie eine "richtige" Hashtable das direkte ansprechen des Zieleintrags löst. Schließlich kann man für einen viel längeren Hash nicht ewig lange Arrays anlegen.

    Wieso nicht? Aber das ist eine falsche Frage, du wählst zuerst die Tabellengröße und dann die Hashfunktion so, dass sie (möglichst gut verteilt) alle Indizes erreicht.

    Auch funktioniert die Index-Methode nicht für alphanumerische Hashwerte (myhashtable[14ffab]).

    Wieso nicht? Es ist doch pupsegal, was die Eingabe deiner Hashfunktion ist, das Ergebnis ist ein Index.

    Wer kann mir sagen wie man das in C noch lösen könnte?

    Wüsste nicht, was das mit C zu tun hat.



  • Danke für deine Antwort!

    Naja, ich habe einfach das praktische Problem, dass mein Hash ja alphanumerisch sein kann (und damit nicht als Index für ein C-Array taugt).

    Beispiel:

    SHA-1("hallo") = fd4cef7a4e607f1fcc920ad6329a6df2df99a4e8

    Grüße,

    Solevita



  • Was du als alphanumerisch bezeichnest sind Hexadezimal-Zahlen.
    Und klar eignen die sich als Index, da sie nur eine andere Darstellung von Werten sind.

    Allerdings sind die 160-Bit vom SHA-1 doch arg viel.
    Aber das 14ffab frisst der Compiler, wenn du ein 0x voran stellst.

    Wenn dein Hashwert zu groß ist, ist dein Algorithmus für deine Zwecke nicht geeignet. Nimm einen anderen.



  • Ja das kam mir auch etwas viel vor, hab irgendwo gelesen dass BitTorrent SHA-1 mit 160 Bits verwendet und das kam mir auch sehr sehr viel vor. Daher die Bemerkung dass solche ewig lange Arrays doch schwierig werden. Bei BitTorrent handelt es sich ja aber auch um eine Distributed Hash Table, und da wird nicht jeder Node die gesamte Tabelle vorhalten. 😉 Vermutlich wird die eher segmentiert sein.

    Danke Dirk, du hast vollkommen recht, ich hätte selbst drauf kommen müssen!! 😉

    Grüße,

    Solevita



  • Leseempfehlung bezüglich der Hashkollisionen: http://de.wikipedia.org/wiki/Hashtabelle#Kollisionen



  • Danke Patrick, ja gemäß diesem Artikel werde ich kein offenes Hashing, sondern Verkettung/Buckets mittels Linked-List als Auflössungsstrategie bei Kollissionen nutzen. Schön, dass das dort nocheinmal so explizit stand. 🙂


Log in to reply