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.
Klausur 06.08.2011 Aufgabe 6 Hash vs. Primär,Sekundär kollision
Hi Leute
wie sieht bei der 6.c) vom 06.08.2011 euer Ergebnis aus?
Im besonderen, wie sind da die Kollisionen gefragt?
Ich habe folgendes.
0,12, S
1,33, D
2,66, S
3,28, P
4,14, D
5, 6, S
6,18, D
7,5, D
8,15, P
9,9, D
Ist hier also nur nach der ersten Kollision gefragt die das Element beim einfügen hatte??
Lies dir mal die Definition von Primär und Sekundärkollision durch
Es geht dabei um den rechtmäßigen Platz des Elements, also um die erste Kollision.
Die Aufgabe hab ich grad nicht da
Mir ist die Definition von Primär und Sekundärkollision durchaus bewusst.
Jedoch gibt es beim Einfügen bestimmter Zahlen, mehrere Kollisionen.
Und für mich ist einfach nicht klar welche Kollision genannt werden soll(Alle/Erste?).
Wenn es die erste ist, sollte meine Aufgabe so stimmen…!!!
Habs auch so
Hab auch mal ne Frage zu 27.März 2006
Aufgabe 7
Hashfunktion war h(x) = x % 7
Hastabelle Länge 7:
9 15 65 74 11 5 - Sondiert wurde mit linearem Sondieren in beide Richtungen (1, -1, 2, -2...)Jetzt ist die Frage, ob man die Einfügereihenfolge von 9, 11 und 74 rekonstruieren kann.
(Angeblich wurde in diese Hashtabelle nur eingesetzt und nichts gelöscht)
Ich denke, wenn diese Konstellation möglich wäre (was die Aufgabenstellung ja postuliert) dann müsste es gehen.
15 11 und 5 stehen an ihren richtigen Plätzen. (Somit kann man schonmal sicher sagen, dass die 11 als erstes kommt.
Da Stelle 7 eine Lücke ist, muss eines der Elemente 9 65 oder 74 mit +1 sondiert worden sein.
Einzige Möglichkeit 65
Das heißt unsere Hashtabelle ist jetzt
- 15 65 - 11 5 -Ab jetzt wird es unlogisch. Sowohol 9 als auch 74 ließen sich mit Schrittweite -1 einfügen.
Fall 1: 9 einfügen
9 15 65 - 11 5 -Fügt man jetzt die 74 ein, will diese auf den Platz, auf dem 11 ist. Sondieren mit +2
--> 9 15 65 - 11 5 74 fail...
Fall 2: 74 einfügen
- 15 65 74 11 5 -Jetzt die 9, die auf die Stelle von 65 will
--> +2 +2 ---> - 15 65 74 11 5 9 fail...Deswegen frage ich mich, wie haben die die Tabelle hingekriegt o.O
Oder interpretiere ich das Sondieren in beide Richtungen irgendwie falsch?
Ich denke das Sondieren in beide Richtung gilt immer nur für einen Einfügevorgang.
Also Feld belegt → nachschauen ob +1 frei ist,
wenn auch belegt → nachschauen ob -1 frei ist,
wenn auch belegt → nachschauen ob +2 frei ist,
…
Edit:
Hab mir jetzt nochmal die Aufgabe angesehen.
fertige Tabelle:
9 15 65 74 11 5 -
65 steht doch auch auf dem richtigen Platz (65=7*9+2)
dann haben wir also
- 15 65 - 11 5 -
Dann kommt die 74 auf Platz 4 (belegt) → Platz 5 (belegt) → Platz 3:
- 15 65 74 11 5 -
Bei der 9 geht das noch ein bisschen länger:
Platz 2 (belegt) → Platz 3 (belegt) → Platz 1 (belegt) → Platz 4 (belegt) → Platz 0:
9 15 65 74 11 5 -