将从字符串派生的唯一数字转换为良好的哈希代码

Question

我有一个应用程序，需要非常快速地比较许多小字符串。幸运的是，我可以保证以下所有字符串：

• 每个字符串中只有前6个字符被认为是重要的；任何剩余字符的差异都将被忽略
• 比较不区分大小写
• 字符串中只允许（英文）字母字符“-”和“'”。

我突然想到，因此可以将每个字符串转换为一个可以直接与其他字符串生成的其他int进行比较的int，从而将潜在成本高昂的字符串比较转换为单周期整数比较。

然而，我还需要将这些字符串用作哈希表中的键（特别是Java的HashMap和HashSet类），我想知道我生成的数字是否可以用作好的哈希代码，或者是否可以轻松地转换为它们，或者是否还应该使用更传统的字符串哈希算法为我的对象生成哈希代码。我可以自己做一个性能测试，但我突然想到，这个确切的问题很可能是以前有人评估过的；我只是在努力寻找关于它的好信息。

我的唯一编号生成代码如下：

private int stringMatcherCode (String word)
{
    int total = 0;
    for (int i = 0; i < word.length() && i < 6; i ++)
    {
        char ch = word.charAt (i);
        if (ch == '-') ch = (char)28;  // does not contain the same last 5 bits as any letter
        if (ch == '\'') ch = (char)29; // nor this
        total = (total << 5) | (ch & 0x1F);
    }
    return total;
}

Answer 1

当我提出这个问题时，我所没有的关键洞察是Java的HashMap实现使用了两个大小表的功能（我假设它是按照我多年前所学的方式工作的，在这种方式中，表的大小保持为素数）。在我的实现中，只有前面的字符在选择任何给定字符串映射到的bucket时才有意义。因此，质数是乘法器的更好选择——然而，31对我来说并不好，因为我可以像使用32一样轻松地保证唯一性。然而，33确实起作用，因为33^6仍然

private int stringMatcherCode (String word)
{
    int total = 0;
    for (int i = 0; i < word.length() && i < 6; i ++)
    {
        char ch = word.charAt (i);
        if (ch == '-') ch = (char)28;  // does not contain the same last 5 bits as any letter
        if (ch == '\'') ch = (char)29; // nor this
        total = (total * 33) + (ch & 0x1F);
    }
    return total;
}