PZY

在分布式缓存场景下，对于大量缓存（key 通常为字串）需要均匀分布多（假设为 N）台服务器节点上，较为主流的做法是取模算法：Hash（key）% N，即：对 key 进行 hash 运算后再进行 N 取模，也就是一致性 Hash 算法，因与本文主题无关，我再写文进行探讨。

然而在 .NET 中，String 本身的 GetHashCode 方法，相同的字符串值，两次运行 GetHashCode 得到的返回值却不一样。现节选部分官方文档说明:

If two string objects are equal, the GetHashCode method returns identical values. However, there is not a unique hash code value for each unique string value. Different strings can return the same hash code.

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.

As a result, hash codes should never be used outside of the application domain in which they were created, they should never be used as key fields in a collection, and they should never be persisted.

因一致性 Hash 要保证相同的字符串值，其哈希码（ hash code） 必须相同，所以 String 本身的 GetHashCode 方法，并不能满足缓存 key 的一致性 Hash 的要求。

在 Java 中，相同的字符串值的 hash code 是相同的，可以参考其算法说明，在 .NET 实现相同的方法。根据 Java 文档，String 对象的哈希码算法为：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

基于 int 运算，其中 s[i] 是字符串的第 i 个字符的 ASCII 值，n 是字符串的长度，^ 表示求幂。

为什么要用31作为乘数？既然是取比较大的素数，为什么不是 29、37 甚至 97 呢？

以下是 StackOverflow 上该问题的认可较高的答案：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

也就是说，选择 31 是因为它是一个奇素数，一方面可以产生更分散的散列，即不同字符串 hash 值一般不同，在选择系数的时候要选择尽量长的并且让乘法结果尽量不要溢出的系数。如果计算出来的 hash地址越大，所谓的「冲突」就越少，查找起来效率也会提高。但是也不能过大，在 Java 乘法中如果数字相乘过大会导致溢出的问题。

另一个方面是计算效率比较高，31 一个很好的特点是乘法可以用移位和减法代替以获得更好的性能：31 * i == (i << 5) - i，现代虚拟机均会进行这种优化。

该算法存在这样一种情况，某字符串及该字符串回文的 hashCode() 返回值相同，例如字符串 "gdejicbegh" 与字符串 "hgebcijedg" 的 hashCode() 返回值都是 -801038016。但这并不影响分布式缓存下的一致性 Hash。

根据上述 Java 字符串 hashCode() 算法解读，很容易得出 C# 版本字符串 hash code 求解方法，核心代码如下：

private int GetHashCode(string text)
{
    if (text.Length <= 0)
    {
        return 0;
    }

    Span<byte> bytes = Encoding.UTF8.GetBytes(text);

    int hashCode = 0;

    foreach (var b in bytes)
    {
        //hashCode = (hashCode << 5) - hashCode + b
        hashCode = 31 * hashCode + b;
    }

    return hashCode;
}

如果不需要与 Java 字符串 hashCode() 结果相一致，也可使用以下实现方法：

private int GetHash(string text)
{
   using (var md5 = MD5.Create())
   {
   	var hash = md5.ComputeHash(System.Text.Encoding.UTF8.GetBytes(key));
   	return BitConverter.ToInt32(hash, 0);
   }
}

（完）