如何计算字符串列表的良好哈希码？

Question

背景：

• 我有一个简短的字符串列表。
• 字符串的数量并不总是相同，但几乎总是“少数”的数量级。
• 我们的数据库将这些字符串存储在第二个规范化表中。
• 这些字符串一旦写入，就永远改变。到数据库。

我们希望能够在查询中快速匹配这些字符串，而不会因为进行大量连接而影响性能。

因此，我正在考虑将所有这些字符串的哈希码存储在主表中并将其包含在我们的索引中，因此只有当哈希码匹配时数据库才会处理连接。

那么如何获得一个好的哈希码呢？我可以：

• 将所有字符串的哈希码一起异
• 或 异或将每个字符串后的结果相乘（例如乘以 31）
• 将所有字符串放在一起，然后获取哈希码
• 其他方式

那么人们怎么想？

---

最后，我只是连接字符串并计算连接的哈希码，因为它很简单并且工作得很好。

（如果您关心的话，我们正在使用 .NET 和 SqlServer）

---

错误！错误！

引用 Eric Lippert 的 GetHashCode 指南和规则

文档 System.String.GetHashCode 注释 特别是两个相同的 字符串可以有不同的哈希码 在不同版本的 CLR 中，以及 事实上他们确实如此。不存储字符串 数据库中的哈希值并期望它们 永远一样，因为他们 不会的。

因此 String.GetHashcode() 不应该用于此目的。

Answer 1

标准的java实践，就是简单的写

final int prime = 31;
int result = 1;
for( String s : strings )
{
    result = result * prime + s.hashCode();
}
// result is the hashcode.

Answer 2

我认为没有理由不连接字符串并计算连接的哈希码。

打个比方，假设我想计算一个内存块的 MD5 校验和，我不会将该块分割成更小的块并为它们计算单独的 MD5 校验和，然后用一些临时方法将它们组合起来。

Answer 3

您的第一个选项唯一的不便是 (String1, String2) 生成与 (String2, String1) 相同的哈希码。如果这不是问题（例如，因为您有修复订单），那就没问题。

“将所有字符串放在一起，然后获取哈希码”对我来说似乎更自然、更安全。

更新：正如评论所指出的，这有一个缺点，即列表 ("x", "yz") 和 ("xy","z") 会给出相同的哈希值。为了避免这种情况，您可以使用不能出现在字符串内部的字符串分隔符来连接字符串。

如果字符串很大，您可能更愿意对每个字符串进行散列，对散列码进行分类并重新散列结果。更多的CPU，更少的内存。

Answer 4

我脑海中浮现的另一种方式是，根据索引使用旋转散列进行链式异或：

int shift = 0;
int result = 1;
for(String s : strings)
{
    result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1);
    shift = (shift+1)%32;
}

编辑：阅读有效java中给出的解释，我认为杰夫的代码会更有效。

Answer 5

基于 SQL 的解决方案可以基于 checksum 和 checksum_agg 函数。如果我没理解错的话，你会得到类似的结果：

MyTable
  MyTableId
  HashCode

MyChildTable
  MyTableId  (foreign key into MyTable)
  String

给定项目 (MyTableId) 的各种字符串存储在 MyChildTable 中。要计算和存储反映这些（永远不会更改）字符串的校验和，应该像这样工作：

UPDATE MyTable
 set HashCode = checksum_agg(checksum(string))
 from MyTable mt
  inner join MyChildTable ct
   on ct.MyTableId = mt.MyTableId
 where mt.MyTableId = @OnlyForThisOne

我相信这是与顺序无关的，因此字符串“The Quick Brown”将产生与“Brown The Quick”相同的校验和”。

Answer 6

我希望这是不必要的，但是由于您没有提到任何听起来像是您只是使用哈希码进行第一次检查，然后再验证字符串实际上是否相等的内容，所以我觉得有必要警告您：

哈希码相等！=值相等

会有很多组字符串产生相同的哈希码，但并不总是相等。

Answer 7

所以我明白，您实际上有一些需要通过哈希码来识别的字符串集，并且您需要在其中识别的那组字符串永远不会改变？

如果是这种情况，这并不特别重要，只要您使用的方案为不同的字符串/字符串组合提供唯一的数字即可。我首先连接字符串并计算 String.hashCode() 并查看最终是否得到唯一的数字。如果不这样做，那么您可以尝试：

