1

我正在寻找具有以下属性的特定哈希码。我不知道任何这样的哈希码，我不知道是否有可能做这样的事情。只是想把它放在那里，看看人们怎么说。

我有两个数据库（松散使用的术语 - 不要想到 SQL 或类似的东西），一个主数据库和一个备份数据库。需要保持两个数据库同步并检测数据库何时不同步。与其验证那里的每个数据，不如保留一些可以验证的哈希码。但是这两个数据库不一定共享所有修改。由于从 master 到 backup 的更改是批处理的，因此从 master 到 backup 的某些修改可能会被折叠。

即：假设数据库的当前状态具有元素 A->X、B->Y 和 C->Z。现在 B 被修改为 B->Y1，然后是 B->Y2。从主服务器发送到备份服务器的唯一更改是 B->Y2。中间的 B->Y1 被跳过。

现在，与其循环遍历每个数据库中的每个元素以验证它们是否匹配，我们更愿意在两个位置保留元素的运行哈希码，然后进行比较。哈希码必须计算如下：

假设 hm0 的前一个哈希码：
hashcode hm1 = f(hm0, A->X, B->Y, C->Z)

当 B 现在发生变化时：
hashcode hm2 = f(hm1, B->Y1)
然后
hashcode hm3 = f(hm2, B->Y2)

所以master会有h3的hashcode。现在备份将不会收到修改 B->Y2，所以如果它计算一个运行哈希码，它将是这样的：

哈希码 hb1 = f(hb0, A->X, B->Y, C->Z)
哈希码 hb2 = f(hb1, B->Y2)

现在我们希望 hb2 和 hm3 匹配，因为数据库的当前状态是相同的。但是大多数（如果不是全部）哈希码都不是这样工作的。

所以我们想要的是，我们首先要从哈希中“移除”B->Y 的贡献，然后“添加”B->Y1 的贡献，然后移除 B->Y1 的贡献并添加B->Y2 对哈希码的贡献。所以我们想要这样的东西：

两个函数 f, g：f 通过添加新元素的贡献来修改现有的哈希码，而 g 通过删除元素的贡献来修改现有的哈希码。

在主机上：
hm1 = f(hm0, A->X, B->Y, C->Z)

当 B 修改为 B->Y1 时：
hm2 = g(hm1, B->Y)
hm3 = f(hm2, B->Y1)

当 B 修改为 B->Y2 时：
hm4 = g(hm3, B->Y1)
hm5 = f(hm4, B->Y2)

hm5 是数据库当前状态的新哈希码 (A->X, B->Y2, C->Z)

备份时：
hb1 = f(hb0, A->X, B->Y, C->Z)

当 B 修改为 B->Y2 时：
hb2 = g(hb1, B->Y)
hb3 = f(hb2, B->Y2)

现在 hm5 和 hb3 应该匹配，因为两个数据库的当前状态是相同的。

那么：有没有这样的算法f和g？我希望我把问题说清楚了......谢谢。

4

2 回答 2

1

只需添加和减去您的代码。h(x) 是任意散列函数：

hm2 = hm1 + h(B->Y)
hm3 = hm2 + h(B->Y1)
hm4 = hm3 - h(B->Y1) 
hm5 = hm4 + h(B->Y2)

hb2 = hb1 + h(B->Y)
hb3 = hb1 + h(B->Y2)

hm5 和 hb3 相等。

请注意，它不一定必须是加法或减法。任何可逆操作都可以工作（理论上乘法/除法也可以工作，但可能存在更多溢出问题和关于 0 附近发生的情况的模糊性）。

于 2009-04-05T18:51:29.217 回答
0

唔。我不确定哈希函数是否完全符合您的要求。但似乎类似于 Git 如何存储其修订的结构可能会满足您的需求（这受到 Monotone 如何存储其修订的启发）。

Git 计算存储库中每个文件的 SHA-1 总和。这些用作 blob 标识符。然后它有一个树，它将文件名映射到 blob ID（和其他子树，用于子目录）。树的标识符是它的 SHA-1 和。（虽然它与您的用法无关，但我不相信，这些树随后会被修订引用，其中包括作者、日期和一个或多个父修订等内容）。

这意味着您不必在更新一个 blob 时重新计算每个 blob 的 SHA-1 总和；您只需为更改的 blob 重新计算 SHA-1，然后为树重新计算 SHA-1。

你可以对你的数据做同样的事情。计算每个对象的哈希值，并将所有 key->hash(value) 映射放入一个文件中，然后计算该文件的哈希值。如果包含 key->hash(value) 的文件太大以至于你不想每次都重新散列它，你可以把它分成几个部分，并有一个 key->hash(section)，每个部分都有 key- >哈希（值）。对于大多数情况，一级分支通常就足够了，但如果你真的需要，你可以从这些分支中构建一个树结构。

于 2009-04-05T18:59:53.673 回答