c++ - 无序多集的散列/crc 算法

Question

假设我想创建一组无序的 unsigned int 无序多重集。为此，我需要创建一个哈希函数来计算无序多重集的哈希值。事实上，它也必须对 CRC 有好处。

一个明显的解决方案是将项目放入 vector 中，对它们进行排序并返回结果的哈希值。这似乎可行，但它很昂贵。

另一种方法是对值进行异或运算，但很明显，如果我有一个项目两次或没有，结果将是相同的——这并不好。

关于如何以更便宜的方式实现这一点的任何想法 - 我有一个应用程序可以为数千套和相对较大的套做这千套。

Answer 1

由于它是一个多重集，您希望相同多重集的哈希值相同，其表示可能具有以不同顺序呈现、添加或删除的相同元素。然后，您希望散列值是可交换的、易于更新的，并且随着元素的每次变化而变化。您还希望两个更改不会轻易取消它们对哈希的影响。

除最后一个条件外，满足所有条件的一个操作是加法。只需对元素求和即可。为了使总和有界，请对散列值的大小求模求和。 (例如，64 位散列的模 2⁶⁴。)要确保插入或删除零值会更改散列，请先为每个值加一。

总和的一个缺点是两个变化很容易抵消。例如。用 2 2 替换 1 3。为了解决这个问题，您可以使用相同的方法并对条目的多项式求和，仍然保留交换性。例如。您可以对 x²+x+1 求和，而不是对 x+1 求和。现在，设计具有相同总和的更改集更加困难。