Fast String Hashing Algorithm with low collision rates with 32 bit integer

Question

I have lots of unrelated named things that I'd like to do quick searches against. An "aardvark" is always an "aardvark" everywhere, so hashing the string and reusing the integer would work well to speed up comparisons. The entire set of names is unknown (and changes over time). What is a fast string hashing algorithm that will generate small (32 or 16) bit values and have a low collision rate?

I'd like to see an optimized implementation specific to C/C++.

Answer 1

Murmur Hash is pretty nice.

Answer 2

One of the FNV variants should meet your requirements. They're fast, and produce fairly evenly distributed outputs.

Answer 3

There's also a nice article at eternallyconfuzzled.com.

Jenkins' One-at-a-Time hash for strings should look something like this:

#include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
        hash += *s;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

Answer 4

For a fixed string-set use gperf.

If your string-set changes you have to pick one hash function. That topic has been discussed before:

What's the best hashing algorithm to use on a stl string when using hash_map?

Answer 5

Another solution that could be even better depending on your use-case is interned strings. This is how symbols work e.g. in Lisp.

An interned string is a string object whose value is the address of the actual string bytes. So you create an interned string object by checking in a global table: if the string is in there, you initialize the interned string to the address of that string. If not, you insert it, and then initialize your interned string.

This means that two interned strings built from the same string will have the same value, which is an address. So if N is the number of interned strings in your system, the characteristics are:

• Slow construction (needs lookup and possibly memory allocation)
• Requires global data and synchronization in the case of concurrent threads
• Compare is O(1), because you're comparing addresses, not actual string bytes (this means sorting works well, but it won't be an alphabetic sort).

Cheers,

Carl

Answer 6

It is never late for a good subject and I am sure people would be interested on my findings.

I needed a hash function and after reading this post and doing a bit of research on the links given here, I came up with this variation of Daniel J Bernstein's algorithm, which I used to do an interesting test:

unsigned long djb_hashl(const char *clave)
{
    unsigned long c,i,h;

    for(i=h=0;clave[i];i++)
    {
        c = toupper(clave[i]);
        h = ((h << 5) + h) ^ c;
    }
    return h;
}

This variation hashes strings ignoring the case, which suits my need of hashing users login credentials. 'clave' is 'key' in Spanish. I am sorry for the spanish but its my mother tongue and the program is written on it.

Well, I wrote a program that will generate usernames from 'test_aaaa' to 'test_zzzz', and -to make the strings longer- I added to them a random domain in this list: 'cloud-nueve.com', 'yahoo.com', 'gmail.com' and 'hotmail.com'. Therefore each of them would look like:

test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, 
test_aaac@gmail.com, test_aaad@hotmail.com and so on.

Here is the output of the test -'Colision entre XXX y XXX' means 'Collision of XXX and XXX'. 'palabras' means 'words' and 'Total' is the same in both languages-.

    Buscando Colisiones...
    Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
    Total de Colisiones: 11
    Total de Palabras  : 456976

That is not bad, 11 collisions out of 456,976 (off course using the full 32 bit as table lenght).

Running the program using 5 chars, that is from 'test_aaaaa' to 'test_zzzzz', actually runs out of memory building the table. Below is the output. 'No hay memoria para insertar XXXX (insertadas XXX)' means 'There is not memory left to insert XXX (XXX inserted)'. Basically malloc() failed at that point.

    No hay memoria para insertar 'test_epjcv' (insertadas 2097701).

    Buscando Colisiones...

    ...451 'colision' strings...

    Total de Colisiones: 451
    Total de Palabras  : 2097701

Which means just 451 collisions on 2,097,701 strings. Note that in none of the occasions, there were more than 2 collisions per code. Which I confirm it is a great hash for me, as what I need is to convert the login ID to a 40 bit unique id for indexing. So I use this to convert the login credentials to a 32 bit hash and use the extra 8 bits to handle up to 255 collisions per code, which lookign at the test results would be almost impossible to generate.

Hope this is useful to someone.

EDIT:

Like the test box is AIX, I run it using LDR_CNTRL=MAXDATA=0x20000000 to give it more memory and it run longer, the results are here:

Buscando Colisiones... Total de Colisiones: 2908 Total de Palabras : 5366384

That is 2908 after 5,366,384 tries!!

VERY IMPORTANT: Compiling the program with -maix64 (so unsigned long is 64 bits), the number of collisions is 0 for all cases!!!

Answer 7

The Hsieh hash function is pretty good, and has some benchmarks/comparisons, as a general hash function in C. Depending on what you want (it's not completely obvious) you might want to consider something like cdb instead.

Answer 8

Why don't you just use Boost libraries? Their hashing function is simple to use and most of the stuff in Boost will soon be part of the C++ standard. Some of it already is.

Boost hash is as easy as

#include <boost/functional/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;

    std::size_t h = string_hash("Hash me");
}

You can find boost at boost.org

Answer 9

Bob Jenkins has many hash functions available, all of which are fast and have low collision rates.

Answer 10

Have a look at GNU gperf.

Answer 11

There is some good discussion in this previous question

And a nice overview of how to pick hash functions, as well as statistics about the distribution of several common ones here

Answer 12

You can see what .NET uses on the String.GetHashCode() method using Reflector.

I would hazard a guess that Microsoft spent considerable time optimising this. They have printed in all the MSDN documentation too that it is subject to change all the time. So clearly it is on their "performance tweaking radar" ;-)

Would be pretty trivial to port to C++ too I would have thought.

Answer 13

Described here is a simple way of implementing it yourself: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

A snippet from the post:

if say we have a character set of capital English letters, then the length of the character set is 26 where A could be represented by the number 0, B by the number 1, C by the number 2 and so on till Z by the number 25. Now, whenever we want to map a string of this character set to a unique number , we perform the same conversion as we did in case of the binary format

Answer 14

CRC-32. There is about a trillion links on google for it.