Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Facharbeit elektromotor

   Kraftstoffe - benzin und diesel im vergleich

   Friedrich dürrenmatt, die physiker

   Referat ueber kernkraftwerke

   Nachweis- und anwendungsmöglichkeiten radioaktiver strahlung

   Mechanische größen

   Zusammenfassung radioaktivität

   Aufbau des ohres und der gehörvorgang

   Pumpenarten: verdrängerpumpe(kolben+zahnräder) und kreiselpumpe

   Physikalische einheiten

   Wasserkraft

   Fotoapparat

   Funktionsweise eines kernkraftwerks

   Kondensatoren

   Druckwasserreaktor
alle kategorien

  Hashing - gestreute speicherung

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 Hash-Funktionen für Zahlen Wenn der Schlüssel eines Datensatzes eine Zahl ist, so wird als Hash-Funktion meist das Divisionsrestverfahren bzw. eine etwas modifizierte Variante davon angewendet: H(K) = K mod M H(K) ist die Hash-Funktion, K der Schlüsselwert und M die Größe des Arrays. Um die Kollisionsbearbeitung (siehe weiter unten) zu erleichtern, sollte für M nach Möglichkeit eine Primzahl gewählt werden.

Zurück zum Inhaltsverzeichnis 3. 2. Geeignete Hash-Funktionen für Zeichenketten Die naheliegendste Lösung für Zeichenketten ist wohl, die Quersumme über die ASCII-Codes der einzelnen Zeichen zu bilden und auf das Ergebnis das Divisionsrestverfahren anzuwenden. Weiters könnte man die ganze Zeichenkette als Zahl interpretieren und auf diese Zahl wiederum das Divisionsrestverfahren anwenden. Der Nachteil dabei ist allerdings, daß dabei relativ hohe Zahlen entstehen (z. B.

: KARLI = 0x4B41524C49). Um das zu verhindern, sollte man nach jedem Buchstaben die Modulu-Operation anwenden: A = 65, I = 73, K = 75, L = 76, R = 82 Größe der Hash-Tabelle = 499 K: 75 mod 499 = 75 A: (75 * 256 + 65) mod 499 = 303 R: (303 * 256 + 82) mod 499 = 305 L: (305 * 256 + 76) mod 499 = 312 I: (312 * 256 + 73) mod 499 = 105 Der Datensatz mit dem Schlüsselwert "KARLI" wird somit in der Hash-Tabelle am Speicherplatz 105 gespeichert. Beispiel für Implementierung: unsigned int hash (char *key, unsigned int m) { int h; for (h = 0; *key != '\0'; key++) h = (256 * h + *key) % m; return (h); } Hinweis: "key" ist der Schlüsselbegriff, "m" die Größe der Hash-Tabelle. Zurück zum Inhaltsverzeichnis 4. Kollisionsverfahren Beispiel: Schlüsselwerte sind Ganzzahlen, die Hash-Tabelle umfaßt 499 Speicherplätze. Es soll das Divisionsrestverfahren angewendet werden.

Zu speichernde Werte: 3598, 6093. 3598 mod 499 = 105 6093 mod 499 = 105 Der Datensatz 3598 kann zwar am Speicherplatz 105 abgelegt werden, beim Speichern des Satzes 6093 ergibt sich allerdings das Problem, daß der errechnete Speicherplatz nicht mehr frei ist. Es ist ein Kollisionsverfahren anzuwenden. Das ist eine Methode, um Schlüssel mit gleichem Ergebnis der Hash-Funktion an anderen Stellen abzulegen und wieder zu finden. Zurück zum Inhaltsverzeichnis 4. 1.

