CODEWITHSUNDEEP
c#.nethashfnv
Keith
Keith

Reputation: 1129

C# implementation of FNV Hash

I have had numerous cases where I need access to a decent hashing algorithm in C#, from overriding GetHashCode to performing quick comparisons/lookups against data.

I have found the FNV hash to be a really easy/good/quick hash algorithm. However, I have never seen a good example of a C# implementation.

The core of the FNV-1a hash algorithm is as follows:

 hash = OFFSET_BASIS
 foreach (object value in object) 
 {
     hash = hash ^ value.GetHashCode()
     hash = hash * FNV_PRIME
 }

So, when I override GetHashCode for a class I end up doing something like:

public static class FNVConstants
{
    public static readonly int OffsetBasis = unchecked((int)2166136261);
    public static readonly int Prime = 16777619;
}

public override int GetHashCode()
{
    int hash = Constants.FNVConstants.OffsetBasis;
    hash = (hash ^ EntityId.GetHashCode()) * Constants.FNVConstants.Prime;
    hash = (hash ^ FromDate.GetHashCode()) * Constants.FNVConstants.Prime;
    hash = (hash ^ ToDate.GetHashCode()) * Constants.FNVConstants.Prime;
    return hash;
}

What do people think of this?

Upvotes: 11

Views: 11422

Answers (2)

James H
James H

Reputation: 1

For anyone else who comes across this thread looking for an FNV-1a implementation in C#, The FNV algorithm calls for an xor of the hash and each octet of the input:

hash = offset_basis
for each octet_of_data to be hashed
  hash = hash xor octet_of_data
  hash = hash * FNV_Prime
return hash

Object.GetHashCode() returns a 32 bit integer. I believe a strict implementation of FNV-1a (ignoring considerations for endianness) would look more along the lines of:

hash = OFFSET_BASIS

foreach (object value in object) 
{
    var hashCode = value.GetHashCode();
    var octets = BitConverter.GetBytes(hashCode);

    foreach(var octet in octets)
    {
        hash = hash ^ octet;
        hash = hash * FNV_PRIME;
    }
}

return hash;

I'm not clear on what the effect of using the full 32 bit integer instead of individual octets is on hash distribution. There's a good outline of the algorithm here, along with some interesting history on it's usage.

If you're looking to implement a deterministic hashing solution, the code above will not work. Object.GetHashCode() is not stable across runs and will produce different results. You need to implement the FNV algorithm without using either the built in implementation of the HashCode class or Object.GetHashCode().

Upvotes: 0

juharr
juharr

Reputation: 32266

You could add this to your FNVConstants class

public static int CreateHash(params object[] objs)
{
    return objs.Aggregate(OffsetBasis, (r, o) => (r ^ o.GetHashCode()) * Prime);
}

Then call it like 

public override int GetHashCode()
{
    return FNVConstants.CreateHash(EntityId, FromDate, ToDate);
}

Upvotes: 9

Related Questions