Not logged in. · Lost password · Register

Horst
Member since Jan 2011
14 posts
Subject: 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??
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
Lies dir mal die Definition von Primär und Sekundärkollision durch
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
Es geht dabei um den rechtmäßigen Platz des Elements, also um die erste Kollision.

Die Aufgabe hab ich grad nicht da
Horst
Member since Jan 2011
14 posts
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....?!?!
ri31hoky
Member since May 2011
452 posts
Habs auch so
ri31hoky
Member since May 2011
452 posts
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?
This post was edited on 2011-08-08, 23:50 by ri31hoky.
schmidti159
Member since Apr 2011
70 posts
Quote by ri31hoky:
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 -
This post was edited on 2011-08-09, 10:29 by schmidti159.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen