复杂度为 O(N) 的字符串的哈希函数

Question

例如，我们有一个字符串：“abc”。是否可以创建一个哈希函数（复杂度为 O(N)，其中 N 是字符串长度），它将执行以下操作：对于字符串“abc”的所有排列，它将返回相同的结果。

例如：

hash("abc") returns SC0wA //just an example value, not a real hash key
hash("bac") returns SC0wA
...
hash("cba") returns SC0wA

但对于“bba”，它将是：

hash("bba") return GD1z
hash("bab") return GD1z

更新：

哈希函数不应该对整个字母表有任何冲突

Answer 1

好吧，你可以在 C# 中这样做：

string text = "abc";
int hash = 0;

foreach(char c in text)
{
  int value = (int)c;
  hash += value;
}

哈希值的分布不会很好，但它可以完成工作。

更新：既然您提到字母表只是由 组成A-Z，a-z那么另一种选择是将它们在字母表中的位置映射到 a 中的位long，其中大写字符占据前 26 位，小写字符占据接下来的 26 位位：

long MakeHash(string text)
{
    long hash = 0;
    long numberOfCharacters = 0;

    foreach(var c in text)
    {
        int offset = 0;

        if(c >= 'A' && c <='Z')
        {
            offset = c - 'A';
        }
        else
        {
            offset = (c - 'a') + 26;
        }

        hash |= (1L << offset);

        numberOfCharacters++;
    }

    hash |= (numberOfCharacters << 52);

    return hash;
}

请注意最后如何将字符数与第 52 位及以后的位进行“或”运算。如果没有这个字符串，像aa和aaa会映射到相同的值，因为它们都只是设置了位a。将长度合并到值中，您会得到不同的值。