Super high performance C/C++ hash map (table, dictionary)

I need to map primitive keys (int, maybe long) to struct values in a high-performance hash map data structure.

My program will have a few hundred of these maps, and each map will generally have at most a few thousand entries. However, the maps will be "refreshing" or "churning" constantly; imagine processing millions of add and delete messages a second.

What libraries in C or C++ have a data structure that fits this use case? Or, how would you recommend building your own? Thanks!

I would recommend you to try Google SparseHash (or the C11 version Google SparseHash-c11) and see if it suits your needs. They have a memory efficient implementation as well as one optimized for speed. I did a benchmark a long time ago, it was the best hashtable implementation available in terms of speed (however with drawbacks).

> What libraries in C or C++ have a data structure that fits this use case? Or, how would you recommend building your own? Thanks!

Check out the LGPL'd Judy arrays. Never used myself, but was advertised to me on few occasions.

You can also try to benchmark STL containers (std::hash_map, etc). Depending on platform/implementation and source code tuning (preallocate as much as you can dynamic memory management is expensive) they could be performant enough.

Also, if performance of the final solution trumps the cost of the solution, you can try to order the system with sufficient RAM to put everything into plain arrays. Performance of access by index is unbeatable.

> The add/delete operations are much (100x) more frequent than the get operation.

That hints that you might want to concentrate on improving algorithms first. If data are only written, not read, then why write them at all?

Just use boost::unordered_map (or tr1 etc) by default. Then profile your code and see if that code is the bottleneck. Only then would I suggest to precisely analyze your requirements to find a faster substitute.

If you have a multithreaded program, you can find some useful hash tables in intel thread building blocks library. For example, tbb::concurrent_unordered_map has the same api as std::unordered_map, but it's main functions are thread safe.

Also have a look at facebook's folly library, it has high performance concurrent hash table and skip list.

khash is very efficient. There is author's detailed benchmark: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ and it also shows khash beats many other hash libraries.

from android sources (thus Apache 2 licensed)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

look at hashmap.c, pick include/cutils/hashmap.h, if you don't need thread safety you can remove mutex code, a sample implementation is in libcutils/str_parms.c

First check if existing solutions like libmemcache fits your need.

If not ...

Hash maps seems to be the definite answer to your requirement. It provides o(1) lookup based on the keys. Most STL libraries provide some sort of hash these days. So use the one provided by your platform.

Once that part is done, you have to test the solution to see if the default hashing algorithm is good enough performance wise for your needs.

If it is not, you should explore some good fast hashing algorithms found on the net

1. good old prime number multiply algo

2. http://www.azillionmonkeys.com/qed/hash.html

3. http://burtleburtle.net/bob/

4. http://code.google.com/p/google-sparsehash/

If this is not good enough, you could roll a hashing module by yourself, that fixes the problem that you saw with the STL containers you have tested, and one of the hashing algorithms above. Be sure to post the results somewhere.

Oh and its interesting that you have multiple maps ... perhaps you can simplify by having your key as a 64 bit num with the high bits used to distinguish which map it belongs to and add all key value pairs to one giant hash. I have seen hashes that have hundred thousand or so symbols working perfectly well on the basic prime number hashing algorithm quite well.

You can check how that solution performs compared to hundreds of maps .. i think that could be better from a memory profiling point of view ... please do post the results somewhere if you do get to do this exercise

I believe that more than the hashing algorithm it could be the constant add/delete of memory (can it be avoided?) and the cpu cache usage profile that might be more crucial for the performance of your application

good luck

Try hash tables from Miscellaneous Container Templates. Its closed_hash_map is about the same speed as Google's dense_hash_map, but is easier to use (no restriction on contained values) and has some other perks as well.

I would suggest uthash. Just include #include "uthash.h" then add a UT_hash_handle to the structure and choose one or more fields in your structure to act as the key. A word about performance here.

http://incise.org/hash-table-benchmarks.html gcc has a very very good implementation. However, mind that it must respect a very bad standard decision :

> If a rehash happens, all iterators are invalidated, but references and > pointers to individual elements remain valid. If no actual rehash > happens, no changes.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

This means basically the standard says that the implementation MUST BE based on linked lists. It prevents open addressing which has better performance.

I think google sparse is using open addressing, though in these benchmarks only the dense version outperforms the competition. However, the sparse version outperforms all competition in memory usage. (also it doesn't have any plateau, pure straight line wrt number of elements)