Hi,

Was ich damit aussagen wollte: ich habe auf “nicht-optimal” bestanden,
weil ich dir widersprochen habe in der Aussage, dass eine perfekte
Hashing-Funktion gesucht wird. Wird IMHO ganz und gar nicht, da sich der
Datenbestand (wahrscheinlich sogar taeglich) von seiner Art (in Hinblick
auf die Hashing-Funktion) aendert.

Und warum sollte dafür keine perfekte Hashfunktion gefunden werden können?
Wenn Du davon ausgehst, das sich die Menge asymptotisch dem Unendlichem annähert ist es korrekt, das sich diese Menge nicht mehr komprimieren läßt: die Hälfte von Unendlich ist ja immer noch unendlich. Dazu müßte die Schlüsselmenge also auch unendlich sein, das geht nur bei direkter Abbildung. Das, was hast Du ja weiter unten als "lächerlich" bezeichnet hast und nun zur Untermauerung _Deines_ Argumentes dient. Mit ein wenig Mühe und gespitztem Bleistift ließe sich daraus sogar ein formal korrekter Beweis basteln. Das geht dann aber nur, wenn Du die 1:1 Abbildung als "perfekten Hash" akzeptierst und nicht sofort als lächerlich abtust. Auch wenn der äußerliche Anschein durchaus zum Lachen reizt, zugegeben.

Deshalb werden ja auch willkürliche Grenzen gesetzt, der Begriff "Hashing" wird je nach Einsatzzweck genau definiert eingegrenzt. Im Bereich Computertechnik ist die schnellste Methode des Zugriffs die direkte Adressierung. Diese Adresse hat eine bestimmte Größe und wird deshalb gerne als Obergrenze der Schlüssellänge benutzt. In einem gängigem x86-32 sind das z.B. 32 Bit und in einem modernem 64-Bit Rechner sind das 64-Bit, wie der Name schon anzudeuten versucht.
Erstens also: die Größe der Hashtabelle sollte 2^32 respektive 2^64 Schlüsselpaare nicht überschreiten.

Worst Case einer Hashtabelle ist O(n), Best Case O(1). Kollisionsbehandlung M addiert sich zu O(1), also O(1+M).

Zweitens also: M<<n, anzustreben: M = 0.

Diese beiden Punkte beschreiben die gängige Auffasung über Hashing, das in praxi anwendbar ist, ja: überhaupt erst Sinn macht. Die ganzen Diskussionen über "gute" oder "schlechte" Hashfunktionen behandeln also nur in mikrooptimierender Weise die Minimierung von M in sehr eng bestimmten Umgebungen und sind somit müßig. Schlechter als O(n) geht's nunmal nicht und wenn nicht alle Daten a priori bekannt sind, ist die Minimierung von M reines T&E. Eine große Sammlung der verschiedensten Hashfunktionen mit jeweils einer kurzen Notiz für welchen Zweck macht viel mehr Sinn als jede noch so abgehobene Diskussion darüber, was denn die Beste sei.

Hier bei der Archivsuche (Als typische Form des "text retrival") ist die effizienteste Art der Suche ein "inverted index" [Witten1999]. Der funktioniert bestens mit verschachtelten Hastables.
Nun ist sowas aber riesig und vollständige Updates würden einen umbringen. Was ist nun also günstiger: eine verzweifelte Suche nach der optimalen Hashfunktion oder Überlegungen bezüglich der optimalen Updatestrategie?
Beides natürlich: sämtlich Postings die archiviert worden sind, sind als "bekannte Daten" im Sinne der Möglichkeit einen perfekten Hash bauen zu können anzusehen. Jede Änderung eienr Hashfunktion verlnagt aber einen vollständigen Rebuild der Hastabelle. Es ist also zu überlegen, wie die Updates am besten auszusehen haben, damit so wenig wie möglich lose rumliegt (was Volltext durchsucht werden müßte = teuer), aber auch so selten wie möglich Updates des Indexes durchgeführt werden müssen.
Teilt man z.B. das Archiv in Jahres/Monats/Tagesringe, wird der vollständige Rebuild des Indexes auf jeweils einen solchen Ring beschränkt. Kostet ein wenig Overhead an Platz und noch weniger an Rechenzeit. Man kann natürlich den Monatsring in-place updaten und die Fragmentierung einmal monatlich durch Rebuild des Monatsringes ausbügeln und diesen Monatsring dann am Ende des Jahres in den Jahresring einbauen. Ist zwar auch mehr oder weniger eine Frage von T&E, zeigt aber deutlich mehr Effekt pro für's Hirn verbrannter Kalorie als komplizierte Hashfunktionsoptimierung. Diese Optimierung ergibt sich sogar von selber, denn für jeden vollständigen Jahresring kannst Du perfekte Hashes basteln. Jedes Jahr erhöht sich dann M um 1, nach zehn Jahren hättest Du dann O(1+10), bei einem n von mehreren Millionen.
Wenn ich aber durch die Zahlen hinter den Forumsjahresarchiven (Hey, das Häckchen bei "Groß/Kleinschriebung beachten" ist ja weg!) mal einen Strich ziehe und schaue, wo der in zehn Jahren endet, wäre ein vorrausschauendes Indexmanagment wahrlich keine schlechte Idee.

So ungefähr hätte Deine Entgegnung auf meine Dreistigkeit aussehen können, aber Du mußtest ja unbedingt von "lächerlich" sprechen. Das ist jetzt die unverdiente Strafe.

so short

Christoph Zurnieden

Bibliographie:

{Witten1999} - Witten, I. H., Moffat, A. & Bell, T. C. (1999), Managing Gigabytes: Compressing and Indexing Documents and Images, second edn, Morgan Kaufmann, San Francisco, California.