Hashing
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
Mathe
divisionsrestverfahren
1516
Referat
Deutsch
Diese Hausaufgabe wurde bisher 1 mal bewertet. Durchschnittlich wurde die Schulnote 6 vergeben.
Freie Ausbildungsplätze in Deiner Region
besuche unsere Stellenbörse und finde mit uns Deinen Ausbildungsplatz
erfahre mehr und bewirb Dich direkt