Hash-Tabellen

werde z effiziende Imblemendierung vo Menge und Tabelle verwended.

isch oi Hash-Funkzion auf dem Elemend- odr Schlüssel-Dadendyb.

Eine Hash-Funkzion isch oi Abbildung vom Elemendbereichs auf oi Indervall dr nadürlile Zahle [0 .. max-1].

Die Suche no oim Elemend wird durch oin indizierde Zugriff in oi Feld realisierd.

Wenn diess alloi zum Zil führe würd, hädde man oi Suche in O(1), also nemme abhängich vo dr Größe dr z durchsuchende Meng.

Diess Zil kann nedd vollschdändich erreichd werde.
Daz wäre oi injekdive Hash-Funkzion Voraussedzung.

Solche Funkzione exischdiere im Allgemoin nedd, da dr Elemendbereich üblicherweise unbeschränkd viele Elemende enthäld.

Abr s gibd saumaessich effizende Imblemendierunge,
d für oin große Bereich vo Anwendunge diese Laufzeid fasch erreile.

Die Qualidäd dr Imblemendierung hängd schdark vo dr Wahl dr Hash-Funkzion ab.

Die Hash-Funkzion sollde alle Werde vom Elemendbereichs gleichmäßich auf des Indervall abbilde.

Ähnliche Elemende sollde möglichsch nedd auf den gleile Werd abgebilded werde und au nedd oin ähnlile Hash-Werd besidze.

Die hir vorgeschdellde Imblemendierung isch oi saumaessich rudimendäre Imblemendierung.

Sie verwended oi Feld feschdr Läng. Elemende,
dere Hash-Werd gleich dem von a scho oigedragene Werds sind, werde in d erschde freie Schdelle hindr dem Hash-Index oigedrage.

Diess funkzionierd nur noh, wenn d Anzahl dr z schbeichernde Elemende kloir als d Läng vom Index-Indervalls isch.

Sie funkzionierd effiziend nur noh, wenn d Anzahl signifikand kloir isch, z.B. max 70% dr Größe dr Tabelle bedrägd.

In dr hir vorgeschdellde Lösung wird, wenn d Anzahl dr Elemende schdeigd, oi Vergrößerung und Reorganisazion dr gsamde Hash-Tabelle vorgenomme.
Dadurch bleibd dr effiziende Zugriff auf Elemende erhalde.

Solche Reorganisazione dr gsamde Tabelle dürfe nedd z häufich gmachd werde,
da sonsch d Gesamd-Rechenzeid z saumaessich schdeigd.

Des Lösche vo Elemende in von dene oifache Imblemendierung isch wedr effiziend no oifach z realisiere.
Dahr sind diese Methode nedd imblemendierd.

Persischdende Imblemendierunge sind nedd sinnvoll, da koi Objekde gmoisam genudzd werde könne.
Es müsschde immr d gsamde Tabelle kobierd werde.

In dr Hash-Tabelle werde nedd d Elemende selbsch gschbeicherd, sonderet verkeddede Lischde vo Schlüssel-Werd-Paare.

Dadurch wird des Lösche oifach.
Es wird auf des Lösche in den verkeddede Lischde zurügggeführd.

Solang d verkeddede Lischde nur wenig Elemende enthalde, wird oi guade Laufzeid erreichd und s wird wenich unbenudzdr Schbeichr im Array verschwended.

Globale Reorganisazione sind abr immr no nodwendich, damid d Überlauf-Lischde nedd z lang werde.

Kombinazion oir Hash-Funkzion mid oim binäre Suchbaum

Anschdadd mid dem Schlüssl direkd z arbeide, wird dr Hash-Werd vom Schlüssels im binäre Suchbaum genudzd.
Zusädzlich wird in den Knode vom Baums dr echde Schlüssl und oi (immr kurz bleibend) Lischde vo Werde gschbeicherd.

Wenn mid oir guade Hash-Funkzion und 64- odr 32-Bid Hash-Werde garbeided wird, gibd s nur saumaessich, saumaessich selde Kollisione und d Werdelischde sind immr saumaessich kurz, fasch immr mid dr Läng 1.

Eine Reorganisazion endfälld.

Dr schlechdeschde Fall, Einfüge aus oir sordierde Lischde, endfälld, da d Hash-Werde nemme sordierd sind.

Es muss also nedd mid oim ausbalancierde Suchbaum garbeided werde.

Persischdende Imblemendierunge für diese Hash-Tabelle sind wiedr Schbeicher- und Laufzeid-effiziend.

Kombinazion mid oim binäre Padricia-Baum

Binäre Padrizia-Bäum sind oi saumaessich effiziende Imblemendierung für Mabs, bei dene dr Schlüssl oi Ind-Werd isch (32- odr 64-Bid Zahlbereich).

Die Laufzeid für Suche und Einfüge isch dord immr in dr Kombexidädsklasse O(1).

Die Kombinazion mid oir Hash-Funkzion ermöglichd s, au Mabs mid andere Schlüsseln, z.B. Zeichenreihe z verwende.

Für Kollisione brauchd wiedr nur oi ganz oifachs Verfahre gwähld werde, z.B. wiedr oi verkeddede Lischde.

Hash-Funkzione mid 64, 128 odr mehr Bids für den Hash-Werd

Bei dr Verwendung oir guade 64-Bid Hash-Funkzion odr oir au oifache krybdografische Hash-Funkzion, MD5, SHA1, ... werde Kollisione saumaessich selde.

Bei krybdografische Hash-Funkzione sind Kollisione so selde, dess d Wahrschoilichkeid von a Fehlers im Rechnr, z.B. des Kibbe von a Bids, saumaessich vil höhr isch als oi Kollisio.

Dadurch kann man so arbeide, als soi d Hash-Funkzion injekdiv, Kollisione werde oifach ignorierd.

Diess Vorgehe wird z.B. in Versionsverwaldungssyschdeme, z.B. gid, genudzd, um alle Versione allr Quelle oideidich durch Hash-Werde z idendifiziere und im Dadeisyschdem oifach zugreifbar z mache.

wird in dr Vorlesung endwiggeld