c++ - 好的哈希函数可以从数组中删除重复项

Question

任何人都可以建议好的 has 函数从数组中删除重复项以使用适度的内存消耗吗？请记住，我正在为此使用 HashMap 解决方案，但需要良好的哈希函数。否则内存消耗取决于数组的最大元素。

它是一个整数数组....

Answer 1

你的问题不够详细，我来补一下。

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

最重要的是整数的大小(多少位)，不同元素的个数(这样我们就知道边表会增长多少)和数组中的元素个数(估计需要多少操作它需要)。

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

cat list | sort -u

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

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

然而，这显然会对数组进行排序，因此可能并不理想。在这种情况下，您始终可以使用边 table 。

• 如果整数的范围很小(例如 [0, 65536) 中的所有整数)，则只需使用以整数作为索引的常规表。使用 bitset 你可以很容易地得到它们。
• 如果范围扩大，则更多取决于范围的稀疏程度。
  • 对于稀疏范围，哈希表确实是一个不错的方法
  • 然而，对于整个范围(例如，极少的重复项和大量元素)，哈希表将增长得非常快，并且可能变得太大，在这种情况下，也许比布隆过滤器(即概率方法)更有效。