algorithm - 如何创建一个唯一的散列来匹配任何字符串排列

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) 空间复杂度(因为数组大小是常数)。

最后，使用您最喜欢的散列函数散列数组的内容。