Folding and Other Compression Techniques

When building a hash table, one of the central challenges is mapping keys drawn from a very large universe of possible values into a much smaller range of table indices. Cryptographic identifiers, social security numbers, product codes, and other real-world keys can span billions or trillions of distinct values, yet a practical hash table might hold only a few thousand slots. Compression techniques are the methods used to bridge that gap: they accept a raw key, possibly already processed by a preliminary hash function, and reduce it to an integer that fits inside the table's address space. Folding is one of the most intuitive families of compression techniques because it works by physically breaking the key into manageable pieces and recombining them, much like folding a long strip of paper so that its layers overlap. The family also includes digit extraction and the mid-square method, each offering a different trade-off between implementation complexity, computational cost, and quality of distribution. Understanding all of these methods, and knowing when to prefer one over another, is essential background for designing efficient hash-based data structures.

Introduction to Folding

Folding begins with a straightforward observation: a large numeric key contains more digits (or bits) than are needed to address a hash table. Instead of discarding the excess digits entirely, folding keeps all of them by slicing the key into several equal-width segments and then combining those segments into a single value whose width matches the desired index size. Because every segment participates in the final result, the information content of the whole key influences the outcome, which tends to produce a more uniform spread than simply truncating the key.

Consider a nine-digit key such as 123456789 and a hash table that requires a three-digit index (addresses 000 through 999). Folding would split the key into three three-digit segments: 123, 456, and 789. These segments are then combined — most commonly by addition — to yield a single three-digit value. The guiding principles are:

• The key is split into parts, typically of a fixed width matching the desired index size. Equal-width segments keep the arithmetic uniform and predictable.
• The parts are added or otherwise combined to yield a single compressed value. Addition is the most common operation, but XOR or multiplication are also used in practice.
• This approach distributes large key values across a smaller address space without requiring complex arithmetic such as division or modular reduction of very large numbers (though a final modular step is often applied to handle carry).

Folding is particularly natural for numeric keys of fixed length, such as phone numbers, ZIP codes, or identification numbers, because these keys already arrive as digit strings that can be partitioned uniformly. The two main variants of folding are shift folding and boundary folding, described next.

Shift Folding

Shift folding is the simpler of the two variants. The key is divided into segments of equal width, reading left to right, and every segment is treated as an independent numeric value. All segments are then added together, and if the resulting sum exceeds the table size, a final modular reduction brings it back into range.

Using the nine-digit key 123456789 split into three-digit segments:

Segment 1:  123
Segment 2:  456
Segment 3:  789
-----------------
Sum:       1368

If the table has 1000 slots (indices 000–999), applying 1368 mod 1000 yields index 368. The key properties of shift folding are:

• Each segment is used exactly as it appears in the original key — no digits are reversed or rearranged. This is why it is called "shift" folding: conceptually, the strips are shifted on top of each other and their columns are summed.
• The resulting sum may be further reduced using modular arithmetic to fit the table size, making it easy to control the final index range without redesigning the folding procedure.
• Shift folding is simple to implement and works well for uniformly distributed numeric keys. Its weakness is that keys sharing many of the same digit patterns in corresponding segments will tend to produce the same or nearby sums, potentially causing clustering.

A second example illustrates the process for key 987654321:

Segment 1:  987
Segment 2:  654
Segment 3:  321
-----------------
Sum:       1962
1962 mod 1000 = 962  →  index 962

Notice that for a table of size 1000 the carry from the thousands column is simply discarded by the modular step, which is equivalent to keeping only the lower three digits of the sum.

Boundary Folding

Boundary folding modifies shift folding by reversing the digit order of every other segment before performing the addition. Visually, this resembles folding a paper strip at the boundary between adjacent segments so that alternate pieces are flipped upside-down. The reversal introduces additional mixing into the combined value.

Using the same key 123456789:

Segment 1 (kept as-is):    123
Segment 2 (reversed):      654   ← "456" reversed
Segment 3 (kept as-is):    789
-----------------------------
Sum:                       1566
1566 mod 1000 = 566  →  index 566

Compare this with the shift-folding result of 368 for the same key. Neither result is inherently "correct"; the goal is simply to achieve good spread across the table. The key properties of boundary folding are:

• Reversing alternate segments introduces additional mixing, which can improve distribution over shift folding alone. The reversal means that two keys that differ only in the ordering of digits within a segment will produce different folded values.
• The reversal step helps avoid clustering that can occur when many keys share similar digit patterns in the same segment positions. For example, if a dataset contains many keys whose middle three digits are all in the range 400–499, shift folding would cause all of those sums to be close together, while boundary folding spreads them further apart.
• Boundary folding is slightly more complex to implement — the code must track which segment index is odd or even and reverse accordingly — but often produces better spread across the index range, especially for structured or partially repetitive key sets.

A side-by-side comparison for two keys illustrates how boundary folding differentiates them more sharply:

