Hashing Problem

[negaH]

Nochmal genauer: Zu jedem 64Bit Wert = äquivalent zu deinem A: array[0..63] of Boolean, wird per Hashfunktion ein 32Bit Hash erzeugt. Da dieser logischer weise niemals alle möglichen 2^64 Werte representieren kann muß man, wenn die Hashtabelle funktionieren soll, auch alle der in der Hashtabelle gehashten 64 Bit Werte gespeichert werden. D.h. also, du musst auf Platte die 2^32 Hashwerte + alle 64Bit Werte die die Hash Tabelle representiert speichern. NUR die Hashtabelle zu speichern bringt rein garnichts, da jeder 32 Bit Hash nur 1/2^32'tel aller möglichen 64 Bit Werte EINDEUTIG beschreibt !
Deine Hashtabelle würde also im schlechtesten Falle 2^32 * 4 Bytes Hash + 2^32 * 2^32 * 8 Bytes Werte speichern müssen. In diesem Falle wären ALLE 64 Bit Werte durch diese Tabellen gespeichert wurden. Nun kannst du per Wahrscheinlichkeiten diese Werte runterrechnen, und wirst immer feststellen das eine Hash Tabelle immer schlechter abschneidet als ein einfaches Array of Int64. Beim Array of Int64 hast du eben nur das Problem das beim Einfügen in dieses Array von einem Element alle nachfolgenden Element um eine Position verschoben werden müssen. Dies kann man aber extrem effizient gestalten, wenn man mit temporären Zwischenarrays arbeitet. D.h. man hat das Hauptarray das sortiert Int64 Werte enthält. Nun speichert man die nächsten 256 Int64 Werte in ein anderes array das ebefalls sortiert ist. Ist dieses array mit 256 Elementen voll, so wird dieses array in das große array eingefügt. Man macht dies indem man das große array um 256 Elemente vergrößert, nun fängt man von hinten nach vorne an die Elemente aus dem kleinen array in das große array einzufügen. Dabei wird einfach solange die Elemente im großen array an die höchste Position kopiert bis man ein Element im kleinen array findet das größer als das nächtse im großen array wäre. Diese Element fügt man dann ein usw. usw. bis das kleine array leer ist.
Somit würde dieser Einfügealgortihmus nur alle 256 Einfügeelemente mal, das große array umkopieren. Zudem würde die Wahrscheinlichkeiten und die Menge aller umzukopierenden Elemente auf ein Minimum reduziert.

Will man nun wissen ob ein neues Element schon in der List vorhanden ist dann müsste man per binärer Suchen nun 2 arrays durchsuchen. Bei 2^16 Einträgen im großen Array und 2^8 im kleinen array müsste man im schlechtesten Falle 24 Vergleiche durchführen. Das ist aber von der Komplexität besser als eine Hashliste da der Speicherverbrauch exakt 64Bit*Anzahl Einträge wäre. Bei einer Hashliste wäre der minimale Speicherverbrauch 2^32 * 32Bit + Anzahl Einträge * 64 Bit.


Gruß Hagen