关于忽略字符排序的字符串散列函数的建议

我需要在C++中使用unordered_map<string, int>的散列函数。我需要根据内容对密钥进行散列处理，但不应取决于内容的顺序。关于忽略字符排序的字符串散列函数的建议

例如，在我的地图中，键是字符串，我需要“ac”，“ca”来生成相同的散列值，但“bb”应该生成不同的散列值。

我试着总结字符串的内容，但我意识到在这种情况下，“ac”和“bb”会生成相同的散列值。

还有类似的问题Does a string hash exist which can ignore the order of chars in this string，但那还没有被回答。

来源

2015-03-08 Anoop

在对它们进行散列操作之前对它们进行排序。这意味着你对'ac'和'ca'都加上'ac'，这样它们就可以根据需要哈希到相同的值，但'bb'（大概）会散列到不同的值。 – 2015-03-08 21:15:17

^他打算说“排序字符串中的字符”。 – 2015-03-08 21:20:20

是的。排序他们现在工作。但是如果有一个线性时间散列函数而没有任何额外的内存来完成这个任务，那将会很棒 – Anoop 2015-03-08 21:23:46

由于a * b * c等同于a * c * b，所以可以将字符相乘而不是相加。

这应该比在对每个字符串中的所有字符进行散列操作之前快很多。

来源

2015-03-08 21:21:48

我认为这在所有情况下都不起作用。例如，如果ascii值从0开始，那么cc => 9也是l => 9。虽然这可能并非如此，但我猜可能会发生碰撞。这将是很好，如果我能以某种方式避免碰撞。我这样说是因为我知道在我的要求中字符串长度限制在50左右。对不起，没有添加此信息的问题。 – Anoop 2015-03-08 21:26:29

@Anoop：任何散列函数都可能发生冲突;这是他们的观点。答案中提出的概念几乎可以肯定你使用原始的ASCII值（所以'a' => 97，'b' => 98，'c' => 99等），但你仍然可能遇到问题截然不同的字符串结束生产相同的产品。如果字符串的长度不合适，那么最终计算模数就会变成一些数字，可能是2的幂，例如2^32或2^64，但不会改变碰撞。 – 2015-03-08 21:34:52

您不能***避免***碰撞，因为您将数百位下载到32位或仅64位。根据定义，这将导致冲突。幸运的是，哈希函数不必保证没有碰撞，它只需要确保它们很少发生。字母的ASCII值从65开始为大写字母'A'，97为小写字母'a'，所以通过将这些数字相乘，您很可能不会碰撞到碰撞，除了您希望看到的特定类型的碰撞。（同一个字符不合要求。） – 2015-03-08 21:39:08

关于忽略字符排序的字符串散列函数的建议

回答

相关问题