algorithm - 高效计算容器哈希码

Question

我所知道的用于计算容器哈希码的算法通过递归地组合容器中所有元素的哈希值来工作。哈希的组合方式与我的问题无关。但是因为算法是递归的，所以计算会变得非常昂贵。 O(n)，其中 n 是可达元素的总数。

我的问题是是否有更有效的方法来做到这一点？例如，如果您有一个包含 100k 个元素的数组，您可以通过组合仅包含的 100 个元素的哈希值来计算哈希值。这将使计算速度提高 1000 倍，同时仍然是一个很好的哈希函数，不是吗？

您选择的 100 个元素可以是前 100 个或每第 1000 个(在上例中)或使用其他确定性公式选择。

所以为了回答我的问题，你能告诉我为什么我的想法行不通吗或者告诉我我的想法在哪里已经被研究过了。是否有任何编程语言像我提议的那样实现了“子 O(n) 序列哈希”？

Answer 1

一般来说，设计合适的哈希函数需要在计算时间和质量之间进行权衡，对于非常大的对象尤其如此。

只散列一个大对象的固定大小的子集是一个有效的策略(例如，Lua 使用这种策略来散列大字符串)，但如果散列对象几乎没有差异，它显然会导致问题，并且碰巧差异不在散列子集中。这打开了拒绝服务攻击(或意外触发相同问题的输入)的可能性，因此如果您正在散列不受控制的输入，通常不是一个好主意。 (如果您将散列用作加密练习的一部分，那么省略部分对象会使伪造变得微不足道，因此在这种情况下，这是一个非常糟糕的主意。)

假设您将哈希用作数据库索引策略(即哈希表)的一部分，请记住，最后您需要将要查找的值与表中的每个潜在匹配项进行比较；这些比较必然是 O(n)(除非您认为几乎所有查找都会失败)。每个误报都需要进行额外的比较，因此质量与计算时间的权衡可能会被证明是一种错误的经济。

但是，最终，没有确定的答案；您将必须根据您拥有的确切用例来做出决定，包括考虑您使用哈希的目的、数据的分布是什么(或可能是什么)等等。