Algorithmen lernen

Kapitel 3. Besser leben durch besseres Hashing

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

In diesem Kapitel lernst du:

• Wie man (Schlüssel, Wert)-Paare in einer Symboltabelle speichert und die mit einem Schlüssel verbundenen Werte abruft.¹

• Wie man ein Array verwendet, um (Schlüssel, Wert) Paare für eine effiziente Suche zu speichern, wenn die Größe des Arrays im Vergleich zur Anzahl der gespeicherten Paare ausreichend groß ist.

• Wie man ein Array aus verknüpften Listen zum Speichern von (Schlüssel, Wert)-Paaren verwendet, um die zusätzliche Möglichkeit zu unterstützen, einen Schlüssel zu entfernen.

• Wie man die Größe einer Symboltabelle ändert, um effizient zu bleiben.

• Amortisierte Analyse zur Ermittlung der durchschnittlichen Laufzeitleistung, wenn sich das Verhalten einer Operation bei aufeinanderfolgenden Aufrufen ändern kann.

• Wie die geometrische Größenanpassung die Häufigkeit der kostspieligen Größenanpassung reduziert, was bedeutet, dass put() im Durchschnitt eine amortisierte O(1) Leistung hat.

• Wie eine rechnerische Hash-Funktion die Schlüsselwerte gleichmäßig verteilen kann, was die Effizienz der Implementierung der Symboltabelle gewährleistet.

Werte mit Schlüsseln verknüpfen

Anstatt nur Werte zu speichern, musst du vielleicht eine Sammlung von (Schlüssel, Wert)-Paaren speichern, um Werte mit bestimmten Schlüsseln zu verknüpfen. Dies ist ein sogenannter Symboltabellen-Datentyp ...