https://wiki.unkompliziert.eu/index.php?action=history&feed=atom&title=Hash_Table_%28Datenstruktur%29 2026-04-30T23:53:28Z Versionsgeschichte dieser Seite in unkompliziert.eu MediaWiki 1.34.1 https://wiki.unkompliziert.eu/index.php?title=Hash_Table_(Datenstruktur)&diff=63&oldid=prev 2020-04-11T07:56:35Z

<p>Die Seite wurde neu angelegt: „=== Grundidee === * Der Index, an dem die gesuchte Information steht, wird berechnet {| class=&quot;wikitable&quot; |- ! Index !! Schlüssel !! Info |- ! !! Name !! Tel…“</p> <p><b>Neue Seite</b></p><div>=== Grundidee ===<br /> * Der Index, an dem die gesuchte Information steht, wird berechnet<br /> <br /> {| class=&quot;wikitable&quot;<br /> |-<br /> ! Index !! Schlüssel !! Info<br /> |-<br /> ! !! Name !! Tel.<br /> |-<br /> | 0 || Baum || 09....<br /> |-<br /> | 1 || || <br /> |-<br /> | 2 || unkompliziert || 0 32 222133190<br /> |-<br /> | 3 || || <br /> |-<br /> | 4 || Wasser || 0...<br /> |-<br /> | 5 || || <br /> |-<br /> | 6 || Bisa || 09...<br /> |-<br /> | 7 || Holla || 09...<br /> |-<br /> | 8 || || <br /> |-<br /> | 9 || || <br /> |}<br /> Aktueller Füllgrad: 60%<br /> <br /> Maximaler Füllgrad 60%<br /> <br /> '''Größe eines Hash Table: Anzahl der zu speichernden Elemente'''<br /> <br /> === Arbeitsweise beim Einfügen von Daten ===<br /> 1. Berechne den Hashwert der gewünschten Information<br /> * z.B. Hashwert von &quot;unkompliziert&quot; = 37852<br /> <br /> 2. Index = Hashwert modulo GrößeHashTable<br /> * im Beispiel: Index = 37852 % 10 = 2<br /> <br /> *Holla: 16517<br /> * Bisa: 12516<br /> * Baum: 19220<br /> * Olga: 13666 =&gt; Index 6<br /> * Wasser 2504<br /> <br /> 3. Prüfe, ob die berechnete Position frei ist<br /> * Nein: Erhöhe Index um 1<br /> Index = Größe vom Hash Table =&gt; Index = 0<br /> * Ja: Einfügen an die berechnete Stelle<br /> <br /> === Kenngrößen einer Hash-Table ===<br /> * Aktueller Füllgrad<br /> aktFüllgrad = (Anzahl der Einträge) / (Größe der HT) * 100 (in Prozent)<br /> <br /> * Maximaler Füllgrad<br /> Beim Anlegen des HT wird ein maximaler Füllgrad mit angegeben (ca. 60-70%)<br /> <br /> * Grundsatz<br /> Je niedriger der aktuelle Füllgrad ist, desto schneller arbeitet der Hashtable, weil es weniger Kollisionen gibt.<br /> <br /> * Kollission<br /> Der Eintrag steht nicht an der berechneten Position<br /> <br /> {| class=&quot;wikitable&quot;<br /> |-<br /> ! Index !! Schlüssel !! Info<br /> |-<br /> ! !! Name !! Tel.<br /> |-<br /> | 0 || || <br /> |-<br /> | 1 || || <br /> |-<br /> | 2 || || <br /> |-<br /> | 3 || || <br /> |-<br /> | 4 || || <br /> |-<br /> | 5 || || <br /> |-<br /> | 6 || || <br /> |-<br /> | 7 || || <br /> |-<br /> | 8 || || <br /> |-<br /> | 9 || || <br /> |-<br /> | 10 || || <br /> |-<br /> | 11 || || <br /> |-<br /> | 12 || Wasser || <br /> |-<br /> | 13 || || <br /> |-<br /> | 14 || || <br /> |}<br /> <br /> Wasser: 2504%14 = 12<br /> <br /> Beim Erreichen des maximalen Füllgrades wird ein HT erweitert, d.h. es wird ein Resize durchgeführt.<br /> <br /> z.B. in DB-Systemen<br /> create table ...<br /> resize 10%<br /> resize 100MB<br /> ...<br /> <br /> === Auswirkungen eines Resize ===<br /> Alle im alten HT vorhandenen Einträge müssen neu berechnet werden.<br /> * Leistungseinbruch des Servers beim Resize<br /> * HT ist während des Resize nicht nutzbar<br /> <br /> ==== Vorteile HT ====<br /> * Sehr schnell, weil Index berechnet wird.<br /> ==== Nachteile HT ====<br /> * Leistungseinbrüche möglich (Resize)<br /> * Sehr hoher Speicherbedarf<br /> * Keine Suche möglich, der exakte Schlüssel muss bekannt sein<br /> ==== Einsatzgebiet ====<br /> In Datenbanken zur Verwaltung der Schlüssel (Primary key und foreign key, oder Indizes)</div>

Felix