Teil 1 Speicher

Teil 1: Speicher

Kollisionsauflösungsstrategien

• Lineares Sondieren: Bei Kollisionen wird der nächste freie Platz nach der berechneten Adresse gesucht und verwendet.

• Nicht verkettete Überläufer: Ein spezieller Überlaufbereich wird bereitgestellt, um kollidierende Datensätze dort zu speichern.

• Verkettete Überläufer: Ein Überlaufbereich wird bereitgestellt, wobei ein Zeiger von der kollidierenden Seite auf die Überlaufseite verweist.

• Mehrfach-Hashing: Eine zweite Hash-Funktion wird genutzt, um bei einer Kollision eine alternative Adresse zu generieren, oft innerhalb eines Überlaufbereichs.

Erweiterbares Hashing

Berechnung von globalen und lokalen Tiefen

Mit Tiefen meint die Anzahl der Bits, die für die Zuordnung zu einer Bucket relevant sind.

• Globalen Tiefe (GT)

$$\text{Globale Tiefe}=\text{Anzahl der Bits}$$

• Lokalen Tiefe

$$\text{Lokale Tiefe}=lo{g}_2(\frac{2^{\text{Bits von GT}}}{\text{Anzahl der Pfeile}})$$

Datensätze löschen

• den entsprechenden Datensatz löschen
• prüfen, ob Buckets (z.B. 001 und 101) sich miteinander verschmolzen werden können

---