What's the best hashing algorithm to use on a stl string when using hash_map?
I worked with Paul Larson of Microsoft Research on some hashtable implementations. He investigated a number of string hashing functions on a variety of datasets and found that a simple multiply by 101 and add loop worked surprisingly well.
unsigned inthash( const char* s, unsigned int seed = 0){ unsigned int hash = seed; while (*s) { hash = hash * 101 + *s++; } return hash;}
From some old code of mine:
/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */static const size_t InitialFNV = 2166136261U;static const size_t FNVMultiple = 16777619;/* Fowler / Noll / Vo (FNV) Hash */size_t myhash(const string &s){ size_t hash = InitialFNV; for(size_t i = 0; i < s.length(); i++) { hash = hash ^ (s[i]); /* xor the low 8 bits */ hash = hash * FNVMultiple; /* multiply by the magic number */ } return hash;}Its fast. Really freaking fast.
Boost has an boost::hash library which can provides some basic hash functions for most common types.