c++ - 如何增量更新哈希值？

Question

我正在寻找一个简单的增量哈希函数 (C++)，这样它就可以使用以下方式进行更新:

               hash = hash_function(hash, update_value)

例如，update_value 可以是一位。

例如，为了计算数组的散列，我会这样做:

              hash = 0
              foreach element a in array { hash = hash_function(hash, a) }

(最好是不会导致太多碰撞，但速度相对较快的东西。)

Answer 1

如果您要散列一个位数组:

你可以实现一个 Cyclic redundancy check. CRC 多项式将确定散列长度并(粗略地)控制冲突的可能性。许多示例软件 CRC 算法都经过优化，可以对比位更宽的事物进行操作，但核心的、未优化的算法一次只工作一点。算法大致是:

1. 从累加器中的一些恒定种子值开始
2. 将数组中的一点移到累加器中。
3. 有条件地，对多项式执行异或运算。不同的实现要么使用您刚移出的位，要么使用您刚移入的位作为条件。
4. 重复后续位(转到 2)。

您提出的方法会将当前累加器值作为第一个参数，并返回下一个累加器值。

多项式选择很重要。有一些多项式被认为不适合哈希。

如果数组包含更宽的内容(如整数或对象):

您可以只散列每个元素，然后将每个元素的散列与异或之类的东西组合在一起。如果单个对象的散列算法很好，那么数组的散列结果也应该相对不错。请注意，首先对单个对象进行哈希处理非常重要。