Hash Funktion? Oder wofür ist dieser Code.

Ersteinmal ein kurzes Hallo.

Ich habe ein wohl eher ungewöhnliches Problem.
Ich schreibe eigentlich in RealBasic und VB.Net.

Für mein aktuelles Projekt, muß ich diverse Daten aus einer Datei lesen.

Für diesen Zweck hat der ersteller dieser Dateien, eine Info bereitgestellt, die sich aber leider auf C bezieht.

Da ich von C aber keine Ahnung habe, diese Hash Funktion aber gerne nachbauen würde, wollte ich fragen, was genau das folgende bedeutet.

Ich hoffe ihr könnt mir weiterhelfen.

struct startBlock
{
    unsigned check;                 // 0xABCDDCBA
    unsigned IDTableOffset;
    unsigned nHashTableEntries;
    unsigned hashTableOffset;
    unsigned dataOffset;
};

struct hashTableEntry
{
    unsigned hashedID;
    unsigned IDOffset;
    unsigned dataOffset;
};

int hashVal(char *c)
{
    int hv=0;
    while (*c)
    {
        hv=(hv<<1)^(hv>>20)^*(c++);
    }

    return hv;
}

cheopz

prinzipiell vielleicht so?

function hashval(s as string) as integer
    dim i as integer, hv as integer
    i = 0
    hv = 0
    while i < s.count
        hv = (hv<<1)^(hv>>20)^s(i)
    end while
end function

Danke erstmal. Der Sinn ist mir momentan noch nicht klar, aber ich kann es wenigsten mal lesen.

BigGranu schrieb:

Danke erstmal. Der Sinn ist mir momentan noch nicht klar, aber ich kann es wenigsten mal lesen.
Nur was macht ">>" ? und "^"? die kenne ich garnicht.

cheopz

Da kommst du schon noch dahinter.

<<1 multipliziert mit 2

20 dividiert durch 1048576
^ ist ein bitweises XOR

Du solltest auch überlegen, ob dir hv in der alten Implementierung hin und wieder überläuft, das könnte ja bei dem <<1 passieren (wäre aber ein Armutszeugnis). In dem Fall müsstest du noch sizeof(int) kennen, und den Überlauf simulieren.

Es ist aber schon seltsam, dass du die VB-Bitoperatoren nicht kennst. :p

cheopz schrieb:

Du solltest auch überlegen, ob dir hv in der alten Implementierung hin und wieder überläuft, das könnte ja bei dem <<1 passieren (wäre aber ein Armutszeugnis).

bei dem >>20 geht noch viel mehr verloren, das ist aber wohl gewollt.

cheopz

bei dem >>20 geht noch viel mehr verloren, das ist aber wohl gewollt.

Sehr qualifizierter Kommentar!

überläuft

Bei >>20 kann er nur unterlaufen, aber das ist egal, wie sogar dir einleuten wird, weil wenn die hochwertige (linke) Datentyp-Grenze schon variabel ist, zumindest die rechte unverrückbar feststeht.

cheopz schrieb:

Bei >>20 kann er nur unterlaufen, aber das ist egal, wie sogar dir einleuten wird, weil wenn die hochwertige (linke) Datentyp-Grenze schon variabel ist, zumindest die rechte unverrückbar feststeht.

das 'nur' finde ich leicht untertrieben. es werden immer 20 bits weggeschmisssen, der informationsverlust ist viel grösser als bei <<1. also ein echt mieser hash-algo, da wäre selbst stumpfes addieren aller werte besser.

Der Algo ist ja nicht von mir.

Er wurde so wie im ersten Post in der entsprechenden Datei mitgeliefert.

Ich versuche jetzt die Datei mit RealBasic zu entpacken, was bis auf einen bestimmten Bereich auch klappt.

Da eben gesagt wird, es sei für C Programmierer hatte ich hier mal gefragt ob ihr etwas damit anfangen könnt.

So wies aussieht ist der Code aber nicht gerade Sinnvoll und damit kann ich ihn eben nicht nachbauen.

Trotzdem Danke für die Hilfe hier.

cheopz

So wies aussieht ist der Code aber nicht gerade Sinnvoll und damit kann ich ihn eben nicht nachbauen.

Wie kommst du denn auf sowas? Man kann sogar den schwachsinnigsten Code nachbauen, und so schlimm ist deiner nun auch wieder nicht. Wenn du die Sache mit den Bitoperatoren verstanden hast, ist alles gut; wenn nicht, solltest du sagen, was dir nicht klar ist.

EDIT:
mit <<1 kann gar kein Informationsverlust auftreten, wenn der Wert nicht überläuft (nichts anderes habe ich gesagt). Warum muss ich hier dogmatische Diskussionen mit Unregs führen, wenn ursprünglich ein Problem zu lösem war?

hellihjb

hv=(hv<<1)^(hv>>20)^*(c++)

es werden immer 20 bits weggeschmisssen, der informationsverlust ist viel grösser als bei <<1. also ein echt mieser hash-algo

bloedsinn.
lesen.

hellihjb schrieb:

lesen.

selber lesen. hv=(hv<<1)^(hv>>20)(c++)* ist keine CRC berechnung, sondern nur so'n schäbiger hashwert.

text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
text text text text text text text text text
(sorry, leider nötig wegen der doofen spamkontrolle)

hellihjb

keine CRC berechnung, sondern nur so'n schäbiger hashwert

du darfst gerne mal kompetent erlaeutern wo deiner meinung nach der unterschied zwischen einer hasing- und einer crc- oder einer anderen streuwert-funktion liegt, insbesondere in hinblick auf kollisionen.
der link geht im uebrigen auf polynomdivision und deren vereinfachung auf eine xor-verknuepfung ein, an deren verstaendnis es hier anscheinend primaer mangelt.
der interessierte leser kann in diesem zusammenhang am ende des artikels auch ruhig mal auf den verweis zu hash-funktionen klicken...

hellihjb schrieb:

keine CRC berechnung, sondern nur so'n schäbiger hashwert

du darfst gerne mal kompetent erlaeutern wo deiner meinung nach der unterschied zwischen einer hashing- und einer crc- ... funktion liegt.

eine CRC funktion ist auch immer eine hashfunktion, aber nicht jede hashfunktion ist eine CRC-funktion. bei eventuellen unklarheiten klicke einfach auf die von dir geposteten links

hellihjb

ah, schoen, du hast es gelesen und was dabei gelernt.
das freut mich sehr