良好的散列函数，以从阵列中删除重复项

Question

任何人都可以建议良好的函数从数组中删除重复项以便使用适度的内存消耗？记住我正在使用哈希映射解决方案，但希望有很好的哈希函数。否则，内存消耗取决于阵列的最大元素。

它的整数数组....

Answer 1

中有，因为它已经足够小，以做对比散列一个整数非常小的点。您可以对数组进行排序并删除相同的后续元素。如果你真的想对它们进行散列，比如前两个字节变成了一个短的，那就是你的散列。

Answer 2

你的问题缺乏细节，所以我只会做出来。

散列整数通常是无用的。整数是它自己的散列。

最重要的是整数的大小（多少位），不同元素的数量（以便我们知道边桌将增长多少）以及数组中元素的数量（估计多少将采取的行动）。

消除重复的最简单的解决方案通常是排序+统一。或在Unix的：

cat list | sort -u 

在C++中，这可以通过<algorithm>实现：

std::sort(vector.begin(), vector.end()); 
vector.erase(std::unique(vector.begin(), vector.end()), vector.end()); 

然而此阵列将明显排序，以便可能不是期望的。在这种情况下，你总是可以使用边桌。

• 如果整数的范围较小（比如都在[0, 65536)例如），然后只需用一个常规表与整数作为索引。使用bitset你可以很容易地得到它们。
• 如果范围增大，则事情更多取决于范围的稀疏程度。
  • 对于稀疏范围，确实是一个哈希表可以是一个很好的方法
  • 但是一个完整的范围（例如，很少重复和大量元素），那么哈希表将极大增加并可能变得太大，在这种情况下，可能比布卢姆过滤器（即概率方法）更好。

Answer 3

您可以使用MAD（乘加和除法）方法，这有助于消除一组整数密钥的重复模式。

h（k）= | ak + b | mod N，

其中N是素数，a和b是随机选择的非负整数，所以mod N！= 0。但是你仍然需要处理冲突。