proggen.org

Xin hat geschrieben:

mfro hat geschrieben: ...
Das hat allerdings den möglicherweise unerwünschten Seiteneffekt, dass für nicht erkannte Zeichen neue "leere" Map-Einträge erzeugt werden (was dann allerdings auch bedeutet, dass die gehasht werden und das Programm mit mehr solcher Einträge immer schneller werden müsste).

Dass es schneller wird, halte ich für eine interessante Theorie, ich würde jetzt eher vermuten, je voller die map, desto langsamer...

Ich habe da an etwas Spezielleres gedacht: so ungefähr das Langsamste, was einem mit einer Hashmap passieren kann, ist die Suche in einer ziemlich vollen Map nach einem nicht vorhandenen Schlüssel. Das müsste m.E. schneller werden.

Die Idee einer Hashmap ist ja, dass die Tabelle klein bleibt (um Speicherplatz zu sparen) und der Key zu einem Hash-Wert geändert wird. So könnte man ein char einfach % 16 rechnen und hätte eine Tabelle mit 16 Einträgen, die zum Beispiel auf eine Liste von maximal 16 Key-Value-Paaren verweisen würde, womit die durchschnittliche Suche eines voll besetzten Datensatzes von 128 Vergleichen auf 8 reduziert wird. Je leere die Listen sind, desto schneller ist man aber auch durch. Wenn die Liste nach dem Hash nun 3 Elemente hat, weiß man nach dem dritten Element, dass der gesuchte Key nicht existiert. Legt man ihn nun an, kostet das Zeit und man macht nun vier Vergleiche für den nächsten nicht existierenden Key.
Ich glaube, meine Lösung ist schneller. ^^

Xin hat geschrieben:... So könnte man ein char einfach % 16 rechnen und hätte eine Tabelle mit 16 Einträgen, die zum Beispiel auf eine Liste von maximal 16 Key-Value-Paaren verweisen würde, womit die durchschnittliche Suche eines voll besetzten Datensatzes von 128 Vergleichen auf 8 reduziert wird. ...

Das könnte man. Wenn man täte. Ich habe da mal ein wenig weiter geforscht.

Tatsächlich sieht's aber so aus, dass std::hash<char> für unseren char-Key einen prima 4 bytes langen int-Hash bastelt, in dem es unseren (signed) char vorzeichenrichtig auf 32 Bit erweitert. Wir reden also - wie's aussieht - tatsächlich von einer eher dünn besetzten Hash-Tabelle ...

mfro hat geschrieben:Tatsächlich sieht's aber so aus, dass std::hash<char> für unseren char-Key einen prima 4 bytes langen int-Hash bastelt, in dem es unseren (signed) char vorzeichenrichtig auf 32 Bit erweitert. Wir reden also - wie's aussieht - tatsächlich von einer eher dünn besetzten Hash-Tabelle ...

Und hast Du mal nachgeforscht, wie groß die Tabelle ist? 32 Bit erlaubt 4 Milliarden Hash-Werte. Mit 8 Multipliziert, also der nachfolgenden Adresse, sind das 32GB für die Tabelle, die dann wirklich sehr dünn besetzt ist. Ich glaube aber nicht, dass die so groß ist