Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Mittwoch, 26. April 2017 00:10 
Hashing in der Informatik
 
Geschrieben von Alexander am Freitag, 12. Mai 2006

Hashing ist eine Methode zur dynamischen Verwaltung von Daten, die durch einen eindeutigen Schlüssel angesprochen (gesteuert) werden:
  • Suchen nach einem Datensatz,
  • Einfügen eines neuen Datensatzes,
  • Löschen eines Datensatzes.
Gehen wir davon aus, dass zu jedem Zeitpunkt nur eine (kleine) Teilmenge K aller möglichen Schlüssel U (und die zugehörigen m Datensätze) gespeichert sind, so kann versucht werden, die Datensätze in einem Array a der Länge m zu speichern, also a[0..m–-1]. Das Array a[0..m–-1] bezeichnen wir als Hashtabelle und die Größe der Hashtabelle wird durch m festgelegt.

Die grundsätzlich Idee ist nun den Speicherplatz eines jeweiligen Datensatzes mit Hilfe des eindeutigen Schlüsselwertes zu berechnen. Dazu benötigen wir natürlich eine Funktion, welche auf einer Teilmenge der natürlichen Zahlen definiert ist - die Hashfunktion. Diese muss um den praktischen Anforderungen zu genügen gewisse Eigenschaften aufweisen.

Im Einzelnen werden behandelt:
  • Grundlagen des Hashings, Behälter, Array, Datensätze, Datenstrukturen zur Verwaltung von Dictionaries, dynamische Datenmengen - Einfügen, Löschen, Verändern
  • Kosten, Platz, Zeit, O(n), Komplexität
  • Hashfunktion, Auswahl der Hashfunktionen, totale Abbildung, surjektiv, injektiv, effizient berechenbar, Kollision, Beispiele
  • Wahrscheinlichkeit einer Kollision, Beispiel
  • Klassifizierung der Hashverfahren, Verkettung der Überläufer, offener Adressierung, offenes Hashing, geschlossenes Hashing
  • Sondierfolge, Sondierungsarten, Lineares Sondieren, quadratisches Sondieren, Doppel-Hashing, Beispiel
  • Divisionsmethode, Multiplikationsmethode, Mittelquadratmethode

Hashing in der Informatik

Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.076 Sekunden, mit 54 Datenbank-Abfragen