Re: hash_map

[Bernd Strieder]

Hello,

Michael Schuster wrote:

> Hi,
> I'm using std::map<std::string, int*>  with a lot of elements. As I
> thought hash_map would be a better choice, I tried to find out the
> improvements.I managed to get it working (after some googling). Ok,
> now my programm works with __gnu_cxx::hash_map but is awfully slow!
> I also tried STLPort's hash_map, but this hash_map really increases
> the speed of my app (~20%). Is there a better version of hash_map
> planed?

When comparing strings with <, often only few letters have to be
considered. When calculating a hash function of a string usually all
letters go into the calculation. Hashing means objects go into buckets.
Comparisions will have to be done to identify objects within a bucket .
If the hash table is too small, the buckets will be large, and quite
some comparisions will have to be done.

The only good advice I can give on hashing, read some textbook about it,
e.g. D.E.Knuths Sorting and Searching, and think well about the
parameters you provide. There is no simple set of rules to get hashing
right in all cases.

>From what you have written, it is not possible to see, whether you mean,
that hash_map is slow in the average case, whether the worst case is
slow, how your hash_map is tuned, and what hashing function you have
used, etc. Your problem is not clear enough to give any specific
advice.

Bernd Strieder