Does linear hashing eliminate collisions?

No. Different keys can still reach the same bucket, and overflow handling may be required.

Does it always split the overflowing bucket?

No. In the basic ordered scheme, the split pointer determines which bucket splits.

Why are two hash ranges needed during growth?

Some buckets have split into the larger range while others still use the old range. The pointer tells lookup which rule applies.

AI Glossary / Graphs and symbolic AI / Intermediate

Linear hashing

Definition

Linear hashing is a dynamic hashing method that expands a table or file by splitting buckets in a predetermined sequence. A split pointer records progress through the current expansion round, allowing lookup to choose the appropriate hash function while some buckets have already split and others have not.

What it means

Ordinary hashing maps keys to storage locations. As records accumulate, collisions and overflow can make a fixed-size arrangement less convenient. Linear hashing distributes growth across successive bucket splits instead of requiring every record to move in a single table-wide expansion.
Here, linear describes the ordered progression of splits. It does not mean searching every record, fitting a straight line, or trying adjacent cells after a collision. Those are different ideas. A bucket may contain several records, and overflow handling remains necessary because adding capacity does not guarantee that all keys distribute evenly.

How it works

Maintain a base bucket count, an expansion level, and a pointer to the next bucket scheduled for splitting. During a round, the current hash function addresses the old range; the next function addresses twice that range. If the old address belongs to a bucket already split, lookup uses the next function.
A split adds one bucket and redistributes records from the scheduled bucket between its old address and its new partner. Then the pointer advances. After the round, the larger range becomes the base for the next round. The event triggering a split and the bucket selected for splitting need not refer to the same bucket.

Three practical examples

A growing record store can expand its key-addressing structure incrementally as records arrive.
A database designer can study how bucket splits interact with overflow chains and storage utilization.
An engineer comparing indexing methods can test equality lookups during sustained insertions, including operations that trigger structural maintenance.

Think of it this way

Think of a filing system that divides one drawer at a time according to a posted schedule. A progress marker tells staff which drawers now have companion drawers. The analogy stops at the addressing rule: real linear hashing uses deterministic computations on keys, not a person deciding where a document seems to belong.

Worked example

Consider an invented table starting with four primary buckets numbered 0 through 3. Use h0(k) = k mod 4 and h1(k) = k mod 8, where mod means the remainder after division. Let the split pointer s identify the next unsplit bucket, initially 0.
Suppose bucket 0 and its associated overflow contain keys 0, 4, 8, and 12. When a split is requested, bucket 0 splits and new bucket 4 is added. Applying h1 puts 0 and 8 in bucket 0, while 4 and 12 move to bucket 4. The pointer becomes 1.
To find key 12, first compute h0(12) = 0. Because 0 is less than s = 1, that old bucket has already split. Recompute h1(12) = 4 and search bucket 4, including any associated overflow. To find key 5, h0(5) = 1. Since 1 is not less than s, use bucket 1 without switching functions.
The next scheduled split is bucket 1, adding bucket 5, even if an insertion elsewhere triggered it. After splitting buckets 0, 1, 2, and 3, eight primary buckets exist. The pointer resets and the next round uses ranges of eight and sixteen. This example establishes addressing behavior, not a measured performance result.

Illustrative case study

In a fictional system, Alder Records tests an incrementally growing customer-key index. A developer assumes that every collision must immediately split the bucket containing that collision. That implementation disagrees with the planned split-pointer scheme and makes the lookup metadata unreliable.
The team writes a small trace showing the pointer, bucket count, and destination of every sample key after each split. They also test keys whose old bucket has already split and keys whose bucket has not. The fictional lesson is that growth and lookup must use the same definition of split progress; an extra bucket alone does not make a valid index.

Common misconceptions and mistakes

Linear hashing is not linear probing. Linear probing resolves collisions by visiting a sequence of positions inside an open-addressed table; linear hashing describes dynamic growth through bucket splitting.
Incremental growth also does not imply that every operation takes identical time. Splits move records, overflow can require additional work, and poor key distribution can affect performance. The method is not a cryptographic hash function and does not conceal sensitive identifiers. Finally, a pointer convention must be explicit: this entry uses the pointer as the next unsplit bucket, so the test for an already split address is strictly less than the pointer.

Business use

The relevant business question is whether an indexing implementation supports the actual pattern of growth and access. Measure insertion throughput, lookup latency, storage overhead, and the cost of split operations using representative keys.
Compare methods under the same durability and concurrency requirements. A classroom bucket trace omits locking, recovery after interruption, and allocation details that matter in a production store. Also distinguish equality lookup from ordered or range queries: hashing a key does not inherently arrange records in business order. Choose the index around query requirements rather than treating gradual expansion as a universal advantage.

Check your understanding

In the worked example after the first split, why is key 12 looked up in bucket 4 rather than bucket 0?

Answer: Its old hash address is 0, which is below the next-unsplit pointer 1. That address has already split, so lookup uses 12 mod 8 = 4.

Related terms

Hash function
Extendible hashing
Linear probing
Database index
Hash table
bucket
collision resolution
overflow chain
load factor

Learn next

Trace a second split using keys 1, 5, 9, and 13. Verify both their new destinations and lookups after the pointer advances to 2. Then compare this process with linear probing so that table growth and collision resolution remain separate concepts.

Linear probing

Sources

Witold Litwin, original paper, Linear Hashing: A New Tool for File and Table Addressing: https://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf NIST Dictionary of Algorithms and Data Structures, linear hashing: https://xlinux.nist.gov/dads/HTML/linearHashing.html

Previous: Linear filter Next: Linear interpolation