Search code examples
chashfnv

FNV hashing for strings in C

Here is what the algorithm says.

hash = FNV_offset_basis
for each octet_of_data to be hashed
    hash = hash * FNV_prime
    hash = hash XOR octet_of_data
return hash

but if i have a set of strings then what shall i take as the FNV_offset_basis,

and what is the meaning of for each octet of data to be hashed.

Also what should be the size of table, say there are N strings to be hashed.

Kindly help me with the modifications for the strings.

Thanks.

Solution

  • From the web site referenced in the comment above,

    32 bit offset_basis = 2166136261

64 bit offset_basis = 14695981039346656037

    use the one that corresponds to the width of your hash.

    An octet is an 8-bit byte. If you are using text with 8-bit characters, an octet and a character are the same thing.

    The size of the table is up to you; be sure to make it bigger than N of course! The bigger it is, the fewer collisions you should expect.