universelle Hashklasse

[Mariexshhx]

Ich habe folgende Menge mit 16 Hashfunktionen gegegeben H17,16 := {ha(x) = (3^x+a mod 17) mod 16 | a ∈ {1, . . . , 16}}. Ich soll sagen, ob dies eine universelle Hasklasse für x ∈ {0, 1, 2, . . . , 15}. Nun ist ja eine universelle Hashklasse wenn es höchstens |H|/m Hashfunktionen gibt bei denen x,y (verschieden) auf den selben Wert gehasht werden. Das ist ja nicht schwierig herauszufinden mit einem kleinem Programm. Ich weiß nur einfach nicht, was dieses m ist. Kann mir jemand weiterhelfen?

 

[mihe7]

Ich weiß nur einfach nicht, was dieses m ist.

Die Hashfunktion ist modulo 16, verteilt also die Schlüssel auf die Menge {0, ..., 15}, d. h. auf 16 Elemente, damit ist m = 16.

 

[osion]

In diesem Fall ist "m" die Größe der Hashtabelle, also die Anzahl der Buckets, in die die gehashten Werte eingefügt werden. In diesem Fall gibt es 16 Buckets, da die Hashfunktionen haben den Wert "mod 16" zurückgeben.