如何创建与任何字符串排列匹配的唯一哈希

Question

给定一个字符串，abcd我如何创建一个独特的哈希方法来哈希这 4 个字符以匹配bcad或字母的任何其他排列abcd？

目前我有这个代码

long hashString(string a) {
    long hashed = 0;
    for(int i = 0; i < a.length(); i++) { 
        hashed += a[i] * 7; // Timed by a prime to make the hash more unique?
    } 
    return hashed;
}

现在这将不起作用，因为ad将与bc.

我知道你可以通过将字母的位置乘以字母本身来使其更加独特hashed += a[i] * i，但随后字符串将不会散列到其排列。

是否可以创建一个哈希来实现这一目标？

编辑

有些人建议在散列字符串之前对它们进行排序。这是一个有效的答案，但排序需要 O(nlog) 时间，我正在寻找一个在 O(n) 时间内运行的哈希函数。

我希望在 O(1) 内存中执行此操作。

Answer 1

创建一个包含 26 个整数的数组，对应于字母a-z。初始化为0，从头到尾扫描字符串，将当前字母对应的数组元素递增。请注意，到目前为止，该算法具有O(n)时间复杂度和O(1)空间复杂度（因为数组大小是常量）。

最后，使用您最喜欢的哈希函数对数组的内容进行哈希处理。