技术
LZ77 匹配查找的三条路线:哈希表 哈希链 二叉树
📅 2026-09-28 · ✍️ 闪压技术团队 · ⏱ 4 分钟阅读
滑动窗口说了去哪里找,没说怎么找得快
讲 LZ77 的时候,大家的注意力通常都放在滑动窗口上:缓冲区划成两段,靠前的一段是可以被引用的历史字典,靠后的一段刚落下来、还没被引用过。每进来一个新字节,压缩器都要在字典区里翻出一段和当前位置开头的字节完全一致的内容,拿它的长度和偏移量去顶替原样输出。
这一步回答了"去哪里找",却没回答"怎么找得快"。字典区随文件推进不断扩大,几乎每个新位置都可能触发一次查找。策略收得太紧,包能再小一点,速度就塌下去;放得太松,速度上来了,包里又会多出一截。这条取舍线基本决定了一个压缩器的性格。
路线一:哈希表,只认最短的键
最直接的思路是建一张表。拿当前位置开头的那段字节当键,哈希成一个数,值里存这段串在字典区出现过的位置。
查找时用当前位置的字节去查表,一次就跳到候选位置上,不再一处一处比对。听着很美,但键不能取得太短。键短意味着大量不同的字节序列挤进同一个桶,查出来一堆位置还得挨个验证,速度优势被抵消;键长意味着键不容易命中,表里大量条目永远用不上,压缩率白白下降。
哈希表走的是"一次查表换掉整段扫描"的路线,代价是匹配长度上不去。
路线二:哈希链,把同键的位置串成队
哈希表只留一个位置,哈希链把同键的所有位置都留着,串成一条链。查找先落到桶头,再沿链一路比下去,遇到更长的匹配就更新记录。
链可以设长度上限。设得短,查找快,但长链里藏着的更长匹配可能被砍掉;链拉长,长匹配能被捞上来,查找时间跟着往上走。
这条路像是"把同一类候选排成队挨个过一遍",平衡点全靠链长这一个旋钮。Zstandard 的早期实现就走在这里。
路线三:二叉树,按长度组织候选
第三条路线不再按哈希值组织候选,而是把所有候选位置构造成一棵按字典序比较的树。查找从根往下走,比当前记录长的分支优先走,短的那一侧直接剪掉。
好处是搜索范围被结构本身压住了,不必一条条挨个比,也不必盲目拉长链表。代价是插入和删除都要维护树结构,内存占用和指针跳转都比前两条路线更重。这条路线的名字在很多压缩器里都见过,LZMA 用的就是它。
三条路线共同的代价:拿空间换时间
不管走哪条,本质都是拿内存换查找速度。哈希表省的是查找时间,花的是哈希桶和位置数组;哈希链省的是桶空间,花的是链上的重复验证;二叉树省的是无效比较,花的是树节点和维护成本。
所以压缩器几乎都会留一个"搜索深度"或"哈希链长度"之类的旋钮,让用户在包小一点和快一点之间自己挑。ZIP 在极速档和存储档之间那几级,以及不少压缩工具界面上"只求速度"和"尽量压小"的预设,背后调的都是这件事。
为什么闪压默认取中间档
本地桌面压缩最常见的场景,不是追求极限包体积的离线归档,而是点一次压缩、传个文件、马上接着用。这种场景下把查找策略拉得太激进,换来的是用户多盯着转几圈进度条;拉得太保守,包里多出来的那点体积,用户基本感知不到。
闪压在文件压缩里默认取中间档,把旋钮留给需要极端取舍的人。想清楚"找匹配"本质上要在速度和体积之间做选择,就能明白大多数压缩选项为什么长成现在这个样子。