Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kollisionen
Hi,
kann jemand an einem Beispiel zeigen wann ist eine “Kollision” passiert?
Danke.
Eine Kolliosion tritt immer dann auf, wenn man irgendwo etwas einfügen will, wo schon was ist.
Also nehmen wir als hash-Funktion mod 5. Dann haben wir 5 verschiedene Listen:
0:
1:
2:
3:
4:
Einfügen von 27:
0:
1:
2: 27
3:
4:
Einfügen von 31:
0:
1: 31
2: 27
3:
4:
Einfügen von 22 (Hier tritt nun die erste Kollision auf, weil in der 2er-Liste schon was drin ist):
0:
1: 31
2: 27, 22
3:
4:
Einfügen von 32 (Hier tritt nun die zweite Kollision auf, weil in der 2er-Liste schon was drin ist):
0:
1: 31
2: 27, 22, 32
3:
4:
Einfügen von 44 (keine Kollision, da 4er-Liste noch leer):
0:
1: 31
2: 27, 22, 32
3:
4: 44
=> insgesamt haben wir also 2 Kollisionen gehabt.
Zum thema:
ich glaube es gibt einen fehler im op test:
es gibt 7 monate mit gleichem anfangsbuchstaben, die beim einfügen 4 kollisionen verursachen sollten:
januar, juni, juli: 2 kollisionen
maerz mai: 1 kollision
april, august: 1 kollision
gefordert nach dem einfügen werden jedoch 0.
falsch gedacht. januar, juni, juli sind nicht nur in der gleichen liste, sondern haben exakt den gleichen key (hash_func berücksichtigt nur den anfangsbuchstaben). damit werden die einträge überschrieben.
=> 0 Kollisionen ist korrekt
edit: was mich jetzt nur ein bisschen stutzig macht, ist das der test direkt danach 4 kollisionen liefert, obwohl nicht schreibend auf den hash zugegeriffen wurde… hm… hauptsache es funktioniert bei mir 
egal warum
jupp, genau das hat mich auch schon ins grübeln gebracht. hat einer ne idee?
ah… idee:
in der for-schleife zwischen den kollisionsabfragen wird ja auf
if(h[c])überprüft. einige anfangsbuchstagen (zB ‘Z’) gibt es in der liste nicht → die einträge werden angelgt (vom operator[]). dadurch hat man nach der schleife alle buchstaben im hash vertreten → mehr kollisionen
… richtig oder unsinn ?!? 
Da passiert schon was. Die Schleife läuft von ‘A’ bis ‘Z’. Es gibt da ja doch ein paar Buchstaben, für die noch keine Monate existieren, weswegen in der Schleife neue dummy-Einträge angelegt werden.
edit: D’OH. Zu langsam…
Schon, aber wo treten da Kollisionen auf?
Aqua
das liegt daran, daß beim lesen von nicht existierenden keys leere elemente erzeugt werden, auf die man schreibend zugreifen kann, da aber operator nicht weiß ob man lesen oder schreiben will, erzeugts immer die elemente auch wenn man nur liest.
Schau dir mal die Hashfunktion an. Die nimmt die Nummer eines Buchstabens zum Quadrat und dann modulo 100. Ab Buchstabe 11 geht’s wieder von vorne los. Und ab Buchstabe 15 nochmal. Da werden dann halt genau 4 Werte doppelt getroffen…
Die Kollisonen treten auf, wenn man sich die hashfunktion etwas genauer anschaut. Zuerst werden die Buchstaben von 0 ab gezählt (c - ‘A’). Diese Zahl wird dann quadriert und modulo 100 genommen. Wenn ich also den 10. buchstaben haben will, dann kommt der in die gleiche Liste wie das ‘A’. Vor dem Durchlauf durch die Schleife mit allen Buchstaben gibt es keine Kollisonen, weil die Namen überschrieben werden. Aber wenn man durchläuft, dann kommt z.b. der 10. Buchstabe (was ist das nochmal für einer, bin zu faul zum nachdenken) in die gleiche Liste wie April und man hat eine Kollision.
Ok. Ich seh gerade IceWeasel hat auch schon geantwortet, aber ich poste es trotzdem mal.