Am 07.08.2017 um 11:15 schrieb tomas@tuxteam.de:
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.
:-)
[...]
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).
Tja, die Sache mit der didaktischen Aufbereitung. Die ist durchaus unterschiedlich gut bei den verschiedenen Dozenten (auch) dieser Kurse. Hier hatten sie m.E. das Problem, dass sie nicht wirklich auf das Entwickeln von Hash-Funktionen eingehen wollten (ich denke auch, dass das den Rahmen wirklich sprengen würde), deshalb haben sie die beiden verwendeten Funktionen doch relativ willkürlich vorgesetzt (dann aber wieder recht ausführlich mathematisch bewiesen). Dass Hashfunktionen schwierig sind und wir jetzt halt einfach mit den uns vorgesetzten und für den Zweck gut geeigneten Funktionen zu arbeiten haben, wurde dadurch nicht so klar wie es hätte sein sollen.
Interessant ist auch, dass der anscheinend ranghöchste der Dozenten didaktisch mit Abstand der Schlechteste 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]).
Wenn man dagegen fortlaufende Daten hat (z.B. weil ein Schlüssel automatisch hochgezählt wird oder weil man Array-Indizes nutzen kann, dann würde ein einfaches Modulo die ideale Verteilung bringen.
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.
Interessante Fragestellung, wie man bei einem Adressbuch die Daten böswillig zurechtrücken wollte (nur das wurde als Beispiel verwendet). Vielleicht wäre das mal ein lohnendes Thema für die amerikanische Wahlbetrug-Kommission. Drei bis fünf Millionen schlecht gehashte Wählereinträge, weil die Schwarzen und Hispanics im Durchschnitt andere Namen haben als stramm-rechte Amerikaner :-/
HG Urs
lg
[1] https://en.wikipedia.org/wiki/Moir%C3%A9 -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug