ist diese hashfunktion kollisionsfrei?

the_menace

Hallo,
ich habe aus dem sedgewick eine funktion nachimplementiert, und wollte wissen ob fuer meine hashtable diese funktion kollisionsfrei ist.
vor ab: ich hab eine hashtable, die schluessel fuer die eintraege ermittle ich durch die funktion, die byteweise den eintrag (oder den schluessel dafuer) einliest.

unsigned long hashing(void *object, unsigned long length, unsigned int size) {
	unsigned long i = 0;
        unsigned long wert = 0;
	unsigned char *ptr = NULL; /* nur auf char gecasted, damit compiler nicht mecker */
	ptr = object;
	for(i = 0; i < length; i++) {
		wert = (wert * 256 + ptr[i]) % size;
	}
	return wert;
}

Ich habe ein Objekt (ein struct, was auch immer, das ist genau length bytes gross, und beginnt bei object. das errechne ich. ich habe genau size eintraege in der hashtabelle und size ist immer eine primzahl (5, 11, 17, 37, ...)

jetzt bin ich mir nicht ganz sicher, ob die funktion nicht doch 2 unterschiedliche byteobjekte auf den gleichen schluessel abbildet. Was meint ihr dazu?

c.rackwitz

damit hast du nur die letzten 7 bytes (wenn du 32 bit bist) gehasht, denn irgendwann werden die anfangswerte aus deinem register rausgeschoben.

wozu brauchst du size?

kollisionen wirst du immer haben. theoretisch kannst du das einfach nicht ausschliessen.

guck dir crc32 an.

the_menace

stimmt ja. aber ich habe eine laengen begrenzung!
also, wenn size zb 17 ist, so weiss ich schon vorher, das es genau 4 Bytes sind, die ich hashe. wenn size 37 ist, so hashe ich genau 5 Bytes.

ist es denn dann kollisionsfrei?
(also, dass 2 verschiedene nicht auf das gleiche abgebildet werden?)

c.rackwitz

das modulo macht die sache schwerer, aber an sich kann man fuer deinen algorithmus relativ schnell kollisionen erzeugen.

int main(void)
{
	int irgendwas = 42;
	char *foo = "hallo welt";
	char *bar = "gegruesst, welJ";
	printf("%ld\n", hashing((void*)foo, strlen(foo), irgendwas));
	printf("%ld\n", hashing((void*)bar, strlen(bar), irgendwas));
	return 0;
}

das modulo macht die sache zusaetzlich schlimmer, denn es schraenkt den wertebereich ein. kollisionen gehen so viel schneller.

volkard

c.rackwitz schrieb:

das modulo macht die sache zusaetzlich schlimmer, denn es schraenkt den wertebereich ein. kollisionen gehen so viel schneller.

das kannst du laut sagen.
bei size==256 macht
wert = (wert * 256 + ptr[i]) % size;
das gleiche wie
wert = ptr[i];
das ist fatal.

nee, % ist viel zu teuer, um es innerhalb der hash-schleife zu verwenden.
also statt

for(i = 0; i < length; i++) {
        wert = (wert * 256 + ptr[i]) % size;
    }
    return wert;

besser

for(i = 0; i < length; i++) {
        wert = (wert * 256 + ptr[i]);
    }
    return wert%size;

und dazu hat man den vorteil, daß die volle breite des int beim hashen verwendet wird und nicht vorzeitog die feinsten bits abgesäbelt werden.

und nun zum multiplikater. wenn er eine gerade zuah ist, schubst er bits unwiederbringlich raus. das ist bäh, bäh.

also nimm ne ungerade und schon klappts.

for(i = 0; i < length; i++) {
        wert = (wert * 31 + ptr[i]);
    }
    return wert%size;

net 0

guckst ihr: http://www.fantasy-coders.de/projects/gh/html/x435.html

the_menace

also, dein kollisionsbeispiel geht schon mal nicht, c.rackwitz, weil ich ja *genau* 4 Bytes teste. Nicht mehr und nicht weniger.

Wie soll dann

char *foo = "hallo welt";
char *bar = "gegruesst, welJ";

funktionieren?

volkard:

wert = (wert * 31 + ptr[i]);

ich dachte, die 256 * wert seien dazu da, um den wert "weiter zu shiften" wie beim hornerschema? ich kapiere nicht so ganz den sinn, wenn man das so macht..

c.rackwitz

achso, na dann...

#include <stdio.h>
#include <string.h>

unsigned long hashing(void *object, unsigned long length, unsigned int size) {
    unsigned long i = 0;
        unsigned long wert = 0;
    unsigned char *ptr = NULL; /* nur auf char gecasted, damit compiler nicht mecker */
    ptr = object;
    for(i = 0; i < length; i++) {
        wert = (wert * 256 + ptr[i]) % size;
    }
    return wert;
}

int main(void)
{
	int irgendwas = 42; // beliebig, echt.
	char *foo = "welt";
	char *bar = "welJ";
	printf("%ld\n", hashing((void*)foo, strlen(foo), irgendwas));
	printf("%ld\n", hashing((void*)bar, strlen(bar), irgendwas));
	return 0;
}

36
36

31 statt 256, weil dein `wert` nur 8 bit breit ist und du so die bits mit *256 einfach rausshiftest anstatt sie ordentlich miteinander zu vermischen.

volkard

the_menace schrieb:

ich dachte, die 256 * wert seien dazu da, um den wert "weiter zu shiften" wie beim hornerschema? ich kapiere nicht so ganz den sinn, wenn man das so macht..

31 statt 256, weil dein `wert` nur 8 bit breit ist und du so die bits mit *256 einfach rausshiftest anstatt sie ordentlich miteinander zu vermischen.

(stell dir vielleicht mal die zahlen binär vor und schau, was bei *256 und was bei *31 passiert.)

the_menace

volkard: ah, okay, kapiert Ich hatte die beschreibung im sedgewick so verstanden, dass das rausschieben gewollt war.

c.rackwitz: in deinem beispiel ist size aber keine primzahl. 41 und 43 wären primzahlen und genau dann gibts mit deinem beispiel keine kollision.

c.rackwitz

int irgendwas = 41; // beliebig, echt.
char *foo = "welt";
char *bar = "welK";

akzeptier es doch bitte. dein algo kollidiert viel zu einfach. ob man dabei die eingabewerte anpassen muss, ist nicht die frage.

life

unsigned long hashing(void *object, unsigned long length, unsigned int size) { 
    unsigned long i = 0; 
    unsigned long wert = 0; 
    unsigned char *ptr = NULL; /* nur auf char gecasted, damit compiler nicht mecker */ 
    ptr = (unsigned char*)object; 
    for(i = 0; i < length; i++) { 
        wert = (wert * 31 + ptr[i]); 
    } 
    return wert % size; 
} 

int main(void) 
{ 	
    int irgendwas = 42; // beliebig, echt. 
    char *foo = "welt"; 
    char *bar = "welJ"; 
    printf("%ld\n", hashing((void*)foo, strlen(foo), irgendwas)); 
    printf("%ld\n", hashing((void*)bar, strlen(bar), irgendwas)); 
    return 0;
}

Ausgabe:

12
12

Wenn du von einer größeren Wertemenge in eine Kleinere abbildest, kann es immer zu Kollosionen kommen, egal wie toll die Hashfunktion ist

volkard

life schrieb:

Wenn du von einer größeren Wertemenge in eine Kleinere abbildest, kann es immer zu Kollosionen kommen, egal wie toll die Hashfunktion ist

auch bei

wert = (wert + ptr[i]) * 31;

? ich seh da grad keine kollission (außer bei größe 31, 62, 93...).

c.rackwitz

zwei zahlen muessen nicht gleich sein, nur damit sie auch modulo X gleich sind.

life

volkard schrieb:

life schrieb:

Wenn du von einer größeren Wertemenge in eine Kleinere abbildest, kann es immer zu Kollosionen kommen, egal wie toll die Hashfunktion ist

auch bei
wert = (wert + ptr[i]) * 31;
? ich seh da grad keine kollission (außer bei größe 31, 62, 93...).

Wenn du behauptest es kann keine Kollisionen geben, behaupteste ja, dass die Hashfunktion injektiv ist. Surjektiv sollte sie weiterhin sinvollerweise sowieso sein. Somit kannst du mir sicherlich eine Umkehrfunktion zu deiner Hashfunktion angeben, die den Hashwert nimmt und das entsprechend gehashte Objekt zurückgibt.

Dass es eine solche Umkehrfunktion nicht geben kann, sollte klar sein, sofern size kleiner ist als die Anzahl der möglichen unterschiedlichen Objekte die man in die Hashfunktion geben kann. Entsprechend kann deine Hashfunktion unter den gleichen Bedingungen nicht injektiv sein...

Übrigens führt das gleiche Beispiel von oben auch hier wieder zur Kollision. Weiter wäre die Hashfunktion selbst ohne das Modulo am Ende nicht injektiv..

c.rackwitz

vergiss nicht, es gibt registerbreiten, die wie modulo wirken.

(ich geh mal davon aus, dass hier keiner ne bignum lib verwendet)

life

c.rackwitz schrieb:

vergiss nicht, es gibt registerbreiten, die wie modulo wirken.

(ich geh mal davon aus, dass hier keiner ne bignum lib verwendet)

Naja dann ist die (hash)-funktion erst recht nicht injektiv und es kann Kollisionen geben.

Aber einen Überlauf von "wert" sollte imho hier eigentlich nicht stattfinden, da ja immer nur 4 byte aufeinmal gehasht werden sollen (so hab ichs jedenfalls verstanden) und in unsigned long auch "normalerweise" mindestens 4 byte reinpassen sollten. Also gibt es keinen Überlauf bei der *256 Variante und bei der *31 Variante sowieso nicht.