CODEWITHSUNDEEP
c++stringdictionaryhash
Kacper Fałat
Kacper Fałat

Reputation: 23

String versus hash as map key - performance

Currently im writing log system for my game engine.

And to keep everything clear i must give name for each of Logger object. Logger objects are stored in LogManager class which keeps track of every Logger instance. Map is storing pointer to Logger instance, as key is using std::string which represents name.

I'm developing realtime 3D engine so reducing latecny is very important. So i figured second way to store it - use fast hash algorithm (for ex. MurMur Hash 3) and store only 64 bit hash instead of string.

And now, my question : Is using hash instead of string as map key value is better in performance at runtime (in my and in global case) ?

@Edit Access Code

    std::map<std::string, CLogger*> map1;
std::map<QWORD, CLogger*> map2;

// access :
CLogger * logger = map1["root"];
CLogger * logger = map2[getHashedString("root")];

//

QWORD getHashedString(const std::string string)
{
    QWORD val = 0;
    hash_x64_128(string.c_str(), string.length(), 1234, &val);
    return val;
}

Algorithm used above is MurMur Hash 3 (https://code.google.com/p/smhasher/source/browse/branches/chandlerc_dev/MurmurHash3.cpp)

Best Regards.

Upvotes: 2

Views: 1588

Answers (2)

Gabor Angyal
Gabor Angyal

Reputation: 2255

Definitly. But make sure that the generated hash codes are unique. The performance gain also depends on the map implementation you are using. For example stl::map uses a search tree to store the keys. In this case you can save a lot of string comparision. If you are using stl::unordered_map you gain less, as it already uses hash values. But you can still save some runtime on hash calculation if you do it cleverly.

A very important thing: measure runtime before and after optimization ;)

Upvotes: 1

Tasos Vogiatzoglou
Tasos Vogiatzoglou

Reputation: 2453

Could you provide some code accessing the map ?

The difference between calculating your own hash and having the accessor calculating the hash is that maybe by using your own hash the Hash parameter of map becomes the identity function.

Upvotes: 0

Related Questions