核心算法基础：二进制差异、字节级比较、块级别哈希、滚动哈希算法原理

好，咱们进入第二章。说实话，这一章是整个差分更新技术的「地基」。你想想看，如果连两个文件到底差在哪都说不清楚，那后面什么增量包、补丁生成全都是空中楼阁。

我个人习惯把差分算法拆成四个层次来理解：二进制差异是底层视角，字节级比较是朴素方法，块级别哈希是工程优化，滚动哈希是真正让差分实用化的关键。咱们一层一层往上走。

2.1 二进制差异：最朴素的视角

两个文件，在计算机眼里就是两串二进制数据。所谓二进制差异，就是逐比特对比，找出「哪里不同」。

举个例子：

文件A（旧版）： 0x48 0x65 0x6C 0x6C 0x6F 0x00
文件B（新版）： 0x48 0x65 0x6C 0x70 0x21 0x00

肉眼一看，第4字节从 0x6C 变成 0x70，第5字节从 0x6F 变成 0x21。这就是最原始的差异描述。

我在项目中遇到过有人直接用 diff 命令对比二进制文件，结果输出一堆乱码。嗯，这里要注意：二进制差异不适合用文本 diff 工具处理，必须用专门的二进制比较工具或算法。

2.2 字节级比较：简单但低效

字节级比较是最直接的实现方式。把两个文件从头到尾逐字节对比，记录所有差异位置。

伪代码大概长这样：

function byteLevelDiff(oldData, newData):
    changes = []
    for i = 0 to min(len(oldData), len(newData)):
        if oldData[i] != newData[i]:
            changes.append({offset: i, oldByte: oldData[i], newByte: newData[i]})
    // 处理长度不一致的情况
    if len(oldData) != len(newData):
        // 记录多余或缺失的部分
    return changes

这个方法的问题很明显——太慢了。两个 1GB 的文件，逐字节对比要扫描 10 亿次。而且它只告诉你「哪里变了」，不告诉你「哪些部分没变可以复用」。

2.3 块级别哈希：分而治之

既然逐字节太慢，那就把文件切成块，逐块比较。这就是块级别哈希的核心思想。

具体做法：

1. 将旧文件和新文件分别切成固定大小的块（比如 4KB 一块）
2. 对每个块计算哈希值（MD5、SHA-1 或更快的 xxHash）
3. 通过哈希值匹配，找出哪些块在新旧文件中相同，哪些不同

哈希值匹配的逻辑：

function blockLevelDiff(oldBlocks, newBlocks):
    // 构建旧文件哈希索引
    hashIndex = {}
    for i, block in enumerate(oldBlocks):
        hashIndex[hash(block)] = i
    
    // 匹配新文件块
    matches = []
    for j, block in enumerate(newBlocks):
        h = hash(block)
        if h in hashIndex:
            matches.append({oldIndex: hashIndex[h], newIndex: j})
    
    return matches  // 匹配的块可以复用，未匹配的块需要传输

这里有个细节：哈希碰撞。两个不同的块可能算出相同的哈希值。我在项目中遇到过这种情况，结果补丁打上去文件就坏了。所以实际工程中，哈希匹配后还要做一次字节级确认，或者使用更安全的哈希算法。

块大小	优点	缺点
512B	匹配精度高，细粒度复用	哈希数量多，索引内存大
4KB	平衡性能和精度，常用	对小块插入/删除不敏感
64KB	哈希数量少，速度快	大块不匹配时浪费带宽

2.4 滚动哈希算法原理

块级别哈希有个硬伤——块边界固定。如果新文件在旧文件中间插入了一个字节，那从插入点开始，后面所有块的边界都偏移了，哈希全部不匹配。说白了，一个字节的插入会导致后面整个文件被视为「不同」。

滚动哈希就是来解决这个问题的。它的核心思想是：哈希值可以「滚动」计算，每次只滑动一个字节，就能快速得到新窗口的哈希值。

最经典的滚动哈希是 Rabin-Karp 算法中使用的多项式哈希：

H(window) = (c1 * B^(k-1) + c2 * B^(k-2) + ... + ck * B^0) mod M

// 滚动更新：去掉最左字节，加入最右字节
H(newWindow) = ((H(oldWindow) - c1 * B^(k-1)) * B + c_new * B^0) mod M

其中：

• c1...ck 是窗口内的字节值
• B 是基数（通常取一个大质数，如 257）
• M 是模数（控制哈希范围）
• k 是窗口大小（即块大小）

你看，滚动哈希把计算复杂度从 O(k) 降到了 O(1)。每次滑动只需要两次乘法和一次加法，性能提升非常明显。

我记得在实现 rsync 风格的差分算法时，滚动哈希是核心引擎。旧文件先按固定块计算哈希并建立索引，然后新文件用滚动哈希逐字节滑动查找匹配。匹配上的块直接复用，未匹配的字节作为「新数据」传输。这样生成的补丁，对插入/删除操作非常鲁棒。

下面这张图展示了滚动哈希在差分过程中的核心位置：

2.5 四种方法的对比总结

咱们把这四种方法放在一起对比一下，方便你理解各自的应用场景：

方法	粒度	时间复杂度	对插入/删除的鲁棒性	适用场景
二进制差异	比特级	O(n)	差（逐位对比）	小文件、固件补丁
字节级比较	字节级	O(n)	差（逐字节对比）	几 KB 以内的小文件
块级别哈希	块级（如 4KB）	O(n/k)	中等（块边界固定）	大文件、版本管理
滚动哈希	滑动窗口级	O(n) 但常数极小	强（自动适应偏移）	OTA 更新、文件同步