Dictionary statt binärer Suche?

[Dejan Vu]

Na ja, und diese Werte sind vermutlich nicht ganz so unterschiedlich, wie man das gerne hätte. Hier im Forum , gibt's doch diverse alternative Implementierungen, die brauchbar sind, oder nicht? Da muss man nicht schauen, wie Emba das macht.

Die Hashfunktion überführt den Schlüssel in einen Wertebereich, der in die interne Implementierung der Dictionary passt: Meist ist das ein Array[X], wobei X i.a. eine Primzahl ist.
Wenn das Array 'voll' ist (mehr oder minder), dann wird das Array vergrößert (auf z.B. Y)und alle Hashwerte neu berechnet. Dieses mal werden die Hashwerte aber auf den größeren Wertebereich gemappt.
Dabei kann das Umschlüsseln durchaus langsam sein (relativ zu einem einfach insert), aber im Durchschnitt ist die Einfügeoperation dennoch sehr schnell. Wieso? Man muss sich nur mal überlegen, was alles passiert:
1x Hash berechnen und auf Wertebereich Mappen (mit Modulo). Das ist der Index in das Array.
Wenn Array [Index]=Frei, dann Value dort reinpacken und fertig.
Sonst ist im Array z.B. eine Liste. Wenn man hier eine verkettete Liste nähme, müsste man den neuen Wert nur in die Liste einhängen. Auch sehr schnell.

Also nochmal: 1x Hash berechnen, 1x Modulo. Fertig.
Nur wenn die Liste voll wird (oder die Hashfunktion Müll, hallo Sir Rufo), muss man den minimalen Overhead für das Einhängen in die Liste einberechnen.

Aber selbst ein Hash über einen String ist da noch sauschnell.