Forum: Algorithmen, Datenstrukturen und Klassendesign
by shmia,
20. Mai 2012
Die Standardimplementierung einer Hash-Tabelle sieht so aus, dass es eine bestimmte Anzahl an Buckets (Einträge in einem Array) gibt.
Die Hashfunktion bildet den Schlüssel auf den Index im Array ab.
Sollte ein Bucket aber schon belegt sein, dann nimmt man den nächsten freien Eintrag. ("Linear Probing")
Bei zu hohem Füllungsgrad; also das Array ist schon zu 80% voll; wird immer seltener ein...
Forum: Algorithmen, Datenstrukturen und Klassendesign
by shmia,
19. Mai 2012
Ich denke es hängt auch davon ab, ob die Menge an Schlüsseln sich nie verändert oder ob zur Laufzeit Schlüssel hinzugefügt oder entfernt werden sollen.
a.) feste Menge an Schlüsseln
-> binäre Suche, Interpolationssuche oder quadratische Binärsuche liefert das beste Ergebnis
b.) zur Laufzeit wird eine begrenzte Menge an Schlüsseln hinzugefügt
-> Hashverfahren können genützt werden
Bei zu...
Forum: Algorithmen, Datenstrukturen und Klassendesign
by shmia,
18. Mai 2012
Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.