Alternative to stdext::hash_map for performance reasons

Question

I'm working on a high performance application where all calls must be justified. I have a map that is used once in the beginning of each transaction to do a lookup that I would like to improve upon. The map is loaded at startup and does not change after that.

The key in the map below is an std::string but it can it changed to a char array if needed. C or C++ as a solution is fine.

  typedef stdext::hash_map<std:string, int> symbols_t;

Does anyone know of any other solutions that would eliminate the lookup or be faster?

Thanks ahead of time for your help.

Additional info from edits:
1. The hash_map currently has 350,000 elements.
2. Each key value is typically between 4 and 10 characters in length.
3. Information is received on a callback from a third party API. The callback is given a symbol that is used as the key value when doing a the map lookup. The rest of the software is driven off of the int returned from the map lookup.

THANKS: Thanks all for your input. You've given me a few avenues to explore. I will definitely try these out. I appreciate the help.

Answer 1

Is this map completely constant or changes between program invocations? For constant hashes (known at compile time) there is gperf program, which generates fast and guaranteed O(1) lookup table.

Also, it could help to understand you problem if you tell us why and how exactly map lookups slow down your code.

Answer 2

A hash table is usually fast enough O(1) and we cannot tell you if you can get rid of the hash table without knowing the whole structure of your application. It may not be possible.

I don't know how is implemented stdext::hash_map<std::string,T> , but a prefix tree is a possibly better solution. It is equivalent to a hash table with a perfect hash function.

      s
      |
      t
    /   \
   o     a
   |     |
(p,42)   r
         |
       (t,69)

It will give you the value corresponding to your string in O(1) maximum 10 iterations (max length of the string) and will minimize the space cost of storing keys.