是否存在一种字符串哈希算法，可以忽略字符串中字符的顺序？

Question

是否存在一种字符串哈希算法，可以忽略字符串中字符的顺序？例如，“helloworld”和“worldhello”可以映射到同一个桶中。

- JoJo

---

是的。不过你需要它做什么呢？将字符串转换为字符集或多重集合并进行操作可能更好。 - user2357112

你能给我更多关于如何实现它的细节吗？@user2357112 - JoJo

在Python中，使用set("helloword")或import collections; collections.Counter("helloworld")。不过我不知道你使用的是什么编程语言。 - user2357112

对字符串内容进行排序并对排序后的值进行哈希处理。这样，您可以对两个示例都哈希处理 dehlloorw，从而得到相同的哈希值。 - Jonathan Leffler

Answer 1

有多种不同的方法可以采用。

• 您可以将字符的值相加。(a + b + c等于a + c + b)。不幸的是，这是最不理想的方法，因为像"ac"和"bb"这样的字符串将生成相同的哈希值。

• 为了减少哈希码冲突的可能性，您可以将值进行异或运算。(a ^ b ^ c等于a ^ c ^ b)。不幸的是，这不会给出非常广泛的随机位分布，因此仍会给不同字符串之间产生高碰撞的机会。

• 为了进一步减少哈希码冲突的可能性，您可以将字符的值相乘。(a * b * c等于a * c * b)。

• 如果这还不够好，那么您可以在应用默认字符串哈希函数之前对字符串中的所有字符进行排序，无论您使用的是哪种语言。(因此，"helloworld"和"wordhello"都将变成"dehlloorw"，然后进行哈希，从而生成相同的哈希码。)这种方法的唯一缺点是它比其他方法更耗费计算资源。

- Mike Nakis

Answer 2

尽管将字符相乘或相加的其他建议可能起作用，但请注意这样的哈希函数根本不安全。原因是它会引入大量冲突，而哈希函数的主要属性之一就是冲突的概率很低。

例如，a+b+c与c+b+a相同。然而，它也与a+a+d相同（因为ascii字符的总和相同）。将数字相乘或异或也适用于相同的事情。

总之，如果想实现一个忽略顺序的哈希函数，可以这样做，但会引入大量冲突，这可能会使您的程序出现故障并且不安全。

- Preslav Mihaylov