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?

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. — digEmAll, Dec 20 '12 at 14:45
A 2023 answer to this would be to use `HashCode.Combine(EntityId, FromDate, ToDate)`. — dana, Jan 10 '23 at 04:10
@dana If the OP is doing an FNV-1a implementation, why would they use a method that uses a different algorithm? — Peter Ritchie, Jun 13 '23 at 14:57
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. — dana, Jun 17 '23 at 17:08

score 7 · Accepted Answer · answered Dec 20 '12 at 14:45

7

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

answered Dec 20 '12 at 14:45

juharr

31,741
4
58
93

nice. I never thought of using Linq for something like that, but it makes perfect sense. Small, concise. :) Thanks – Keith Jan 28 '13 at 20:55
5

GetHashCode should never allocate memory on the heap. – Frank Hileman Mar 15 '13 at 19:30
Huh? Where does it ever allocate memory on the heap? – Keith Mar 17 '15 at 15:03
@Keith The `params` will result in a heap allocation for the array. – juharr Apr 13 '16 at 13:26
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. – Mark Jeronimus Aug 01 '16 at 08:46
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. – Drew Noakes May 30 '23 at 03:01

C# implementation of FNV Hash

1 Answers1