• 不要连接字符串，而是连接组成字符串的哈希码，并尝试不同的乘数（例如，如果您想识别两个字符串序列的组合，请尝试 HC1 + 17 * HC2，如果如果没有给出唯一的数字，请尝试 HC1 + 31 * HC2，然后尝试 19，然后尝试 37 等等——本质上任何小的奇数都可以。
• 如果您没有以这种方式获得唯一的数字 - 或者如果您需要应对扩展的可能性集 - 那么请考虑更强的哈希码。 64 位哈希码是易于比较和哈希唯一性之间的良好折衷方案。

64 位哈希码的可能方案如下：

• 使用相当强大的方案生成 256 个 64 位随机数的数组（您可以使用 SecureRandom，尽管 XORShift 方案可以正常工作）
• 选择“m”，另一个“随机”64 位奇数，其位或多或少一半设置
• 生成哈希码，遍历每个字节值 b，组成字符串，并从随机数数组中取出第 b 个数字；然后将其与当前哈希值乘以“m”进行异或或相加。

因此，基于数值配方中建议的值的实现将是：

  private static final long[] byteTable;
  private static final long HSTART = 0xBB40E64DA205B064L;
  private static final long HMULT = 7664345821815920749L;

  static {
    byteTable = new long[256];
    long h = 0x544B2FBACAAF1684L;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 31; j++) {
        h = (h >>> 7) ^ h;
        h = (h << 11) ^ h;
        h = (h >>> 10) ^ h;
      }
      byteTable[i] = h;
    }
  }

上面正在初始化我们的随机数数组。我们使用 XORShift 生成器，但我们实际上可以使用任何质量相当好的随机数生成器（使用特定种子创建 SecureRandom()，然后调用 nextLong() 就可以了）。然后，生成哈希码：

  public static long hashCode(String cs) {
    if (cs == null) return 1L;
    long h = HSTART;
    final long hmult = HMULT;
    final long[] ht = byteTable;
    for (int i = cs.length()-1; i >= 0; i--) {
      char ch = cs.charAt(i);
      h = (h * hmult) ^ ht[ch & 0xff];
      h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
    }
    return h;
  }

要考虑的指南是，给定 n 位哈希码，平均而言，您需要生成 2^(n/2) 个字符串的哈希值，然后才能获得碰撞。或者换句话说，对于 64 位哈希，您预计在大约 40 亿个字符串后会发生冲突（因此，如果您要处理多达几百万个字符串，则发生冲突的可能性可以忽略不计） ）。

另一种选择是 MD5，它是一个非常强大的哈希值（实际上安全），但它是 128 位哈希值，因此您有一个必须处理 128 位值的轻微缺点。我想说 MD5 对于这些目的来说有点过分了——正如我所说，使用 64 位散列，您可以相当安全地处理几百万个字符串。

（抱歉，我应该澄清一下——MD5 被设计为一种安全散列，只是后来发现它不安全。“安全”散列是指给定特定散列时，故意构造会导致以下情况的输入是不可行的：在某些情况下——但不像我所理解的——你可能需要这个属性，另一方面，如果你正在处理用户输入的数据——即a。恶意用户可能会故意尝试混淆您的系统。您可能还会对我过去写的以下内容感兴趣：

• 哈希码指南
• Java 中的安全哈希码< /a> （包括一些性能测量）

Answer 8

使用 GetHashCode() 并不适合组合多个值。问题是对于字符串来说，哈希码只是一个校验和。对于相似的值来说，这留下了很少的熵。例如，为（“abc”，“bbc”）添加哈希码将与（“abd”，“abc”）相同，从而导致冲突。

如果您需要绝对确定，您可以使用真正的哈希算法，例如 SHA1、MD5 等。唯一的问题是它们是块函数，很难快速比较哈希值是否相等。相反，请尝试 CRC 或 FNV1 哈希。 FNV1 32 位非常简单：

public static class Fnv1 {
    public const uint OffsetBasis32 = 2166136261;
    public const uint FnvPrime32 = 16777619;

    public static int ComputeHash32(byte[] buffer) {
        uint hash = OffsetBasis32;

        foreach (byte b in buffer) {
            hash *= FnvPrime32;
            hash ^= b;
        }

        return (int)hash;
    }
}

Answer 9

您可以使用以下方法来聚合哈希码：
http ://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash(java.lang.Object...)

Answer 10

如果您碰巧使用 Java，则可以创建一个字符串数组（或将集合转换为数组），然后使用 Arrays.hashCode()，如文档 此处。

Answer 11

让我们解决您的根本问题。

不要使用哈希码。只需为每个字符串添加一个整数主键