如何通过快速比较哈希来找到插入/删除？

Question

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

伪代码:

string getFileDiffHash(file){
    string result = "";
    for each (512 bytes in file){
        result += hash(bytes);
    }
}

string getFileDiff(file, diffHash){
    string result = "";
    for each (hash size bytes in diffHash){ //yes this would be in a hash table ideally, but hey, this is pseudocode
        string 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){
                result += "+"+diffHash+":"+i;
            }
        }
    }
    return result;
}

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

Answer 1

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