The third and fourth rows show that for highly symmetric keys, boundary folding may not produce a different result than shift folding because the reversed segment is numerically identical to the original. This underscores that no single compression technique dominates in all cases.

Digit Extraction

Digit extraction takes a completely different approach. Rather than using all segments of a key, the method selects a small, predetermined subset of digit positions from the key and uses only those digits to form the index. The assumption is that some positions in the key vary widely across different keys while other positions are nearly constant and therefore carry little distinguishing information.

For example, consider employee identification numbers of the form DDYYMMSSSS, where DD is a two-digit department code, YY is a two-digit hire year, MM is a two-digit hire month, and SSSS is a four-digit sequence number. If all employees were hired in the same department (making DD constant) and within a narrow date range (making YY and MM nearly constant), extracting positions 7–10 (the sequence digits) would yield good spread, while extracting positions 1–4 would produce severe clustering.

• Positions with the greatest variation are chosen to maximize spread across the hash table. This requires analyzing the actual distribution of keys in advance.
• Poorly chosen positions can lead to severe clustering if many keys share the same digits at those locations. Using the department code in the example above would map all employees from one department to the same small cluster of indices.
• Digit extraction requires prior knowledge of the key distribution to be applied effectively. It is a static technique: once the positions are selected, the method works well only for keys that continue to follow the expected pattern.

Digit extraction is extremely fast — the implementation need only pick out specific characters from a string or specific bit fields from an integer — but its quality is entirely dependent on the quality of the position analysis. It is most useful in specialized applications where the key structure is well understood and stable, such as look-up tables for fixed-format records.

Mid-Square Method

The mid-square method is based on the idea that squaring a number causes its middle digits to depend on all digits of the original number through the cross-product terms of multiplication. This makes the middle digits a more thoroughly mixed function of the entire key than any segment of the key alone.

The procedure is:

• Square the key: compute key².
• Extract the middle digits (or middle bits, in a binary implementation) of the squared value.
• Use those extracted digits as the hash index, possibly followed by a modular reduction.

For a concrete example, consider key 3121 and a table requiring a two-digit index:

key       = 3121
key²      = 3121 × 3121 = 9,740,641
digits    = 9 7 4 0 6 4 1  (7 digits total)
middle 2  = positions 3–4 from the left → "40"  (or depending on convention, "06")
index     = 40

The exact middle positions extracted depend on the implementation and the desired number of index digits, but the principle is that the center of the squared value is chosen because it is most influenced by all parts of the original key. The key properties of the mid-square method are:

• Squaring the key causes the middle digits to depend on all digits of the original key, improving mixing. This is a genuine mathematical property: in the expansion of (a·10ⁿ + b)² the cross-term 2ab·10ⁿ appears in the middle of the result, coupling the high and low halves of the key.
• The number of middle digits extracted is chosen to match the desired index range size. If you need indices from 0 to 9999, you extract four middle digits; if you need 0 to 999, you extract three.
• This method can produce good distribution but requires handling very large intermediate values when keys are large. A ten-digit key squared produces a value up to twenty digits long, which overflows standard 32-bit integers and may even overflow 64-bit integers, requiring arbitrary-precision arithmetic or careful bit manipulation.

The mid-square method was historically popular in early computing when multiplication was available as a hardware instruction but division (needed for modular reduction) was costly. On modern hardware, modular arithmetic is inexpensive, so the mid-square method is less commonly the first choice, but it remains a useful conceptual tool for understanding mixing.

Comparing Compression Strategies

Each of the techniques described above occupies a different point in the design space defined by implementation effort, computational cost, sensitivity to key structure, and quality of distribution. The table below summarizes these trade-offs:

Several broader observations tie these techniques together:

• Folding methods are computationally inexpensive and easy to implement for numeric keys of fixed length. They require only addition (and possibly string reversal), making them attractive in performance-critical applications that process millions of keys per second.
• Digit extraction is fast but highly dependent on domain knowledge about the key structure. When that knowledge is available and the key format is stable, digit extraction can outperform all other methods in speed while still achieving good distribution. When the key structure is unknown or variable, it is dangerous.
• The mid-square method provides stronger mixing at the cost of handling large intermediate values. For short keys — say, four or five digits — the squared value is manageable within a 64-bit integer, and the method is practical. For long keys, the intermediate value may need special handling.
• All these techniques may be combined with modular arithmetic as a final step to ensure the index fits within the table bounds. Regardless of which compression technique is used, computing result mod tableSize as a last step is a reliable way to clamp the output to the valid index range. Choosing a prime number for tableSize further reduces the likelihood of systematic collisions when the hash values are not already well distributed.

In practice, most modern hash function libraries use bit-level operations (XOR, rotation, multiplication by carefully chosen constants) rather than digit-based folding, because bits generalize naturally to non-numeric keys such as strings and binary objects. Nevertheless, the conceptual foundations established by folding and the other techniques surveyed here — segment decomposition, selective extraction, and mixing through arithmetic — appear in recognizable form inside many contemporary hash functions, making them valuable models for understanding why and how hashing works.