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

tl;dr: 

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  

Boost: 
======
hash_combine

Advertisements

About Alexis Chan

https://alexisylchan.wordpress.com/about/
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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s