Skip to content

Instantly share code, notes, and snippets.

@StephenCleary
Created October 6, 2019 14:15
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save StephenCleary/4f6568e5ab5bee7845943fdaef8426d2 to your computer and use it in GitHub Desktop.
Save StephenCleary/4f6568e5ab5bee7845943fdaef8426d2 to your computer and use it in GitHub Desktop.
FNV-1a hash in C#
/// <summary>
/// A hash combiner that is implemented with the Fowler/Noll/Vo algorithm (FNV-1a). This is a mutable struct for performance reasons.
/// </summary>
public struct FnvHash
{
/// <summary>
/// The starting point of the FNV hash.
/// </summary>
public const int Offset = unchecked((int)2166136261);
/// <summary>
/// The prime number used to compute the FNV hash.
/// </summary>
private const int Prime = 16777619;
/// <summary>
/// Gets the current result of the hash function.
/// </summary>
public int HashCode { get; private set; }
/// <summary>
/// Creates a new FNV hash initialized to <see cref="Offset"/>.
/// </summary>
public static FnvHash Create()
{
var result = new FnvHash();
result.HashCode = Offset;
return result;
}
/// <summary>
/// Adds the specified byte to the hash.
/// </summary>
/// <param name="data">The byte to hash.</param>
public void Combine(byte data)
{
unchecked
{
HashCode ^= data;
HashCode *= Prime;
}
}
/// <summary>
/// Adds the specified integer to this hash, in little-endian order.
/// </summary>
/// <param name="data">The integer to hash.</param>
public void Combine(int data)
{
Combine(unchecked((byte)data));
Combine(unchecked((byte)(data >> 8)));
Combine(unchecked((byte)(data >> 16)));
Combine(unchecked((byte)(data >> 24)));
}
}
@glen-84
Copy link

glen-84 commented Feb 22, 2024

Why signed and not unsigned integers?

@StephenCleary
Copy link
Author

I don't remember, but most likely because the .NET hash types use signed integers. Which is an ancient holdover from an attempt to make .NET a language-independent virtual machine bytecode system, which never really panned out.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment