universelle Hashklasse

[Mariexshhx]

Hallo, man sagt, dass eine universelle Hashklasse höchstens H(Anzahl aller Funktionen)/m die x,y auf den selben Wert hashen (x und y verschieden) Was genau ist mit diesem m gemeint ?

 

[Mariexshhx]

|{h ∈ H : h(x) = h(y )}| = |H|/m}

 

[osion]

Hier wird "m" als die Größe des Hashtabellenspeichers bezeichnet. Wenn du eine Hashtabelle verwendest, um Daten zu speichern, gibst du ihr normalerweise eine feste Größe an, die angibt, wie viele Einträge sie aufnehmen kann.

Jeder Eintrag in der Hashtabelle wird auf einen bestimmten "Bucket" oder "Slot" gelegt, der durch den Hashwert des Eintrags bestimmt wird. Wenn du also beispielsweise eine Hashtabelle mit 10 Slots hast, dann könnten maximal 10 Einträge in der Tabelle gespeichert werden.