Hi,

Ich fürchte ich war immer noch nicht explizit genug! Du gehst davon aus das immer neue Tabellen fixer Größe aufgefüllt werden sobald eins "zu voll ist", sprich zuviele Kollisionen.

Nein, das hast Du doch korrigiert. Jedes Loch der ersten Hashtabelle hat eine zweite dahinter, diese hat dann hinter jedem Loch die üblichen linked lists.

Nein, stattdessen werden Tabellen aufgefüllt mit allen _jeweiligen_ Kollisionen.

Rein formal: Die Kollisionen an der Stelle x in H sind
   W_x={w ∈ W| h(w)=x}
diese und nur diese werden dann in K_x auf der Platte eingespeißt, wäre k=h folgte aber
  mit w ∈ W_x:  k(w)=h(w)=x

Ja, genau, aber nicht für H, sondern für H_i, eine ganz andere Hashtabelle. Da ist das Loch beim erstem Mal noch leer.

(Da es sortierte Listen bekannter Länge sind, könnte man die Schnittmengenbildung evt(!) auf nlogn runterbringen, aber auch nur als Best Case. Durchschnitt wäre n^2 und Worst case n^3. Mmh... nein, Worst Case käme gar nicht vor, oder?)

Was ist hier n? Ist |L_i| die Mächtigkeit der i-ten Liste und
n= Σ |L_i|, dann ist doch wohl O(n)!?! Wenn die Mengen aufsteigend geordnet sind brauche ich jedes nur Element nur 1 mal anzufassen, oder verwechsle ich hier was ?

Wahrscheinlich die Schreibweise. Die O-Notation wird hin und wieder verkürzt (durch n geteilt) bzw ist das 'O' eigentlich zwei verschiedene Buchstaben, zwei verschiedene Angaben. Mach Dich einfach mal kundig über "O-Notation", dsa Wiki ist hier glaueb ich ausnahmsweise gut, bin ich jetzt aber zu faul, dsa zu kontrollieren.

Ganz trivial: 2 geordnete Mengen, vergleiche die beiden kleinsten Elemente, sind sie identisch dann sind sie im Schnitt und man streicht beide ansonsten streicht man nur das kleinere. Das so lange bis eine Liste leer ist.

Ja, genau das meinte ich und das bedeutet eine Komplexität von O(n*log(n)). Du mußt jeden einmal anfassen (n), weil Du aber nach dem Vergleich streichen kannst (bzw eine Suche in einer sortierten Liste bekannter Länge eh nur log(n) dauert), mußt Du nicht n-mal vergleichen, sondern nur log(n)-mal.
Worst case ist hier, das beide Mengen keine gemeinsamen Elemente haben, jedes Element mit jedem verglichen werden müßte: O(n^3). Ausgehend aber davon, das eine Suche in einer sortierten Liste bekannter Länge nur log(n) dauert, ist Worst Case hier "nur" O(n^2 * log(n)).

Habe ich das richtig erklärt Christian? Stimmt alles?

so short

Christoph Zurnieden