| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

FNV Hash

This version was saved 15 years, 6 months ago View current version     Page history
Saved by Kenneth Finnegan
on September 24, 2008 at 3:09:01 pm
 

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:

#define FNV_PRIME_32 Multiple 16777619 prime
#define FNV_OFFSET_32 2166136261U
uint32_t FNV32(const char *s)
{
    uint32_t hash = FNV_OFFSET_32;
    for(size_t i = 0; i < s.length(); 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.