绳子的有效重新散列

Question

给定一个绳子，假设我们需要知道它的哈希值（通过一些哈希函数传递所有叶子的连接）。

现在，当一个绳叶发生变化时，再次重新计算整条绳子的哈希值的有效方法是什么？即类似 O(log n) 而不是 O(n) 的东西。

一种方法是使用Merkle 树。但是，这会导致诸如...

• 空的非叶节点，或具有零长度子串的叶节点，即使对有效绳索内容没有影响，也会影响散列；
• 将子树右侧的节点移动到该子树右侧兄弟节点的左侧会影响最终的哈希值，但不会影响有效的绳索内容。

有没有更好的算法呢？散列函数不需要加密安全，只要足够好以避免可能的冲突。

Answer 1

正如绳索的任何节点存储左子树（如果它是叶子，则存储其自身）的大小一样，任何节点都可以另外存储与左子树（或如果它是叶子，则其自身）对应的字符串的多项式哈希。

当重新计算节点的权重时，也会重新计算该节点的哈希值，具有相同的渐近复杂度。

例如，假设节点及其中的值是：

    left     right    string     weight
1:                     abcd         4
2:    1        4                    4
3:                     ef           2
4:    3        5                    2
5:                     ghi          3

具有一些固定常数 p 和 q 的多项式哈希为：

h (s[0] s[1] ... s[n-1]) = (s[0] * p^(n-1) + s[1] * p^(n-2) + .. .+ s[n-1] * p^0) mod q。

因此，我们存储了以下哈希值，全部以 q 为模：

         hash
1:  a*p^3 + b*p^2 + c*p^1 + d*p^0
2:  a*p^3 + b*p^2 + c*p^1 + d*p^0
3:  e*p^1 + f*p^0
4:  e*p^1 + f*p^0
5:  g*p^2 + h*p^1 + i*p^0

关于计算模 q 的注释。此处和下文中，所有加法和乘法均以 q 为模进行。换句话说，我们在以 q 为模的整数环中进行运算。我们利用这样一个事实

(a ? b) mod q = ((a mod q) ? (b mod q)) mod q

为了 ？运算有加法、减法和乘法。因此，每次我们执行其中一项操作时，我们都会立即附加 amod q以保持数字较小。例如，如果 p 和 q 小于 2 ³⁰ = 1,073,741,824，则可以在 32 位整数类型中进行加法和减法，并且可以在中间 64 位整数类型中进行乘法。每次相乘后，我们立即对结果取模 q，使其再次适合 32 位整数。

现在，我们如何获取根的哈希值 - 例如，使其成为某个节点的左子节点，或者只是获取整个字符串的哈希值？

我们从根向右，我们必须添加权重并合并哈希值。事实证明我们可以这样做（记住一切都是以 q 为模）：

({ a*p^3 + b*p^2 + c*p^1 + d*p^0} * p^2 + { e*p^1 + f*p^0}) * p^3 + { g*p^2 + h*p^1 +i *p^0}

大括号中的值是存储在 out 节点中的值。我们向右递归。起床时，我们记住到目前为止收集到的权重，将左侧散列乘以 p 的权重次方（这就是 p^3 和 p^(3+2=5) 的来源），然后添加累积的值右侧哈希。

结果值等于整个字符串的哈希值：

a*p^8 + b*p^7 + c*p^6 + d*p^5 + e*p^4 + f*p^3 + g*p^2 + h*p^1 + i*p^0

这里有一些注意事项。

1. 我们必须预先计算（也许是懒惰的）p 模 q 的幂，以便能够快速乘以它们。

2. 如果我们将整个子树的哈希值（而不仅仅是左子树的哈希值）存储在节点中，整个结构可能会变得更加清晰。然而，这样，我们可能会失去绳索结构所具有的 O(1) 连接可能性，使其降至通常的 O(log n)，因此我们可能只使用常规的陷阱而不是绳索。即使没有，将整个子树的哈希值缓存在一个节点中也绝对是可能的。

3. 如果我们反转哈希多项式中的幂顺序，使其成为
   h (s[0] s[1] ... s[n-1]) = (s[0] * p^0 + s[1] * p^1 + ... + s[n-1] * p^(n-1)) mod q，
   数学类似，但是可以迭代而不是递归地从节点的所有右后代收集哈希。