Interne Kollisionsauflösung (Lineares Austesten) Für das Element wird ein Platz innerhalb der Tabelle gesucht, z. B. wird der nächste bzw. übernächste Platz genommen. Der Nachteil dabei ist die Clusterbildung. Die Tabelle enthält neben dem Datensatz selbst auch die Anzahl der Datensätze, deren berechneter Hashcode dem tatsächlichen Index an dieser Position entspricht (z.

B. an Position 4 wird die Anzahl der Sätze gespeichert, für die als Hashcode 4 errechnet wurde). Man benötigt außerdem einen speziellen Wert, der anzeigt, daü eine Position in der Hash-Tabelle "frei" ist, z. B. bei Strings einen Leerstring oder -1 bei Zahlen (Voraussetzung ist natürlich, daß diese Werte nicht als Schlüssel auftreten können). Der Vorteil gegenüber dem externen Verfahren ist die schnelle Positionierung.


Allerdings wird die Kapazität der Hash-Tabelle bei geringer Auslastung schlecht genutzt. Durch oftmaliges Löschen und Einfügen von Datensätzen kann sich beim internen Verfahren die Anzahl der Zugriffe stark erhöhen. Beispiel: Schlüsselwerte sind Zeichenketten. H("Carmen") = 2, H("Renate") = 6, H("Tina") = 4, H("Veronika") = 2 Kollisionsverfahren: Neuer Hashcode = Alter Hashcode + 3 Wenn Plätze nicht belegt sind, werden die Personen-ID und der berechnete Index auf -1 gesetzt. tatsächlicher Index berechneter Index Datensatz-ID Anz. Elemente mit diesem Hashcode 1 -1   0 2 2 Carmen 2 3 -1   0 4 4 Tina 1 5 2 Veronika 0 6 6 Renate 1 Suche nach Datensatz "Veronika": Hashcode errechnen (im Beispiel: 2) Vergleiche Suchschlüssel mit gespeicherter Datensatz-ID auf Position 2 und stelle fest, daü "Veronika" <> "Carmen" Gehe 3 Positionen weiter Erneuter Vergleich mit Datensatz-ID auf Position 5, Suche erfolgreich Beim Löschen des Datensatzes "Veronika" ist zu berücksichtigen, daß die Anzahl der Elemente mit Hashcode 2 (nicht 5) um 1 vermindert werden muß (im Beispiel: Anzahl bei "Carmen" auf 1 setzen).

Die durchschnittliche Anzahl der Zugriffe beim Suchen nach einem Datensatz, der tatsächlich in der Tabelle existiert, berechnet sich nach folgender Formel: 0,5 + 1 / (2 * (1 - Auslastung)) Beim erfolglosen Suchen: 0,5 + 1 / (2 * (1 - Auslastung) hoch 2) Beispiele: Auslastung 50 % 70 % 80 % durchschn. Zugriffe bei erfolgloser Suche 2,5 6,1 13,0 durchschn. Zugriffe bei erfolgreicher Suche 1,5 2,2 3,0 Zurück zum Inhaltsverzeichnis 4. 2. Externe Kollisionsauflösung Anstelle der Daten enthält die Hash-Tabelle nur Zeiger auf die eigentlichen Daten. Bei einer Kollision wird eine verkettete Liste aufgebaut.

Vorteile gegenüber dem internen Verfahren: Es können auch mehr Sätze gespeichert werden, als eigentlich in der Hash-Tabelle Platz hätten. Der Speicherbereich ist nicht fix, daher wird auch bei geringer Auslastung kein Speicherplatz verschwendet. Beim Löschen und Einfügen werden einfache Listenoperationen getätigt. Nachteile gegenüber dem internen Verfahren: Der Vorteil des Hashings, die direkte Positionierung, geht teilweise verloren (weil man bei Kollisionen die Liste sequentiell durchlesen muß). Bei hoher Auslastung entstehen lange Listen. Beispiel: Angabe wie oben Index Anzahl Liste 1 0   2 2 Carmen, Veronika 3 0   4 1 Tina 5 0   6 1 Renate Zurück zum Inhaltsverzeichnis 5.

