Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


physik artikel (Interpretation und charakterisierung)

Doppeltes hashing


1. Atom
2. Motor

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

 
 

Datenschutz
Top Themen / Analyse
indicator Thomsonscher Ringversuch
indicator DAS MAGNETISCHE FELD
indicator Direktextrusion von Schlauchfolien
indicator Der Vergrößerer
indicator Der Diesel
indicator Der Verbraucher:
indicator Unbemannte Raumfahrtprogramme
indicator Koma
indicator Energiegewinnung im Atomkraftwerk
indicator TURBOLADER


Datenschutz
Zum selben thema
icon Transistor
icon Energie
icon Schall
icon Einstein
icon Kernfusion
icon Bomben
icon Strahlung
icon Magnet
icon Kohäsion
icon Welle
icon Diamant
icon Newton
icon Blitz
icon Adhäsion
icon Biomasse
icon Gleitreibung
icon Dichte
icon Watt
icon Entwicklung
icon Otto
icon Laser
icon Reaktor
icon Widerstand
icon Kraft
icon Mikroskope
icon Dynamik
icon Turbine
icon Herstellung
icon Elektrizität
icon Gesetz
icon Strahlung
icon Theorie
icon Kapazität
icon Haftreibung
icon Transformator
icon Wirkung
icon Mechanik
A-Z physik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.
dsolution