5

我想创建一个文件的哈希，这样如果文件被更改，我可以确定文件的哪些部分发生了更改。问题是，如果删除或添加一个字节，所有后续散列也会发生变化，因此我需要通过所有散列遍历每个字节。然而，这可能很昂贵，所以我正在寻找一个不需要我重新计算整个哈希开始到完成而是让我撤消一个字节然后添加另一个字节的哈希。

伪代码：

字符串 getFileDiffHash(文件){
    字符串结果 = "";
    对于每个（文件中的 512 个字节）{
        结果+=哈希（字节）；
    }
}

字符串 getFileDiff（文件，diffHash）{
    字符串结果 = "";
    对于每个（diffHash 中的哈希大小字节）{ //是的，理想情况下这将在哈希表中，但是嘿，这是伪代码
        字符串 current_hash = "";
        for (i = 0; i < file_size(file); i++){
            if (current_hash.size > hash_size){
                current_hash = undo_hash(current_hash, file[i-hash_size]);
            }
            current_hash = add_hash(current_hash, file[i]);
            if (current_hash.size == hash_size && bytes == current_hash){
                结果 += "+"+diffHash+":"+i;
            }
        }
    }
    返回结果；
}

关于什么样的哈希适合“undo_hash”和“add_hash”的任何想法？

4

2 回答 2

0

如果您可以拥有长度为 log2(N) 字节的哈希，则可以使用汉明码。如果它必须更短，那么低密度奇偶校验码就可以完成这项工作。

于 2013-06-14T23:37:37.670 回答
0

@Interjay 的评论是正确的，我需要一个滚动哈希。此外，我在这里描述的算法类似于 rsync 所做的（以及 Dropbox 的扩展）。

于 2013-06-14T23:39:47.030 回答