你好 Christoph,

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?

Die Tatsache, dass wieder dieselben Kollisionen auftreten. Vergiss nicht:
du hast eine gleich grosse Hashtabelle H_i, das heisst, der Schluessel
kann in seiner Genauigkeit nicht vergroessert werden, sondern muss gleich
gross bleiben. In dem Fall haetten wir dieselbe Kollision noch mal, weil
wir zwei Eingangswerte haben, die bereits kollidiert sind. Beispiel,
nehmen wir an, wir haetten eine beliebige Tabelle, oben die Position und
damit den Hash-Wert und unten den Schluessel:

1|2|3|4|5
----------
a|b|c|d|e

Packen wir jetzt den Schluessel f dazu, bekommen wir eine Kollision:

1 |2|3|4|5
----------
af|b|c|d|e

Deshalb muss eine neue Hash-Tabelle aufgemacht werden, ich deute das mal
an:

1|2|3|4|5
----------
||b|c|d|e
|
------> 1|2|3|4|5
        ---------
         | | | |

In diese neue Tabelle muessen jetzt a und f eingesetzt werden, jedoch mit
einem Schluessel in der gleichen Genauigkeit wie in der Stufe zuvor. Werfen
wir jetzt a in die Funktion, bekommen wir den Hash-Wert 1 heraus. Werfen
wir jetzt noch f in die Funktion, bekommen wir -- na? Ahnst du es? Genau,
wir bekommen auch 1 heraus, weil die Genauigkeit gleichgeblieben ist und
die Funktion nicht ausgetauscht wurde. Es muss ja zwangslaeufig so sein,
denn Hashing waere sinnlos, wenn die gleiche Funktion bei gleicher
Genauigkeit und gleichen Eingangswerten unterschiedliche Hash-Werte
auswerfen wuerde.

Bei Mehrwortanfragen wäre jedes Wort einzeln zu prüfen. Gut, das
ist seltenst viel, das würde sich wahrscheinlich auch noch lohnen.
Phrasensuche wäre aber schon schwieriger.

Wieso seltenst? Die Schnittmenge der Postinglisten muss halt gebildet
werden. (gleich kommt sowas wie geordnete Listen dafür nicht optimal
sind ... geschenkt ;-)

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.

Naja, das halte ich fuer uebertrieben, ein Grep durchs Archiv duerfte
noch teurer sein, vor allem wenn man geschickt merged: die Begriffe sind
ja UND-verknuepft, also sucht man sich zuerst den Begriff mit den
wenigsten Treffern heraus und geht von da aus weiter. Aber du hast schon
recht, das kann die Datenbank vermutlich besser und schneller.

Also ich halt jede Wette das der Zuwachs an Vokabeln des Forums über
die Jahre abgeflacht ist.

Ich setz' 'n Kasten Bier dagegen.

Und ich klaer auf ;-) Aber ich kriege was ab!

Maaan, dauert das... kein Wunder, bei der Menge an Daten und dem
“Zimmermannsalgorithmus”... *wart* Ok, also Ergebnisse:

new in 1998: 9228
new in 1999: 51678
new in 2000: 89827
new in 2001: 58391
new in 2002: 227148
new in 2003: 259379
new in 2004: 251905

Ich glaube, das duerfte alle Fragen beantworten *g* Christoph, ich krieg
die Haelfte ab *fg*

再见,
 CK