C# implementation of FNV Hash

Question

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?

Rumilly

It looks fine to me... you shoudl just close hash ^ x in brackets - e.g. (hash ^ x) * prime - otherwise the multiplication will be performed first. – Sotted

A 2023 answer to this would be to use HashCode.Combine(EntityId, FromDate, ToDate). – Aekerly

@Aekerly If the OP is doing an FNV-1a implementation, why would they use a method that uses a different algorithm? – Equation

Yeah, I'm not sure why FNV was selected. It does look like the intent is to override GetHashCode by combining the hash codes of several properties. This is exactly what HashCode.Combine does, without having to worry about the implementation. – Aekerly

Answer 1

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);
}

Salesin

nice. I never thought of using Linq for something like that, but it makes perfect sense. Small, concise. :) Thanks – Rumilly

GetHashCode should never allocate memory on the heap. – Sauternes

Huh? Where does it ever allocate memory on the heap? – Rumilly

@Rumilly The params will result in a heap allocation for the array. – Salesin

FNV collects octets/bytes, not hashcodes (ints). I wonder if that makes a difference for hashtables, if for example, EntityId goes up from 1 to well above 255. FYI I've doing the same. – Wundt

This will also allocate for the Aggregate call, and (potentially) for the lambda expression. While this is nice and succinct, if performance matters in your scenario it's worth unrolling the loop and writing a few extra lines of code to avoid allocations. – Sarraute

Answer 2

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().

Freya