Seite 1 von 1

10.1 Implementationsinvariante

Verfasst: 29. Jun 2013 10:29
von AlexanderP
Hallo,
wo finde ich im Wiki die Implementationsinvariante zur Hashtable.
In HashTable find und insert sind jeweils die Invarianten nur im Abstract view.

Gruß Alex

Re: 10.1 Implementationsinvariante

Verfasst: 29. Jun 2013 11:50
von JannikV

Re: 10.1 Implementationsinvariante

Verfasst: 29. Jun 2013 12:23
von AlexanderP
Geilo :lol: , danke!

Re: 10.1 Implementationsinvariante

Verfasst: 29. Jun 2013 15:55
von Schnell
Ich verstehe die Aufgabe irgendwie nicht.
Wenn die Hashtable so sein soll wie sie im Beispiel steht und mit der gleichen Reihenfolge wie gegeben, dann müsste dafür ganz klar an einer Stelle 5.2 verletzt worden sein und nicht, wie in der Aufgabenstellung steht, korrekt eingehalten worden sein. Was mach ich falsch?

Re: 10.1 Implementationsinvariante

Verfasst: 29. Jun 2013 16:12
von cofi
Die Invariante der Datenstruktur ist nicht die einzige, die verletzt werden kann.

Re: 10.1 Implementationsinvariante

Verfasst: 29. Jun 2013 17:02
von JannikV
Und ich verstehe das Problem mal wieder nicht xD
Also da lief etwas anders als es soll. Stichwort Reihenfolge. Und jetzt finde raus was und präsentiere es deinem Tutor :)

VG

Re: 10.1 Implementationsinvariante

Verfasst: 30. Jun 2013 16:20
von ONeff
Die große Frage ist doch, wieso wird 5.2 im Wiki eingehalten, obwohl wir offensichtlich über eine leere Stelle drüber Iterieren ohne das Element einzufügen?
Und ganz ehrlich, ich habe keine Ahnung. ^^
Aber was ist mit hashtable insert ???

Re: 10.1 Implementationsinvariante

Verfasst: 30. Jun 2013 16:35
von JannikV
Na die Aufgabe ist zu erklären warum das gezeigte Beispiel so nicht entstanden sein kann. Offensichtlich bist du doch da schon auf etwas gestoßen.......
ONeff hat geschrieben:Aber was ist mit hashtable insert ???
Was soll damit sein?

VG

Re: 10.1 Implementationsinvariante

Verfasst: 30. Jun 2013 16:48
von ONeff
Meiner Meinung nach wird die Inavariante des Abstract Views von Hashtable insert verletzt.
Oder bin ich gerade auf dem Holzweg ?

Re: 10.1 Implementationsinvariante

Verfasst: 30. Jun 2013 16:53
von JannikV
Ich kann dir ja jetzt nicht die Lösung sagen. :roll:

Aber du hast doch bemerkt dass etwas nicht stimmt. Herzlichen Glückwunsch, das war Sinn der Sache. Jetzt schreib doch auf, was da passiert ist und wie es eigentlich aussehen müsste.

VG

Re: 10.1 Implementationsinvariante

Verfasst: 30. Jun 2013 17:05
von ONeff
Das ist der Grund wieso ich erst selber nicht so genau drauf eingehen wollte.
Aber danke für die Hilfe :-)

Re: 10.1 Implementationsinvariante

Verfasst: 1. Jul 2013 14:57
von AnnaW
Sehe ich das richtig, dass wir Double Hashing gar nicht anwenden müssen? Da steh ich nämlich auf dem Schlauch, wie genau \(F_1\) und \(F_2\) definiert sind...

Re: 10.1 Implementationsinvariante

Verfasst: 1. Jul 2013 15:34
von JannikV
Hallo, die Hashfunktion ist F. Diese ist eine Double-hashing Hashfunktion, da sie die beiden Hilfshashfunktionen F1 und F2 benutzt.
Kannst du das Problem konkretisieren?

VG

Re: 10.1 Implementationsinvariante

Verfasst: 1. Jul 2013 17:16
von cofi
@AnnaW: Hum, nun ... genau unter \(F\).

Re: 10.1 Implementationsinvariante

Verfasst: 1. Jul 2013 22:04
von AnnaW
Ich hab meinen Denkfehler gefunden... Danke euch :-)