高效计算容器哈希码
Efficiently calculating containers hash codes
我所知道的用于计算容器哈希码的算法通过递归组合其中所有元素的哈希值来工作。哈希的组合方式与我的问题无关。但是因为算法是递归的，所以计算会变得非常昂贵。 O(n)，其中 n 是可到达元素的总数。
我的问题是是否有更有效的方法来做到这一点？例如，如果您有一个包含 100k 个元素的数组，您可以通过组合仅包含的 100 个元素的哈希值来计算哈希值。这将使计算速度提高 1000 倍，同时仍然是一个很好的哈希函数，不是吗？
您选择的 100 个元素可以是第 100 个或每第 1000 个（在上例中）或使用其他确定性公式选择。
所以为了回答我的问题，你能或者告诉我为什么我的想法行不通吗或者告诉我我的想法在哪里已经被调查过了。是否有任何编程语言像我提议的那样实现了 "sub O(n) sequence hashing"？
一般来说，设计一个合适的哈希函数需要在计算时间和质量之间进行权衡，对于非常大的对象尤其如此。
仅散列大对象的固定大小子集是一种有效策略（例如，Lua 使用此策略散列大字符串），但如果散列对象具有几乎没有差异，并且碰巧差异不在散列子集中。这打开了拒绝服务攻击（或意外触发相同问题的输入）的可能性，因此如果您正在散列不受控制的输入，通常不是一个好主意。 （如果您将散列用作加密练习的一部分，那么省略部分对象会使伪造变得微不足道，因此在这种情况下，这是一个非常糟糕的主意。）
假设您将散列用作数据库索引策略的一部分（即散列 table），请记住最后您需要将查找的值与每个潜在值进行比较在 table 中匹配；这些比较必然是 O(n)（除非您认为几乎所有查找都会失败）。每个误报都需要进行额外的比较，因此质量与计算时间的权衡可能会被证明是一种错误的经济。
但是，最终，没有确定的答案；您将必须根据您拥有的精确用例来决定，包括考虑您使用哈希的目的、数据的分布是什么（或可能是）等等。
我所知道的用于计算容器哈希码的算法通过递归组合其中所有元素的哈希值来工作。哈希的组合方式与我的问题无关。但是因为算法是递归的，所以计算会变得非常昂贵。 O(n)，其中 n 是可到达元素的总数。
我的问题是是否有更有效的方法来做到这一点？例如，如果您有一个包含 100k 个元素的数组，您可以通过组合仅包含的 100 个元素的哈希值来计算哈希值。这将使计算速度提高 1000 倍，同时仍然是一个很好的哈希函数，不是吗？
您选择的 100 个元素可以是第 100 个或每第 1000 个（在上例中）或使用其他确定性公式选择。
所以为了回答我的问题，你能或者告诉我为什么我的想法行不通吗或者告诉我我的想法在哪里已经被调查过了。是否有任何编程语言像我提议的那样实现了 "sub O(n) sequence hashing"？
一般来说，设计一个合适的哈希函数需要在计算时间和质量之间进行权衡，对于非常大的对象尤其如此。
仅散列大对象的固定大小子集是一种有效策略（例如，Lua 使用此策略散列大字符串），但如果散列对象具有几乎没有差异，并且碰巧差异不在散列子集中。这打开了拒绝服务攻击（或意外触发相同问题的输入）的可能性，因此如果您正在散列不受控制的输入，通常不是一个好主意。 （如果您将散列用作加密练习的一部分，那么省略部分对象会使伪造变得微不足道，因此在这种情况下，这是一个非常糟糕的主意。）
假设您将散列用作数据库索引策略的一部分（即散列 table），请记住最后您需要将查找的值与每个潜在值进行比较在 table 中匹配；这些比较必然是 O(n)（除非您认为几乎所有查找都会失败）。每个误报都需要进行额外的比较，因此质量与计算时间的权衡可能会被证明是一种错误的经济。
但是，最终，没有确定的答案；您将必须根据您拥有的精确用例来决定，包括考虑您使用哈希的目的、数据的分布是什么（或可能是）等等。