Doppeltes Hashing Das doppelte Hashing verwendet die Methode der internen Kollisionsauflösung mit dem Ziel, Clusterbildung zu vermeiden. Das wird erreicht, indem nicht, so wie beim linearen Austesten, bei einer Kollision immer ein konstanter Betrag addiert wird, sondern ein vom Schlüssel abhängiger Wert. Beispiel: H2(K) = 1 + (K / M) mod (M - 1) K ist der Schlüsselwert, M die Größe der Hash-Tabelle. Bei der Division (K / M) handelt es sich um eine Ganzzahldivision. Beispiel: Die Hash-Tabelle bietet Platz für 11 Datensätze. Schlüsselwerte sind Ganzzahlen ("Personen-ID").

Wenn Plätze nicht belegt sind, werden die Personen-ID und der berechnete Index auf -1 gesetzt. 1. Hash-Funktion: H(K) = K mod M 2. Hash-Funktion: H2(K) = 1 + (K / M) mod (M - 1) Einfügen: 37, Huber (Hashcode 4) 25, Meier (3) 20, Schmidt (9) 54, Gruber (10) 42, Stangl (9): H2(42) = 4 tatsächlicher Index berechneter Index Personen-ID Name Anz. Elemente mit diesem Hashcode 0 -1 -1   0 1 -1 -1   0 2 9 42 Stangl 0 3 3 25 Meier 1 4 4 37 Huber 1 5 -1 -1   0 6 -1 -1   0 7 -1 -1   0 8 -1 -1   0 9 9 20 Schmidt 2 10 10 54 Gruber 1   Einfügen: 11, Böck (Hashcode 0) 15, Richter (4): H2(15) = 2 31, Wagner (9): H2(31) = 3 4, Steiner (4): H2(4) = 1 tatsächlicher Index berechneter Index Personen-ID Name Anz. Elemente mit diesem Hashcode 0 0 11 Böck 1 1 9 31 Wagner 0 2 9 42 Stangl 0 3 3 25 Meier 1 4 4 37 Huber 3 5 4 4 Steiner 0 6 4 15 Richter 0 7 -1 -1   0 8 -1 -1   0 9 9 20 Schmidt 3 10 10 54 Gruber 1   Löschen: 15, Richter (Hashcode 4) Einfügen: 16, Bauer (5): H2(16) = 2 Löschen: 42, Stangl (9) tatsächlicher Index berechneter Index Personen-ID Name Anz.

Elemente mit diesem Hashcode 0 0 11 Böck 1 1 9 31 Wagner 0 2 -1 -1 Stangl 0 3 3 25 Meier 1 4 4 37 Huber 2 5 4 4 Steiner 1 6 -1 -1 Richter 0 7 5 16 Bauer 0 8 -1 -1   0 9 9 20 Schmidt 2 10 10 54 Gruber 1 Die durchschnittliche Anzahl der Zugriffe beim Suchen nach einem Datensatz, der tatsächlich in der Tabelle existiert, berechnet sich bei diesem Verfahren nach folgender Formel: -ln (1 - Auslastung) / Auslastung Beim erfolglosen Suchen: 1 / (1 - Auslastung) Beispiele: Auslastung 50 % 70 % 80 % durchschn. Zugriffe bei erfolgloser Suche 2,0 3,3 5,0 durchschn. Zugriffe bei erfolgreicher Suche 1,4 1,7 2,0 Zurück zum Inhaltsverzeichnis

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   Zusammenfassung Der Vorleser

   sachtextanalyse

   interpretation zwist

   Fabel interpretation

   literarische charakteristik

   interpretation bender heimkehr

   felix lateinbuch

   interpretation der taucher von schiller

   textbeschreibung

   charakterisierung eduard selicke
Anmerkungen:

* Name:

* Email:

URL:


* Diskussion: (NO HTML)




| impressum | datenschutz

© Copyright Artikelpedia.com