明明有更好的hash方法

有位朋友对我吐槽前几天我列举的在源生成器的生成db映射实体的优化点提前生成部分 hashcode 进行比较

所示代码

public static void GenerateReadTokens(this IDataReader reader, Span<int> s)
{
    for (int i = 0; i < reader.FieldCount; i++)
    {
        var name = reader.GetName(i);
        var type = reader.GetFieldType(i);
        switch (EntitiesGenerator.SlowNonRandomizedHash(name))
        {
            
            case 742476188U:
                s[i] = type == typeof(int) ? 1 : 2; 
                break;

            case 2369371622U:
                s[i] = type == typeof(string) ? 3 : 4; 
                break;

            case 1352703673U:
                s[i] = type == typeof(float) ? 5 : 6; 
                break;

            default:
                break;
        }
    }
}

这里为什么不用 string.GetHashCode, 而要用 SlowNonRandomizedHash(name)，有更好的方法不用，真是傻

当时俺也只能囧着脸给ta解释 string.GetHashCode真的没办法用，

可惜口头几句解释再多，一时也无法摆脱ta鄙视的目光

只有在此多写几句“狡辩”

“狡辩”

首先其实NormalizedHash 性能很强的，其实现如下

public static uint SlowNonRandomizedHash(this string? value)
{
    uint hash = 0;
    if (!string.IsNullOrEmpty(value))
    {
        hash = 2166136261u;
        foreach (char c in value!)
        {
            hash = (char.ToLowerInvariant(c) ^ hash) * 16777619;
        }
    }
    return hash;
}

但是不管性能强不强，也不是只能用这个方法的原因

其实真实原因很多人都知道，都是大家的默认常识了：net code string.GetHashCode是随机的，多次运行程序，同一个字符串可能会在每次运行都有不同的哈希值

比如 18年的文章 Why is string.GetHashCode() different each time I run my program in .NET Core?

这里简单复述一下原文内容

以这个非常简单的程序为例，它连续两次调用一个字符串GetHashCode()

using System;

static class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Hello World!".GetHashCode());
        Console.WriteLine("Hello World!".GetHashCode());
    }
}

如果在 .NET Framework 上运行此程序，则每次运行该程序时，都会获得相同的值：

> dotnet run -c Release -f net471
-1989043627
-1989043627

> dotnet run -c Release -f net471
-1989043627
-1989043627

> dotnet run -c Release -f net471
-1989043627
-1989043627

相反，如果为 .NET Core 编译同一程序，则在同一程序执行中每次调用都会获得相同的值，但对于不同的程序执行，将获得不同的值：GetHashCode()

> dotnet run -c Release -f netcoreapp2.1
-1105880285
-1105880285

> dotnet run -c Release -f netcoreapp2.1
1569543669
1569543669

> dotnet run -c Release -f netcoreapp2.1
-1477343390
-1477343390

努力查找之后，在微软官方文档给出过使用GetHashCode()方法的建议。其明确提示，不应将GetHashCode()方法产生的hash值当作为相同能持久化的值使用。

The hash code itself is not guaranteed to be stable. Hash codes for identical strings can differ across .NET implementations, across .NET versions, and across .NET platforms (such as 32-bit and 64-bit) for a single version of .NET. In some cases, they can even differ by application domain. This implies that two subsequent runs of the same program may return different hash codes.

为什么要用随机化的 hash？

Stephen Toub 在一个issue 中提到了这个问题的答案:

Q: Why .NET Core utilize randomized string hashing?
问：为什么 .NET Core 使用随机字符串哈希？
A: Security, prevention against DoS attacks, etc.
A：安全性、防止 DoS 攻击等。

原文很详细的解释有关安全的内容，这里就不作详细复述了

那么有没有更好的 hash 方法呢？

当然肯定是有的，string 类内部其实就有，

感兴趣的童鞋可以阅读源码 https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/String.Comparison.cs#L923

里面大小写敏感和不敏感都有实现，其代码比上面18年文章列举的方法还有更多性能优化

不过内部方法，我们没有办法可以直接使用

但是呢？我们有黑魔法可以直接使用

public static partial class StringHashing
{
    [UnsafeAccessor(UnsafeAccessorKind.Method, Name = "GetNonRandomizedHashCodeOrdinalIgnoreCase")]
    public static extern int Hash(this string c);
}

比较一下

我们都写到这里了，不比一下性能，大家肯定不服气

来一段简单的比较

[ShortRunJob, MemoryDiagnoser, Orderer(summaryOrderPolicy: SummaryOrderPolicy.FastestToSlowest), GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByCategory), CategoriesColumn]
public class StringHashingBenchmarks
{
    [Params(0, 1, 10, 100)]
    public int Count { get; set; }

    public string Str { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        var s = string.Join("", Enumerable.Repeat("_", Count));
        var b = Encoding.UTF8.GetBytes(s);
        Random.Shared.NextBytes(b);
        Str = Encoding.UTF8.GetString(b);
    }

    [Benchmark(Baseline = true)]
    public int GetHashCode()
    {
        return Str.GetHashCode();
    }

    [Benchmark]
    public uint SlowNonRandomizedHash()
    {
        return Str.SlowNonRandomizedHash();
    }

    [Benchmark]
    public int NonRandomizedHash()
    {
        return Str.Hash();
    }
}

结果


BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3880/23H2/2023Update/SunValley3)
13th Gen Intel Core i9-13900KF, 1 CPU, 32 logical and 24 physical cores
.NET SDK 9.0.100-preview.6.24328.19
  [Host]   : .NET 8.0.7 (8.0.724.31311), X64 RyuJIT AVX2
  ShortRun : .NET 8.0.7 (8.0.724.31311), X64 RyuJIT AVX2

Job=ShortRun  IterationCount=3  LaunchCount=1  
WarmupCount=3

Method	Count	Mean	Error	StdDev	Ratio	RatioSD	Allocated	Alloc Ratio
SlowNonRandomizedHash	0	0.3286 ns	0.0727 ns	0.0040 ns	0.69	0.01	-	NA
GetHashCode	0	0.4751 ns	0.1093 ns	0.0060 ns	1.00	0.00	-	NA
NonRandomizedHash	0	0.6614 ns	0.0339 ns	0.0019 ns	1.39	0.02	-	NA

GetHashCode	1	0.5686 ns	0.0881 ns	0.0048 ns	1.00	0.00	-	NA
NonRandomizedHash	1	0.6559 ns	0.0254 ns	0.0014 ns	1.15	0.01	-	NA
SlowNonRandomizedHash	1	7.3752 ns	0.2379 ns	0.0130 ns	12.97	0.11	-	NA

GetHashCode	10	3.1627 ns	0.2081 ns	0.0114 ns	1.00	0.00	-	NA
NonRandomizedHash	10	16.1921 ns	1.1773 ns	0.0645 ns	5.12	0.02	-	NA
SlowNonRandomizedHash	10	44.4825 ns	2.8742 ns	0.1575 ns	14.06	0.01	-	NA

GetHashCode	100	40.4233 ns	0.7217 ns	0.0396 ns	1.00	0.00	-	NA
NonRandomizedHash	100	110.2494 ns	13.1581 ns	0.7212 ns	2.73	0.02	-	NA
SlowNonRandomizedHash	100	362.0329 ns	11.0681 ns	0.6067 ns	8.96	0.02	-	NA