Hashing

Schlagwörter:
Referat, Hausaufgabe, Hashing
Themengleiche Dokumente anzeigen

Beschreibung / Inhalt
Das Dokument beschäftigt sich mit der Methode des „Hashing“, die eine Möglichkeit bietet, auf Datensätze in einer Tabelle direkt zuzugreifen. Dazu wird eine Hash-Funktion verwendet, die aus einem Schlüssel die Adresse des zugehörigen Datensatzes in der Tabelle errechnet. Es wird erklärt, wie diese Hash-Funktion berechnet wird und welche Methoden zur Kollisionsbehandlung es gibt.

Bei der Wahl der Hash-Funktion ist es wichtig, eine Funktion zu finden, die Schlüssel in ganze Zahlen umwandelt und dabei eine gute Verteilung der Schlüssel liefert. Eine der bekanntesten Funktionen ist das Divisionsrestverfahren.

Die Möglichkeit der Kollisionen bei der Verwendung einer Hash-Funktion wird ebenfalls behandelt. Es werden zwei Methoden zur Kollisionsbehandlung vorgestellt: Getrennte Verkettung und Offene Adressierung.

Bei der getrennten Verkettung wird für jede Tabellenadresse eine verkettete Liste erzeugt, um jene Datensätze zu speichern, deren Schlüssel auf diese Adresse abgebildet werden.

Bei der Offenen Adressierung wird hingegen der Adressbereich nach freiem Speicherplatz durchsucht, wenn eine Kollision auftritt. Es werden zwei Methoden der Offenen Adressierung besprochen: das lineare Austesten und das doppelte Hashing.

Es wird darauf hingewiesen, dass Methoden der Offenen Adressierung in einer dynamischen Situation, bei der eine nicht vorhersagbare Anzahl von Einfüge- und Löschoperationen auszuführen sind, unzweckmäßig sein können. Es muss beim Löschen mit Vorsicht vorgegangen werden, da ein Datensatz nicht einfach aus einer Tabelle entfernt werden kann, die mit Hilfe von linearem Austesten oder doppeltem Hashing erzeugt wurde.

Die Wahl der besten Hashing-Methode für eine spezielle Anwendung kann sehr kompliziert sein. Im Allgemeinen wird jedoch empfohlen, die Methode der einfachen getrennten Verkettung anzuwenden, um die Suchzeit stark zu verkürzen, wenn die Anzahl der zu verarbeitenden Datensätze nicht im Voraus bekannt ist, und doppeltes Hashing zu verwenden, um eine Menge von Schlüsseln zu suchen, deren Größe im Voraus grob angegeben werden kann.

Insgesamt ist Hashing ein guter Kompromiss zwischen Zeit- und Platzbedarf und ermöglicht eine effiziente Nutzung der verfügbaren Speicherkapazität sowie einen schnellen Zugriff auf den Speicher.
Direkt das Referat aufrufen

Auszug aus Referat
Hashing Bei Hashing (zerhacken) handelt es sich um eine Methode für die direkte Bezugnahme auf Datensätze in einer Tabelle. Dies erfolgt mit Hilfe einer Funktion, die direkt aus dem jeweiligen Schlüssel die Adresse des zugehörigen Datensatzes errechnet. Wenn man weiß, daß die Schlüssel nur ganze Zahlen von 1 bis N sind, kann beispielsweise der Datensatz mit dem Schlüssel 5 an der Tabellenposition 5 gespeichert werden. Hashing ist eine Verallgemeinerung dieser Methode, wenn die speziellen Kenntnisse über die Schlüsselwerte nicht vorhanden sind. Bei der Benutzung von Hashing sind zwei Punkte zu beachten: 1.) Wahl einer geeigneten Hash-Funktion zur Berechnung der Tabellenadresse. 2.) Da die Anzahl der verfügbaren Speicherplätze in der Regel geringer ist, als die der möglichen Schlüssel, muß eine Funktion gewählt werden, die eine Doppelbelegung einer Adresse zuläßt. Die Art der Behandlung derartiger Kollisionen beeinflußt die Zugriffsdauer wesentlich. Hashing ist ein guter Kompromiß zwischen Zeit- und Platzbedarf. Gäbe es keine Beschränkung des Speichers, könnte man jede beliebige Suche mit nur einem Zugriff auf den Speicher ausführen, wenn man den Schlüssel als Speicheradresse verwendet. Wenn es keine zeitliche Begrenzung gäbe, könnte man mit einem minimum an Speicherplatz auskommen, indem man ein sequentielles Suchverfahren verwendet. Hashing ermöglicht es, mit einem vertretbaren Maß an Speicherplatz als auch an Zeit auszukommen. Eine effiziente Nutzung der verfügbaren ...
Direkt das Referat aufrufen

Autor:
Kategorie:
Sonstiges
Anzahl Wörter:
1210
Art:
Fachbereichsarbeit
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bislang noch nicht bewertet.
Zurück