绳索的高效重新散列
Efficient re-hashing of a rope
给定一个 rope，假设我们需要知道它的哈希值（通过一些哈希函数传递所有叶子的串联）。
现在，当一根绳子的叶子发生变化时，有什么有效的方法可以再次重新计算整根绳子的哈希值？ IE。类似于 O(log n) 而不是 O(n)。
一种方法是使用 Merkle tree。但是，这会导致诸如...
- 空的非叶节点或具有零长度子串的叶节点会影响哈希，即使它们对有效绳索内容没有影响；
- 将节点从子树的右侧移动到该子树右侧兄弟的左侧会影响最终哈希，但不会影响有效的绳索内容。
有更好的算法吗？散列函数不需要加密安全，只要足够好就可以避免可能发生的冲突。
就像绳索的任何节点都存储左子树的大小（如果是叶子，则为自身），任何节点都可以额外存储左子树对应的字符串的多项式哈希（如果为叶子，则为自身）是一片叶子）。
当为一个节点重新计算权重时，也会为该节点重新计算散列，具有相同的渐近复杂度。
例如，让节点和其中的值是：
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.
因此，我们存储了以下哈希值，所有 modulo 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
关于计算的说明 modulo q。
在这里和下面，所有加法和乘法都进行了 modulo q。
也就是说，我们操作在ring of integersmodulo q。
我们使用
(a ? b) mod q = ((a mod q) ? (b mod q)) mod q
为了？运算是加法、减法和乘法。
因此，每次我们执行这些操作之一时，我们都会立即附加一个 mod q 以保持数字较小。
比如p和q小于230 = 1,073,741,824，加减可以用32位的整型，乘法用中间的64位就可以了整数类型。
每次乘法后，我们立即取结果modulo q，使其重新适合32位整数。
现在，我们如何获取根的哈希值 - 例如，使其成为某个节点的左子节点，或者只是获取整个字符串的哈希值？
我们从根向右走，还要加权重，合并哈希。事实证明我们可以这样做（记住一切都是 modulo 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节点中存储的值。
我们向右递归。
起床时，我们记住到目前为止收集到的权重，将 left-side 散列乘以 p 的权重次方（这就是 p^3 和 p^(3+2=5) 的来源），并添加累积的 right-side 哈希值。
结果值等于整个字符串的哈希值：
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
这里有几点说明。
我们必须预先计算 p modulo q 的幂，以便能够快速乘以它们。
如果我们将整个子树的散列存储在一个节点中，而不仅仅是左子树的散列，整个结构可能会变得更加清晰。然而，这样一来，我们可能会失去绳索结构具有的 O(1) 级联可能性，使其降为通常的 O(log n)，因此我们可能只是使用了常规的 treap一根绳子。就算不是，把整个子树的hash值缓存在一个节点中也绝对是可以的。
如果我们颠倒散列多项式中的幂次序，则
h (s[0] s[1] ... s[n-1]) = (s[0] * p^0 + s[1] * p^1 + ... + s[n-1] * p^(n-1)) mod q,
数学是相似的，但是可以迭代而不是递归地从节点的所有右后代收集哈希。
给定一个 rope，假设我们需要知道它的哈希值（通过一些哈希函数传递所有叶子的串联）。
现在，当一根绳子的叶子发生变化时，有什么有效的方法可以再次重新计算整根绳子的哈希值？ IE。类似于 O(log n) 而不是 O(n)。
一种方法是使用 Merkle tree。但是，这会导致诸如...
- 空的非叶节点或具有零长度子串的叶节点会影响哈希，即使它们对有效绳索内容没有影响；
- 将节点从子树的右侧移动到该子树右侧兄弟的左侧会影响最终哈希，但不会影响有效的绳索内容。
有更好的算法吗？散列函数不需要加密安全，只要足够好就可以避免可能发生的冲突。
就像绳索的任何节点都存储左子树的大小（如果是叶子，则为自身），任何节点都可以额外存储左子树对应的字符串的多项式哈希（如果为叶子，则为自身）是一片叶子）。
当为一个节点重新计算权重时，也会为该节点重新计算散列，具有相同的渐近复杂度。
例如，让节点和其中的值是：
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.
因此，我们存储了以下哈希值，所有 modulo 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
关于计算的说明 modulo q。 在这里和下面，所有加法和乘法都进行了 modulo q。 也就是说，我们操作在ring of integersmodulo q。 我们使用
(a ? b) mod q = ((a mod q) ? (b mod q)) mod q
为了？运算是加法、减法和乘法。
因此，每次我们执行这些操作之一时，我们都会立即附加一个 mod q 以保持数字较小。
比如p和q小于230 = 1,073,741,824，加减可以用32位的整型，乘法用中间的64位就可以了整数类型。
每次乘法后，我们立即取结果modulo q，使其重新适合32位整数。
现在，我们如何获取根的哈希值 - 例如，使其成为某个节点的左子节点，或者只是获取整个字符串的哈希值？
我们从根向右走，还要加权重，合并哈希。事实证明我们可以这样做（记住一切都是 modulo 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节点中存储的值。 我们向右递归。 起床时，我们记住到目前为止收集到的权重，将 left-side 散列乘以 p 的权重次方（这就是 p^3 和 p^(3+2=5) 的来源），并添加累积的 right-side 哈希值。
结果值等于整个字符串的哈希值：
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
这里有几点说明。
我们必须预先计算 p modulo q 的幂，以便能够快速乘以它们。
如果我们将整个子树的散列存储在一个节点中，而不仅仅是左子树的散列，整个结构可能会变得更加清晰。然而，这样一来，我们可能会失去绳索结构具有的 O(1) 级联可能性，使其降为通常的 O(log n)，因此我们可能只是使用了常规的 treap一根绳子。就算不是，把整个子树的hash值缓存在一个节点中也绝对是可以的。
如果我们颠倒散列多项式中的幂次序，则
h (s[0] s[1] ... s[n-1]) = (s[0] * p^0 + s[1] * p^1 + ... + s[n-1] * p^(n-1)) mod q,
数学是相似的，但是可以迭代而不是递归地从节点的所有右后代收集哈希。