C++ STL Hashmaps

Note:  STL here refers to SGI STL , not to be confused with the C++ Standard Library , which only recently include hash maps/sets in C++11 . For pre-C++11 users, hash maps/sets are included under the name unordered_map/unordered_set in std::tr1 as explained in the article:

From: http://www.drdobbs.com/cpp/c-stl-hash-containers-and-performance/198800559


hash_maps store key/value pairs that have unique keys.
hash_sets store unique values.
hash_multimaps store key/value pairs with nonunique keys.
hash_multisets store nonunique values  

When to use hash functions: 
trade offs - how often do the key/value pair change 
vs frequency & performance of accesses 
vs memory allocation
Hash function:
Most primitives hash to themselves: integers, 
characters, and longs all simply cast to size_t

SizeTCastHasher - hash based on memory location

ShiftedPairHasher - hash a pair of integers 
(bitwise shift first integer, then XOR, to fit 
both integers in a size_t)  
Memory allocation: 
Map --> RB tree , a few pointers, 
Hashmap - 193 buckets  

Must Benchmark: 
Hash function calculation time 
vs hash function collision resolution  



About Alexis Chan

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s