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

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

如果你有一个长度为 log2(N) 字节的散列，你可以使用 Hamming code .如果它必须更短，那么 Low-density parity-check代码可以完成这项工作。