[linux-l] mbox/Maildir/tar

[Rocco Rutte]

Hi,

* Ivan F. Villanueva B. wrote:
>Am Mi, Nov 28, 2007 10:42:14 +0100, Rocco Rutte schrieb:
>> O(log(n))/O(1) statt O(n)
>           ^^^^^
>        das verstehe ich nicht

Gute Hashtabellen (max. 50% voll, gute Hashfunktion mit guter Streuung) 
haben im Mittel keine Kollisionen, d.h. der Eintrag ist nach Berechnung 
der Hashsumme modulo Tabellengröße immer im Mittel sofort gefunden. Im 
worst-case kommt die Komplexität glaube ich auf das Verfahren zur 
Kollisionsauflösung an. Wenn man chaining (also verkettete Liste an der 
Stelle in der Tabelle) benutzt, kann man im schlechtesten Fall eine 
einfach verlinkte Liste haben, also O(n) (z.B. wenn die Tabelle nur 1 
Zeile hat). Bei linearem Auflösen (also Soll-Stelle je 1 Stelle weiter 
probieren) müsste man auch auf O(n) kommen. Für andere Verfahren weiss 
ich es nicht aus dem Kopf.

Ist aber schon 'ne Weile her, dass das in der Uni dran war. IIRC gibt es 
für O(1) auch einen Beweis (zumindest denke ich dass der Prof mal sowas 
erwähnt hatte)...

Nachteil: Hashtabellen brauchen viel Pflege und ggfs. zu lange, um die 
Elemente neu einzusortieren, damit die 50% Füllstandsbedingung erfüllt 
bleibt. Obwohl Datenbanken wie PostgreSQL dafür wohl Lösungen haben 
(wenn man einen Index als Hash statt als B-Baum möchte), aber trivial 
sah das nicht mehr aus als ich das Paper dazu mal überflogen hatte.

MfG, Rocco