Hello everyone. I need a very fast container, for an app which indexes words (web pages) (written in c++/linux, stl containers). I used maps, which are very popular (recomended on programming forums), then i moved to hash_map which brought significant speed gain. However when my hash_maps are growing, as the program indexes more words, the program slows down considerably. My questions:

1. Is there any other container faster than hash_map ?
2. Using other hashing function that the default one provided by hash_map (used for hashing strings, as keys for my hash_map), could I expect significant speed improvement ? (i.e. I tried SuperFastHash, which I found it @ http://www.azillionmonkeys.com/qed/hash.html).



Thank you people for your time !

You're assuming that the program is slowing down because the algorithm your particular hash_map is using doesn't scale well. I agree - that's probably the case.

But maybe the problem is insufficient RAM: as you add more strings, your program uses lots more memory ... and at some point, you begin swapping. And the program slows because of the SWAPPING, not because of the algorithm.

You could easily verify it by running "swapon -s" and/or "vmstat" when your program slows down.

Just a thought...

Thank you for time !

I really don't think that's the case: my app is running on dual processor system with plenty of RAM (1Gb Ram). I tried to run my app while no other appz/servers where running , but I get the very same behavior ;-(

A hash_map is only as good as its hash. As you add more data the likelihood of a collision increases. I don't know what the default hash function is for char *, but knowing that the inputs are (case insensitive?) words, you can probably improve it.

As a guess I would try a huffman encoded version of the string, using the frequencies of letters in dictionary words. But with some thought you can probably do much better.

None taken. I think it was funny ;-). I asked myself too, about that default hash on char *, which caused me a lot of head eachs when i first tried to use hash_map on std::string ;-)