How 7-Zip Optimizes Matching with Hash Chains

7-Zip relies heavily on the LZMA compression algorithm, which achieves high compression ratios by identifying recurring byte sequences inside a sliding dictionary. To locate these matches at high speeds, 7-Zip implements specialized hash chain search algorithms that quickly index previous data positions, discard irrelevant candidates, and balance search depth against processing time. This article breaks down how 7-Zip constructs and traverses hash chains to optimize dictionary matches during compression.

The Role of Hash Chains in LZMA Compression

In dictionary-based compression like LZ77 and LZMA, the encoder must find the longest previous occurrence of the current data stream within a defined history window. A naive linear scan across a large dictionary—often 16 MB to 1 GB in size—would make compression impossibly slow.

To solve this, 7-Zip employs a Match Finder subsystem. While maximum-compression modes often use Binary Trees (bt2, bt3, bt4), faster modes rely on Hash Chains (hc3, hc4). A hash chain records the positions of previous byte sequences using a hash table where entries with the same hash value are linked together in reverse chronological order.

Multi-Level Hashing

A standard single hash table struggles to distinguish between very short matches and long matches efficiently. 7-Zip overcomes this by using multi-level hash arrays simultaneously:

  • 2-Byte and 3-Byte Hashes: 7-Zip uses dedicated tables (often referred to as Hash2 and Hash3) directly indexed by short byte combinations. This avoids hash collisions for small lengths and allows rapid evaluation of short matches.
  • 4-Byte Hashes: A primary hash function maps 4-byte sequences into a larger hash table, pointing to the head of the chain for longer candidates.

By separating lookups into discrete length tiers, 7-Zip eliminates the overhead of calculating complex hash functions or traversing deep chains when only short matches exist.

Contiguous Array Storage and Cache Locality

Instead of using traditional pointer-based linked lists, 7-Zip stores hash chains inside flat, pre-allocated cyclic arrays of 32-bit integers.

  1. Table Lookup: When the encoder processes a position, it computes the hash of the current bytes to retrieve the index of the most recent match candidate.
  2. Chain Traversal: The chain array stores the index of the candidate that preceded the current one. The algorithm jumps backward through indices directly in memory.
  3. In-Place Updates: The algorithm overwrites the oldest entries as the sliding window advances, avoiding dynamic memory allocation during active compression loops.

Storing indices in contiguous arrays maximizes CPU cache utilization, reducing memory latency when walking through candidate positions.

Search Depth Limiting (Match Cycles)

Iterating through an entire hash chain guarantees finding the absolute longest match, but long chains can cause severe performance drops on repetitive or redundant data.

7-Zip prevents this bottleneck using a configurable cutoff parameter known as MC (Match Cycles):

  • The search stops after inspecting a predetermined number of candidates, regardless of whether the chain has ended.
  • If a candidate meets or exceeds a target threshold (such as a maximum match length or an early good-enough match), the search terminates immediately.
  • This bound transforms the worst-case time complexity from \(O(N \times D)\) down to a predictable, bounded number of operations per byte, ensuring stable throughput.

Comparison Skip Optimizations

When traversing the chain, comparing every candidate byte-by-byte would be inefficient. 7-Zip accelerates comparisons using two key techniques:

  • Boundary Checking: The engine checks the final byte of the currently known best match before comparing the full sequence. If the candidate does not match at that specific offset, the algorithm skips the candidate immediately.
  • Prefix Matching: Because the hash already guarantees that the initial bytes match (e.g., the first 2, 3, or 4 bytes), the comparator skips inspecting those initial positions and begins verification further along the sequence.

Hash Chains vs. Binary Trees in 7-Zip

7-Zip selects hash chains when compression speed takes priority over absolute file size reduction. While binary trees maintain sorted branches to find optimal matches for the LZMA optimal parser, they require updating child pointers on every position shift. Hash chains simply update a single head pointer and prepend the current index to the list. This reduced maintenance cost makes 7-Zip's hash chain match finders significantly faster for medium and fast compression presets.