-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Mon, Aug 07, 2017 at 07:30:45AM +0200, Urs Liska wrote:
Am 03.08.2017 um 13:53 schrieb tomas@tuxteam.de:
[...]
5 mod 7 == 5
[...]
Danke, jetzt hat es klick gemacht.
Na, wenn's sooo einfach geht ;-D
Ich fand diesen Modularkram immer ein wenig schwer zu lesen/schreiben:
(foo mod bar ...) mod bar
Habe ich jetzt ein mod vergessen? Es fühlt sich wie Distributivgesetz an, man muss aber "draussen" noch ein mod liegen lassen.
Jetzt ist mir auch klar, warum (a^b) mod c = ((a mod c)^b) mod c ist, und dass man damit immense große Zahlen vermeiden kann, wenn man hinterher sowieso wieder nur am Modulo interessiert ist.
Jaja. Der obskure Hinweis in der Aufgabe "immer schön modulo machen" oder so ähnlich.
[...]
Ich habe mich wahrscheinlich nicht klar genug ausgedrückt. Dass ich zum jetzigen Zeitpunkt nicht erwarten kann, mir selber für gegebene Datenstrukturen geeignete Hashfunktionen auszudenken, ist mir schon klar. Aber ich hatte auch noch große Schwierigkeiten, den Ausführungen über die im Kurs vorgegebenen Funktionen zu folgen.
Das mag daran liegen, dass oft Konzept und Implementierungsdetails in der Präsentation wild durcheinandergemischt werden. Am Ende behält man den Eindruck, Hashing hätte "irgendwie mit Primzahlen zu tun" (was nur ganz bedingt stimmt), und "Primzahlen sind schwierig" (was schon eher stimmt, aber eine andere Geschichte ist).
Ja, Primzahlen nimmt man gerne zur Implementierung, aber nur, um sich aus der Affäre zu ziehen -- oder um den Geist im Computer zu verwirren. Aber mit der Grundidee des Hashings haben sie wenig zu tun.
Die Sache mit Modulo ist ja naheliegend (man hat M Kandidaten und N Plätze, also nimmt man erst M mod N und "wickelt" sozusagen M um N "herum" -- so könnte man vorgehen, wenn man eine (vorher nicht bekannte) Zahl M an Leuten auf N Tische verteilt. Wenn die Leute auch noch je mit einer Nummer ankommen (Perso), dann ist es noch besser: die Tischnummer N ist einfach die Endnummer des Persos. Dann weisst Du, welchen Tisch Du ansteuern musst, wenn Du jemanden suchst.
Das hat man auch für Variablennamen gerne benutzt, bis wir dummen Programmierer/innen kamen und unsere Variablen gerne ORT1, GESCHW1 BLUB1 nannten und dann alle an einem (überfüllten) Tisch landeten.
Das viel zu naive Modulo (meist eine Zweierpotenz) neigte dazu, die letzten Bytes "unversehrt" in den Hashwert "durchzureichen" und die (verdeckte) Struktur der Daten machten Interferenzen (man könnte sagen, ein Moiré-Effekt [1]). Dann kamen die Primzahlen.
Wenn jemand uns böse will, dann müssen wir evtl. würfeln (z.B. mit universal hashing, wie Du erwähnt hast). Eine feste Hashfunktion könnte unsere/r Gegner/in schnell rausbekommen.
lg
[1] https://en.wikipedia.org/wiki/Moir%C3%A9 - -- t