Verändert ihr dann die Blockgröße???? Weil sonst würde find den Block ja nie wieder finden, aber dadurch wäre die invariante verletzt, dass ein Block m-groß ist.
Und es ist schließlich gefordert, dass es in einen von den Beiden Blöcken drin sein muss. Wenn diese aber nun mal voll sind, sehe ich keine Möglickeit bei m-großen Blöcken alle erforderlichen Elemente unter zu bringen. Verdrängen würde ja entweder ein Element in den falschen Block stoßen, oder müsste es zerstören. Wenn man die Blockgröße ändert dann sehe ich das gefährdet:
"find muss also nur zwei Blöcke durchsuchen und ist garantiert in konstanter
Zeit ausführbar, [...]"
Wenn das so wäre, dass wir die Blockgröße nach bedarf ändern, und alle Elemente auf die selben Felder gehasht werden, dann haben wir für Find eine Laufzeit von O(2*(n/2)^2)
[...]falls auch B konstant.
Heißt dass, wir dürfen das für den Spezialfall vernachlässigen???
Denkt ihr wir dürfen Listen verwenden?
Zusatzdaten, die linear mit der Gr¨oße der Hashtabelle wachsen,
sind nicht erlaubt (da sonst e ziemlich sinnlos)
Eigentlich gehören die Pointer ja zu unserer Hashtabelle, verursachen aber natürlich overhead. Aber ausser Arrays verursacht jede Datenstruktur overhead. Und dann bleibt uns algorithmisch gesehen nicht mehr viel Spielraum, was nicht besonders für eine Algorithmenaufgabe sprechen würde.
-==[Edit]==-
Also ich habe es mal mit dem Fall vernachlässigen und Arrays gemacht...
bei fixed epsilon, und mit nem 2,1 Ghz Starken Rechner habe ich es auf 1,93 Sekunden geschafft... muss gleich nochmal schauen ob ich was optimieren kann...
Dafür will mein 2. Test einfach nicht aufhören... ich habe mir mal die Testmethode angesehen, die läuft so lange durch bis successfull runs = 0 ist.
Ich lasse mir mal die Werte nebenbei ausgeben. Ich bin gerade bei 25000 Elementen mit einem Epsilon von
![](http://www.codecogs.com/eq.latex?1*10^{-46})
... und er läuft weiter???
Hört der überhaupt noch auf???
[/Edit]