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
--
ul@openlilylib.org
https://openlilylib.org
http://lilypondblog.org