Hashing Problem

[negaH]

Zitat:

1024 .. also so wenig Einträge sind es halt nicht.

Bei 1024 Einträgen würdest du nach 10 Vergleichen mit Werten aus dem Array herausfinden ob der aktuelle 64Bit Wert schon im Array ist. Bzw. in 10 Vrgleichen würdest du die EInfügeposition ermitteln können.
Bei 2048 Einträgen wären 11 Vergleiche nötig, da 2^11 = 2048. Somit bei 65535 Einträgen nut 16 Vergleiche. Die Anzahl dieser Vergleiche ist die Anzahl im Worst Case, also im schlechtesten Falle. Im Durchschnitt würden man aber bei 2^16 Elementen im Array nur 8 Vergleiche benötigen !

Schneller kann eine Hashfunktion auch nicht sein. Eine hashfunktion würde diese 2^16 Elemente durch ein Array von z.B. 1024 Word's beschreiben. D.h. 1 Eintrag im hasharray ist der Index in eine Int64 Tabelle. Man zieht vom in64 ein 16Bit Hash der dann an die Position im array positioniert. So, bei 1024 Haswerten im hasharray würden 65535/1024 = 64 Duplikate pro hashwert möglich sein. D.h. jeweils 64 Int64 Werte teilen sich ein und selben Hashwert. Somit würde die hashtabelle beim Heraussuchen von 65535 Werten a 64Bit mit einer Berechnung 63/64 aller Werte ausfiltern. Die restlichen 64 Werte müssten wiederum ber Vergleichssuche gefunden werden. Nimmt man dafür eine Binäre Suche so wären 6 Vergleiche nötig. D.h. insgesamt würde eine Hashtabelle 4 Vergleiche im Duerchschnitt benötigen, im Gegensatz zu 8 bei einer reinen binären Suche. Dafür benötigt die hashtabelle ein wesentlich komplexerer Struktur die ihre Zeit kostet. In deinem Falle wäre dieser Zeitliche Aufwand aber der Performancebestimmende Faktor.

Gruß Hagen