Hashing

Schlagwörter:
Speicherbereich mit direktem Zugriff, mathematische Funktion, ASCII Codes, Kollisionsverfahren, Referat, Hausaufgabe, Hashing
Themengleiche Dokumente anzeigen

Beschreibung / Inhalt
Das Dokument beschäftigt sich mit dem Thema „Hashing“, einer Methode zur gestreuten Speicherung von Daten in einem Speicherbereich mit direktem Zugriff. Der Speicherbereich wird als Hash-Tabelle bezeichnet und die Daten werden direkt über einen Index abgerufen. Die Indizes werden dabei durch eine Hash-Funktion aus dem Datensatz-Schlüssel errechnet. Die Hash-Tabelle sollte eine optimale Größe haben, die durch den Belegungsfaktor zwischen 0,5 und 0,8 definiert wird. Die Hash-Funktion sollte so gewählt werden, dass sie zu möglichst wenigen Kollisionen führt.

Es werden auch verschiedene geeignete Hash-Funktionen aufgeführt, je nachdem ob der Schlüssel ein Zahl oder eine Zeichenkette ist. Für Kollisionen stehen interne und externe Kollisionsauflösungen zur Verfügung. Beim internen Verfahren werden bei Kollisionen die nachfolgenden Plätze in der Hash-Tabelle besetzt, was jedoch zur Clusterbildung führen kann. Beim externen Verfahren werden Zeiger auf eine verkettete Liste statt der eigentlichen Daten in die Hash-Tabelle gespeichert. Beim doppelten Hashing wird die Technik der internen Kollisionsauflösung verwendet, jedoch wird der Betrag, der bei einer Kollision addiert wird, vom Schlüssel abhängig gemacht, um eine Clusterbildung zu vermeiden.

Das Dokument bietet auch Beispiele und Implementierungen für die verschiedenen Techniken und berechnet durchschnittliche Zugriffe bei erfolgreicher oder erfolgloser Suche. Insbesondere wird betont, dass die Wahl einer geeigneten Hash-Funktion und einer angemessenen Größe der Hash-Tabelle in der Praxis von großer Bedeutung ist, um eine optimale Leistung zu erreichen.
Direkt das Referat aufrufen

Auszug aus Referat
Hashing - Gestreute Speicherung 1. Einführung Vom Hashing spricht man, wenn Daten in einem Speicherbereich mit direktem Zugriff (der Hash-Tabelle) gespeichert werden und auf jedes gespeicherte Datenelement direkt zugegriffen wird. Dieser direkte Zugriff ist nur über einen Index möglich. Doch man verwaltet die Indizes nicht, wie üblich, in einer eigenen Tabelle, sondern errechnet den Index eines Datensatzes direkt aus seinem Schlüssel. Zurück zum Inhaltsverzeichnis 2. Die Hash-Tabelle Die Hash-Tabelle ist jener Speicherbereich, über den die Datensätze verteilt werden sollen. Dabei stellt sich die Frage, wie groß die Tabelle denn sein soll. Ist sie zu klein, so ist sie zu hoch ausgelastet und es kommt zu vielen Kollisionen (Begriff Kollision: siehe weiter unten). Ist sie zu groß, so wird Speicherplatz verschwendet. In diesem Zusammenhang ist der Begriff des Belegungsfaktors zu erwähnen: Belegungsfaktor Anzahl der Datensätze Anzahl der Speicherplätze Der Belegungsfaktor sollte zwischen 0,5 und 0,8 liegen. Zurück zum Inhaltsverzeichnis 3. Die Hash-Funktion Die Hash-Funktion ist eine mathematische Funktion, die aus dem Schlüssel eines Datensatzes einen Index für die Hash-Tabelle errechnet. Diese Funktion soll so gewählt werden, daß die Daten so abgebildet werden, daß der Grenzwertindex nicht überschritten wird, die Daten möglichst gleich über die Hash-Tabelle verteilt sind und es zu möglichst wenigen Kollisionen kommt. Zurück zum Inhaltsverzeichnis 3. 1. Geeignete ...
Direkt das Referat aufrufen

Autor:
Kategorie:
Mathe
Anzahl Wörter:
1516
Art:
Referat
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bisher 1 mal bewertet. Durchschnittlich wurde die Schulnote 6 vergeben.
Zurück