具有可逆属性的校验和/哈希函数 [英] checksum/hash function with reversible property

问题描述

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

I am looking for a specific hashcode that has the following properties. I dont know of any such hashcodes and I dont know if it is possible to do such a thing. Just wanted to put it out there and see what people say.

我有两个数据库(经常使用的术语-不要想到SQL或类似的任何东西)，一个数据库和一个备份.有必要使两个数据库保持同步，并检测何时数据库不同步.与其验证每个数据，不如保留一些可以验证的哈希码.但是，两个数据库不一定共享所有修改.由于从主服务器到备份的更改是批量处理的，因此从主服务器到备份的某些修改可能会被折叠.

I have two databases (loosely used term - dont think of SQL or anything of that sort), one master and one backup. There is a need to keep the two databases in sync and to detect when the databases are not in sync. Instead of verifying every data in there, it would be preferable to keep some hashcode that can be verified. But the two databases dont necessarily share every modifications. Since changes from master to backup are batched, it is possible that certain modifications from the master to backup are collapsed.

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

ie: lets say current state of database has elements A->X, B->Y and C->Z. Now B gets modified such that B->Y1 and then later B->Y2. The only change that will get sent from master to backup is B->Y2. The intermediate B->Y1 is skipped.

现在，我们不必遍历每个数据库中的每个元素以验证它们是否匹配，我们宁愿在两个位置都保留元素的运行哈希码，然后进行比较.哈希码必须计算如下内容:

Now instead of looping over every element in each database to verify that they match, we would prefer to keep a running hash code of the elements in both the locations and then just compare that. The hashcode would have to compute something like:

假设先前的哈希码为hm0:
哈希码hm1 = f(hm0，A-> X，B-> Y，C-> Z)

assuming previous hashcode of hm0:
hashcode hm1 = f(hm0, A->X, B->Y, C->Z)

当B现在改变时:
哈希码hm2 = f(hm1，B-> Y1)
然后
哈希码hm3 = f(hm2，B-> Y2)

When B changes now:
hashcode hm2 = f(hm1, B->Y1)
and then
hashcode hm3 = f(hm2, B->Y2)

因此master将具有h3的哈希码.现在，备份将不会收到B-> Y2的修改，因此，如果它计算正在运行的哈希码，它将是这样的:

So master will have hashcode of h3. Now backup will not receive the modification B->Y2, so if it computes a running hash code, it will be like this:

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

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

现在，我们希望hb2和hm3匹配，因为数据库的当前状态是相同的.但是大多数(如果不是全部)哈希码都无法通过这种方式工作.

Now we want hb2 and hm3 to match, as the current state of the databases are the same. But most (if not all) hashcodes dont work this way.

那么我们想要的是首先要从散列中删除" B-> Y的贡献，然后添加" B-> Y1的贡献，然后删除B-> Y1的贡献并将B-> Y2的贡献添加到哈希码中.所以我们想要这样的东西:

So what we would want then is that we would want to "remove" the contribution of B->Y from the hash first and then 'add' the contribution of B->Y1 and then remove contribution of B->Y1 and add the contribution of B->Y2 into the hash code. So we want something like this:

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

Two functions, f, g: f modifies existing hashcode by adding contribution of a new element, while g modifies existing hashcode by removing contribution of an element.

在母版上:
hm1 = f(hm0，A-> X，B-> Y，C-> Z)

On master:
hm1 = f(hm0, A->X, B->Y, C->Z)

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

when B gets modified to 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)

when B get modified to B->Y2:
hm4 = g(hm3, B->Y1)
hm5 = f(hm4, B->Y2)

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

hm5 is the new hashcode for the current state of the database (A->X, B->Y2, C->Z)

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

On backup:
hb1 = f(hb0, A->X, B->Y, C->Z)

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

when B gets modified to B->Y2:
hb2 = g(hb1, B->Y)
hb3 = f(hb2, B->Y2)

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

Now hm5 and hb3 should match, as the current state of both databases is the same.

那么:是否有f和g这样的算法?我希望我把问题弄清楚了..谢谢.

So: are there such algorithms f and g? I hope I made the question clear.... Thanks.

推荐答案

只需添加和减去代码即可. h(x)是任何哈希函数:

Just add and subtract your codes. With h(x) being any hash function:

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相等.

hm5 and hb3 are equal.

请注意，它不一定必须加或减.任何可逆的运算都将起作用(理论上乘/除也可以，但是可能存在更多的溢出问题以及关于0周围发生的模棱两可的问题).

Note that it does not necessarily have to be add or subtract. Any reversible operation will work (theoretically multiply/divide can also work, but there could be more overflow issues and ambiguity about what happens around 0).

这篇关于具有可逆属性的校验和/哈希函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！