| 
View
 

FNV Hash

Page history last edited by Kenneth Finnegan 16 years, 2 months ago

Hashes are used to assign some form of identification to a piece of information.  The trick is that every time that information is hashed, it results in the same identification.  This is useful for tracking files to see if they've changed, or for using hash tables to store large sets of data.

 

This code is based on the FNV hash, but is greatly simplified for clarity.  If you're planning on using it for a real application, I urge you to download the original source, which does serveral tests to ensure portability and speed.

 

This sample code only demonstrates the 32 bit version of the hash.  It also comes in 64, 128, 256, 512, and 1024 bit version, which require different constants.

 

Code:

#include <string.h>
#define FNV_PRIME_32 16777619
#define FNV_OFFSET_32 2166136261U
uint32_t FNV32(const char *s)
{
    uint32_t hash = FNV_OFFSET_32, i;
    for(i = 0; i < strlen(s); i++)
    {
        hash = hash ^ (s[i]); // xor next byte into the bottom of the hash
        hash = hash * FNV_PRIME_32; // Multiply by prime number found to work well
    }
    return hash;
} 

 

Usage:

char *teststring = "This is a test";
uint32_t hash_of_string = FNV32(teststring);

// This is technically the FNVa hash, which reverses the xor and
// multiplication, but is believed to give better mixing for short strings
// (ie 4 bytes).

 


Extensions:

To decrease the inevitable collisions, use the 64 bit variant of the hash.

 

To translate the hash to any other size (ie 24 bit, 56 bit, etc), right shift the top of the hash and xor with the bottom:

uint32_t hash24 = (hash32>>24) ^ (hash32 & 0xFFFFFF);

 


Sources:

http://isthe.com/chongo/tech/comp/fnv/

http://stackoverflow.com/questions/114085/

http://stackoverflow.com/questions/98153/

Comments (0)

You don't have permission to comment on this page.