FNV Hash 的 C# 实现

Question

我遇到过很多需要在 C# 中使用合适的哈希算法的情况，从覆盖

GetHashCode

到对数据执行快速比较/查找。

我发现 FNV 哈希是一种非常简单/良好/快速的哈希算法。然而，我从未见过 C# 实现的好例子。

FNV-1a哈希算法的核心如下：

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

所以，当我覆盖一个类的

GetHashCode

时，我最终会做类似的事情：

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

人们对此有何看法？

Answer 1

您可以将其添加到您的

FNVConstants

课程中

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

然后称呼它为

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

Answer 2

对于遇到此线程并在 C# 中寻找 FNV-1a 实现的任何其他人，FNV 算法要求对哈希值和输入的每个八位字节进行异或：

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() 返回一个 32 位整数。我相信严格实施 FNV-1a（忽略字节顺序的考虑）看起来更像是：

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;

我不清楚使用完整的 32 位整数而不是单独的八位字节对哈希分布有何影响。 这里有一个很好的算法概述，以及一些关于它的使用的有趣历史。

如果您正在寻求实现确定性哈希解决方案，则上面的代码将不起作用。 Object.GetHashCode() 在运行中不稳定，会产生不同的结果。您需要在不使用 HashCode 类的内置实现或 Object.GetHashCode() 的情况下实现 FNV 算法。