Hi

Tja, das hatte ich befürchtet, das ist auch sehr schlecht vorstellbar. Also nochmal:
Stell Dir vor, Du hast eine Hashtabelle H mit 5 Löchern {a,b,c,d,e} und eine Funktion f(x), die alle Elemente einer Menge S gleichmäßig auf diese Löcher abbildet. Ist |S| größer als |H| dann kommt es zu Mehrfachbelegung, zu Kollisionen. Nun steht hinter jenen Löchern von H je eine weitere Hashtabelle H_i = {f,g,h,i,j}.
Zuerst wird jedes Loch in H gefüllt (wir setzen einmal eine optimale Verteilung der Hashwerte voraus), nach fünf Vorgängen erfolgt also die erste Kollision, sagen wir mal in a. Wir brauchen nun also eine Hashfunktion, die ein Element aus S in H_i packt. Was hindert uns nun daran, ebenfalls f(x) zu nehmen? Dadurch, das H voll ist, wird eine _neue_ Hastabelle genommen, wir fangen sozusagen bei 0 an. D.h.: wir können den alten Hashwert nehmen, der funktioniert für H_i genauso gut oder schlecht, wie für H. Vorausgesetzt natürlich, das |H| = |H_i|, aber das trifft in Deinem Beispiel ja zu.
Jetzt verstanden? Na, ich sehe noch zweifelnde Blicke ...
Bastel Dir einfach ein Beispiel, oder mal's Dir auf, das hilft mir auch mitunter.

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, 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

Ist K "zu voll" (75%) wird keine neue Tabelle M angelegt, sondern K wird verdoppelt.

Aufmalen kann ichs dir jetzt leider schlecht...

Schnittmenge bilden ist _sehr_ teuer. Noch teurer fast, als ein grep durch's Archiv. Wenn das sein muß, ist die ganze vorherige Optimierung für die Katz.

(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 ?

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.

Wie macht es die DB?

Tschau
  rolf