LZ4算法详解：无Hash链的快速匹配，为什么它比gzip快10倍？
大家好，我是你们的老朋友。今天我们来聊聊LZ4——这个号称“压缩界的法拉利”的算法。
说实话，我第一次接触LZ4是在一个实时日志采集系统里。当时gzip压缩太慢，CPU扛不住。我试了试LZ4，好家伙，压缩速度直接飙到500MB/s。那一刻我就知道，这玩意儿不简单。
那LZ4到底凭什么比gzip快10倍？核心就一句话：它放弃了复杂的Hash链，用了一种更“莽”的匹配方式。
LZ4的核心思想：用空间换时间
LZ4和gzip都基于LZ77算法家族。LZ77的核心是找重复的字符串，然后用“距离+长度”来替换。
但区别在于：
- gzip：用Hash链维护一个复杂的字典，每次匹配都要遍历链表。匹配精度高，但开销大。
- LZ4：只用一张简单的Hash表，每个位置只存最近一次出现的位置。没有链表，没有回溯。
你想想看，gzip的Hash链可能长达几十个节点，而LZ4的Hash表就一个槽位。这速度能不快吗？
核心结论：LZ4的匹配策略是“宁可漏掉，也要快”。它不追求最优匹配，只追求“够用”的匹配。
LZ4的匹配流程：三步走
我习惯把LZ4的匹配过程拆成三步，这样好理解：
- 计算Hash值：取当前4字节，算一个Hash值。
- 查Hash表：看这个Hash值对应的位置，有没有存过数据。
- 比较并更新：如果存过，就尝试匹配；然后更新Hash表为当前位置。
就这么简单。没有链表遍历，没有多级索引。嗯，这里要注意：LZ4的Hash表大小是固定的，通常是2^16或2^17个槽位。
为什么Hash链是性能杀手？
我曾经在一个嵌入式项目里踩过坑。当时用了zlib（gzip的库），压缩速度死活上不去。一分析，发现Hash链的遍历占了40%的CPU时间。
为什么会这样？
Hash链的问题在于：
- 每个槽位可能挂着一个链表，长度不定。
- 匹配时，需要遍历链表，比较每个候选位置。
- 链表越长，匹配越慢。最坏情况下，可能遍历几十个节点才找到一个匹配。
LZ4直接砍掉了链表。每个槽位只存一个位置。匹配时，看一眼就行。不匹配？拉倒，继续往下走。
我的建议：如果你的场景对压缩率要求不高，但对速度敏感，LZ4几乎是唯一选择。比如实时日志、网络传输、内存数据库。
LZ4的匹配限制：最短匹配长度
LZ4还有一个关键设计：最短匹配长度是4字节。
为什么是4？因为Hash值就是基于4字节算的。少于4字节，Hash值算出来也没意义。
这个设计带来的好处是：
- 减少了小匹配的尝试次数。
- 匹配长度用可变长编码存储，效率更高。
但代价也很明显：如果数据里大量重复的是2-3字节的片段，LZ4就无能为力了。这时候压缩率会下降。
LZ4 vs gzip：性能对比
我整理了一份实测数据，供你参考：
| 指标 | LZ4 | gzip (默认级别) |
|---|---|---|
| 压缩速度 | ~500 MB/s | ~50 MB/s |
| 解压速度 | ~1.5 GB/s | ~200 MB/s |
| 压缩率 | ~50% | ~35% |
| 内存占用 | ~4 KB | ~256 KB |
你看，LZ4的压缩速度是gzip的10倍，解压速度更是7倍以上。代价是压缩率差了15%左右。
避坑指南：我曾经在一个存储系统里直接用LZ4压缩文本日志，结果压缩率只有40%，比预期的50%差了不少。后来发现是因为日志里有很多短重复片段（比如时间戳的“2024-”部分只有4字节）。解决方案是先用一个预处理步骤，把短重复合并成更长的块。
LZ4的编码格式：简洁到极致
LZ4的压缩数据格式也很简单。它由一系列指令组成，每个指令包含：
- 字面量长度：未匹配的原始数据长度。
- 字面量数据：原始字节。
- 匹配信息：距离（offset）和匹配长度。
没有复杂的霍夫曼编码，没有动态字典。就是纯粹的LZ77 + 简单的可变长编码。
这种设计让解压也变得极快。解压时只需要：
- 读取指令。
- 复制字面量。
- 根据距离和长度，从已解压的数据中复制匹配。
说白了，就是内存拷贝。现代CPU对memcpy有硬件加速，所以LZ4的解压速度能跑到1.5GB/s以上。
什么时候选LZ4？
根据我的经验，以下场景LZ4是首选：
- 实时数据流：比如Kafka、Flume中的消息压缩。
- 内存数据库：比如Redis的RDB快照压缩。
- 网络传输：比如WebSocket的Payload压缩。
- 日志收集：比如Fluentd、Logstash的日志压缩。
但如果你的场景是：
- 存储长期归档数据。
- 带宽极度受限（比如卫星通信）。
- 对压缩率有硬性要求。
那还是老老实实用gzip或者zstd吧。
LZ4的变种：HC（High Compression）
LZ4还有一个“高压缩”版本，叫LZ4 HC。它牺牲了压缩速度，换来了更好的压缩率。
LZ4 HC的原理是：在匹配时，不再只看Hash表的一个位置，而是尝试多个候选位置。但即便如此，它依然没有用Hash链，而是用了更复杂的搜索策略。
我个人的建议是：除非你对压缩率有中等要求，否则别用LZ4 HC。它的压缩速度只有普通LZ4的1/10，但压缩率只提升5-10%。性价比不高。
总结
LZ4之所以比gzip快10倍，核心原因就两个：
- 无Hash链：每个Hash槽只存一个位置，匹配时O(1)复杂度。
- 极简编码：没有霍夫曼、没有动态字典，解压就是内存拷贝。
它用压缩率换速度，适合那些“快比省更重要”的场景。
好了，这一章就到这里。下一章我们会深入LZ4的源码，看看它到底是怎么实现“无Hash链”的。到时候我会带大家手写一个迷你LZ4，敬请期待。
公众号:蓝海资料掘金营，微信deep3321