Please explain murmur hash?

algorithm hashtable collision
jaka picture jaka · Jun 29, 2009 · Viewed 17.8k times · Source

I just found out murmur hash, seems to be the fastest known and quite collision resistant. I tried to dig more about the algorithm or implementation in full source code, but I am having difficulty understanding it. Could someone here explain the algorithm used, or implement it in full source code, preferably in C. I read the C source code from the author website but has no idea, like: What is seed, h, k, m?

What does this mean? :

k *= m; 
k ^= k >> r; 
k *= m; 
    
h *= m; 
h ^= k;

data += 4;
len -= 4;

Reference : http://murmurhash.googlepages.com/

Answer

Howard May picture Howard May · Jun 29, 2009

The code is available here . m and r are constants used by the algorithm. k *= m means take variable k and multiple it by m. k ^= k >> r means take k and right shift the bits r places (e.g. if r is 2 110101 would become 001101) and then XOR it with k.

Hope that gives you enough to work through the rest.

Regards

Related questions

hash function for string

I'm working on hash table in C language and I'm testing hash function for string. The first function I've tried is to add ascii code and use modulo (%100) but i've got poor results with the first test of data: 40 collisions …

Read More
Hash table runtime complexity (insert, search and delete)

Why do I keep seeing different runtime complexities for these functions on a hash table? On wiki, search and delete are O(n) (I thought the point of hash tables was to have constant lookup so what's the point if …

Read More
Binary Trees vs. Linked Lists vs. Hash Tables

I'm building a symbol table for a project I'm working on. I was wondering what peoples opinions are on the advantages and disadvantages of the various methods available for storing and creating a symbol table. I've done a fair bit …

Read More