HashingStreuwertfunktionen

Referat von Kim Schröer – Intelligente Dateisysteme WS13/14

- Übersicht -

• Hashingfunktionen• Ein einfaches Hashing-Schema• Kollisionen• Ein einfacher Hashing-Algorithmus• Progressiver Overflow• Buckets• Löschen von Datensätzen

Hashfunktionen

produzieren immer dann eine Adresse, wenn ein Schlüssel gegeben wird

Ein einfaches Hashing-Schema

• h(k) = a• Bsp: LOWELL

• Name ASCII (2 B.) Product addressLOWELL 76 79 76 x 79 = 6004 004

• h(LOWELL) = 4• home address = 4

Ein einfaches Hashing-Schema

Kollisionen

LOWELL Adresse = 4

OLIVER Adresse = 4

Synonyme

Kollisionen

Kollisionen (Vermeidung)

Eine perfekte Hash-Funktion

Kollisionen reduzieren:1. Verteilen der Datensätze2. Extra Speicher verwenden3. mehr als einen Datensatz einer einzelnen

Adresse zuweisen

Ein einfacher Hash-Algorithmus

• Schritt 1:

LOWELL = 76 79 87 69 76 76 32 32 32 32 32 32

L O W E L L |<- Blanks ->|

Ein einfacher Hashing-Algorithmus

• Schritt 2:76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 327679 + 8769 + 7676 + 3232 + 3232 + 3232 = 33820

Bsp: Grenze von 19937:7679 + 8769 -> 16448 -> 16448 mod 19937 -> 1644816448 + 7676 -> 24124 -> 24124 mod 19937 -> 41874187 + 3232 -> 7419 -> 7419 mod 19937 -> 74197419 + 3232 -> 10651 -> 10651 mod 19937 -> 10651

10651 + 3232 -> 13883 -> 13883 mod 19937 -> 13883

Ein einfacher Hashing-Algorithmus

• Schritt 3:

Bsp: 100 Adressen (0-99)

a = s mod n a = 13883 mod 100

a = 83

Progressiver Overflow

Progressiver Overflow

Buckets

Adresse mit mehr als einem Datensatz

Überlauf von Datensätzen viel seltener

Aufbau eines Buckets

Löschen von Datensätzen

Löschen von Datensätzen

• Irgendwann sehr viele Tombstones• Idee:

Algorithmus überprüft, ob die DS, die nach einem Tombstone kommen, nicht doch in ihre Home-Addresse passen.

Auch die Suchlänge verkürzt sich

Andere Techniken zur Vermeidung von Kollisionen

Double Hashing

Noch Fragen?!

Vielen Dank für die Aufmerksamkeit!

Bsp: einfacher Hash-Algorithmus

int Hash (char key[12], int maxAddress){

int sum = 0;for (int j = 0; j < 12; j += 2)

sum = (sum * 100 * key[j] * key[j+1]) % 19937;return sum % maxAddress;

}

Die Funktion hash verwendet die folding and prime number division, um eine hash Adresse für einen 12 char string.