Linear Probing in Hash Tables Tutorial

What Is Linear Probing?

Linear probing is an open-addressing technique used to resolve collisions in hash tables. When a key maps to a table position that is already occupied, linear probing checks the next position, then the next one, and continues until it finds a suitable slot.

Unlike separate chaining, linear probing does not maintain a separate collection for each bucket. Every key-value entry is stored directly inside the hash table.

Core idea: Hash Key → Initial Index → Collision → Check Next Index → Continue Until Available

Initial index = 3

Index 3 → occupied
Index 4 → occupied
Index 5 → empty

Store the new entry at index 5.

Why Is Linear Probing Needed?

A hash function maps keys to table indexes, but different keys can produce the same index. This is called a hash collision.

Table size = 7

10 % 7 = 3
17 % 7 = 3
24 % 7 = 3

10 → 3
17 → 3
24 → 3

Collision!

Linear probing resolves the collision by looking at nearby table positions instead of storing multiple entries inside the same bucket.

How Linear Probing Works

Linear probing uses a simple sequence of consecutive positions. If the initial position is occupied, the algorithm checks the next position.

Initial index = hash(key) % tableSize

Probe sequence:

index
(index + 1) % tableSize
(index + 2) % tableSize
(index + 3) % tableSize
...

The modulo operation allows the sequence to wrap around to the beginning of the table.

Linear Probing Example

Consider a hash table with seven positions and the hash function key % 7.

Insert 10

10 % 7 = 3

Index 3 is empty.

Store 10 at index 3.

Insert 17

17 % 7 = 3

Index 3 is occupied.

Check index 4.

Index 4 is empty.

Store 17 at index 4.

Insert 24

24 % 7 = 3

Index 3 → occupied
Index 4 → occupied
Index 5 → empty

Store 24 at index 5.

The final table is:

Index   Key
  0      -
  1      -
  2      -
  3      10
  4      17
  5      24
  6      -

Linear Probing Formula

The next position can be calculated using the following formula:

probeIndex =
  (initialIndex + attempt) % tableSize

If the initial index is 4, the probe sequence becomes:

Attempt 0 → 4
Attempt 1 → 5
Attempt 2 → 6
Attempt 3 → 0
Attempt 4 → 1
...

This predictable pattern is the defining characteristic of linear probing.

Insertion Using Linear Probing

During insertion, the table calculates the initial index and checks whether that position is available. If another key occupies it, the algorithm moves to the next index.

Calculate the hash value.
Calculate the initial table index.
Check the current slot.
If it is empty, insert the entry.
If the slot contains the same key, update the value.
If another key occupies the slot, move to the next position.
Repeat until an appropriate slot is found.

function insert(key, value) {
  let index = hash(key);

  while (table[index] !== undefined) {
    if (table[index].key === key) {
      table[index].value = value;
      return;
    }

    index = (index + 1) % table.length;
  }

  table[index] = { key, value };
}

Searching with Linear Probing

Searching follows the same sequence used during insertion. The algorithm begins at the key's original hash position and moves forward until it finds the key or reaches a position that proves the key cannot be present.

Table:

Index 3 → 10
Index 4 → 17
Index 5 → 24

Search for 24:

hash(24) → 3

Check 3 → 10
Check 4 → 17
Check 5 → 24

Found.

Searching cannot stop just because the first position contains a different key. That key may have been inserted there because of an earlier collision.

When Can a Search Stop?

In a basic linear-probing table without deleted markers, a search can stop when it reaches a slot that has never been occupied. If the probe sequence reached an unused slot, the requested key would have been placed there or before it if it existed.

Search for 31

hash(31) → 3

Index 3 → 10
Index 4 → 17
Index 5 → empty

Stop.

31 is not in the table.

This rule changes when deletion uses tombstones because a deleted position does not mean that the probe sequence can safely stop.

Deletion in Linear Probing

Deletion is more complicated than insertion because removing an entry can break the probe sequence used by later searches.

Index 3 → 10
Index 4 → 17
Index 5 → 24

Delete 17.

If index 4 becomes EMPTY:

Search for 24:
3 → 10
4 → EMPTY

Search incorrectly stops.

But 24 is at index 5.

To avoid this problem, open-addressed implementations commonly use a special deleted marker, also called a tombstone.

Tombstones

A tombstone indicates that an entry used to occupy the slot but has been deleted. A search continues through a tombstone, while an insertion can potentially reuse it.

Before deletion:

3 → 10
4 → 17
5 → 24


After deleting 17:

3 → 10
4 → DELETED
5 → 24


Search for 24:

3 → 10
4 → DELETED
5 → 24

Found.

Complete Linear Probing Implementation

The following example demonstrates insertion, searching, updating, deletion, tombstones, and wraparound in a linear-probing hash table.

class LinearProbingHashTable {
  constructor(size = 7) {
    this.table = new Array(size);
    this.deleted = Symbol('deleted');
  }

  hash(key) {
    return key % this.table.length;
  }

  set(key, value) {
    let index = this.hash(key);
    let firstDeleted = -1;

    for (
      let attempts = 0;
      attempts < this.table.length;
      attempts++
    ) {
      const entry = this.table[index];

      if (entry === undefined) {
        const target =
          firstDeleted !== -1
            ? firstDeleted
            : index;

        this.table[target] = { key, value };
        return;
      }

      if (entry === this.deleted) {
        if (firstDeleted === -1) {
          firstDeleted = index;
        }
      } else if (entry.key === key) {
        entry.value = value;
        return;
      }

      index = (index + 1) % this.table.length;
    }

    if (firstDeleted !== -1) {
      this.table[firstDeleted] = { key, value };
      return;
    }

    throw new Error('Hash table is full');
  }

  get(key) {
    let index = this.hash(key);

    for (
      let attempts = 0;
      attempts < this.table.length;
      attempts++
    ) {
      const entry = this.table[index];

      if (entry === undefined) {
        return undefined;
      }

      if (
        entry !== this.deleted &&
        entry.key === key
      ) {
        return entry.value;
      }

      index = (index + 1) % this.table.length;
    }

    return undefined;
  }

  delete(key) {
    let index = this.hash(key);

    for (
      let attempts = 0;
      attempts < this.table.length;
      attempts++
    ) {
      const entry = this.table[index];

      if (entry === undefined) {
        return false;
      }

      if (
        entry !== this.deleted &&
        entry.key === key
      ) {
        this.table[index] = this.deleted;
        return true;
      }

      index = (index + 1) % this.table.length;
    }

    return false;
  }
}

const table = new LinearProbingHashTable();

table.set(10, 'Alice');
table.set(17, 'Bob');
table.set(24, 'Carol');

console.log(table.get(10));
// Alice

console.log(table.get(17));
// Bob

table.delete(17);

console.log(table.get(17));
// undefined

console.log(table.get(24));
// Carol

Primary Clustering

One of the main disadvantages of linear probing is primary clustering. When several consecutive table positions become occupied, they form a cluster. Future collisions near that cluster can make it even larger.

Index:

0   1   2   3   4   5   6   7
        X   X   X   X
            ← cluster →

A new key whose initial position falls anywhere near the cluster may need to inspect several occupied positions before finding an available slot.

Why Primary Clustering Happens

Linear probing always moves one position at a time. If a collision creates an occupied position next to another occupied position, future insertions can extend the same consecutive block.

Existing cluster:

3 → A
4 → B
5 → C


New key hashes to 4:

4 occupied
5 occupied
6 empty

Store at 6.

Cluster becomes:

3 → A
4 → B
5 → C
6 → D

Wraparound in Linear Probing

When probing reaches the last position in the table, it wraps around to index zero. This allows the algorithm to examine the entire table when necessary.

Table size = 7

Current index = 6

Next index:

(6 + 1) % 7
= 0

Probe sequence:

6 → 0 → 1 → 2 → ...

Forgetting wraparound can cause an implementation to miss available positions near the beginning of the table.

Load Factor and Linear Probing

The load factor represents how full the table is:

Load Factor =
Number of Stored Entries / Table Capacity

For example, a table containing 6 entries and 10 positions has a load factor of:

6 / 10 = 0.6

As the load factor increases, there are fewer empty positions available and probe sequences generally become longer. Open-addressed hash tables therefore typically resize before the table becomes too crowded.

Rehashing After Resizing

When a linear-probing table is resized, existing entries are usually inserted into the new table again. This is necessary because the table capacity affects the hash index.

Old capacity = 7

17 % 7 = 3


New capacity = 13

17 % 13 = 4

Old position → 3
New position → 4

Rehashing also rebuilds the probe arrangement and can eliminate clusters that existed in the old table.

Linear Probing Performance

With a good hash function and a suitable load factor, linear probing can provide efficient average-case operations. However, collisions and clustering can increase the number of positions that need to be inspected.

Operation	Average Case	Worst Case
Search	O(1) expected	O(n)
Insertion	O(1) expected	O(n)
Deletion	O(1) expected	O(n)

The worst case occurs when a large portion of the table must be inspected, such as when many keys collide or the table becomes highly clustered.

Linear Probing vs Quadratic Probing

Both techniques use open addressing, but they calculate their next positions differently.

Feature	Linear Probing	Quadratic Probing
Probe pattern	Consecutive positions	Quadratic offsets
Formula	(index + attempt) % size	(index + attempt²) % size
Primary clustering	Can occur significantly	Reduced
Implementation	Simple	More involved

Linear Probing vs Separate Chaining

Linear probing and separate chaining use different ways to store collided entries.

Feature	Linear Probing	Separate Chaining
Collision handling	Find another table slot	Store another entry in the same bucket
Storage	Inside table array	Inside bucket collections
Load factor	Must remain below capacity	Can exceed 1
Deletion	Needs careful handling	Generally simpler
Clustering	Can occur	Long chains can occur instead

Advantages of Linear Probing

The basic algorithm is simple to understand and implement.
Entries are stored directly inside the table.
It does not require separate linked-list nodes for collided entries.
Consecutive table access can provide good memory locality in suitable implementations.
Only a small amount of metadata is required for the basic table structure.

Limitations of Linear Probing

Primary clustering can increase probe lengths.
Performance degrades as the table becomes crowded.
Deletion requires tombstones or another careful strategy.
The table cannot contain more live entries than its capacity.
Resizing requires rehashing existing entries.
A poor hash function can cause many collisions and long probe sequences.

Practical Example: Tracking Unique IDs

Imagine a system that needs to maintain a collection of numeric identifiers. A hash table using linear probing can calculate an initial position from each identifier and move forward when a collision occurs.

IDs:

101
108
115

Table size = 7

101 % 7 = 3
108 % 7 = 3
115 % 7 = 3

Storage:

Index 3 → 101
Index 4 → 108
Index 5 → 115

This example shows how several keys with the same initial hash position can occupy consecutive positions through linear probing.

Common Mistakes in Linear Probing

1. Forgetting Wraparound

The probe sequence must normally wrap from the last index back to zero.

index = (index + 1) % tableSize

2. Stopping at an Occupied Slot

An occupied position may contain a different key. The search must continue according to the probe sequence.

3. Treating Tombstones as Empty

A tombstone represents a previously occupied position. Searches generally need to continue through it.

4. Ignoring a Full Table

A loop that probes forever is a serious implementation bug. The algorithm should stop after examining the table's capacity and handle the full-table condition.

5. Ignoring Clustering

Linear probing is particularly sensitive to primary clustering. A good hash function and appropriate resizing policy are important for maintaining useful performance.

6. Assuming Hash Values Are Unique

Different keys can map to the same initial position. Collision resolution is a normal requirement of a hash table.

Linear Probing in Interviews

Linear probing is a common data structures interview topic because it demonstrates how an open-addressed hash table behaves internally.

Important concepts to understand include:

Hash collisions.
Open addressing.
The linear probing formula.
Insertion after collisions.
Searching through a probe sequence.
Tombstones and deletion.
Primary clustering.
Load factor.
Resizing and rehashing.
Average-case and worst-case complexity.
Linear probing versus separate chaining.

Key Takeaways

Linear probing is an open-addressing collision-resolution technique.
When a collision occurs, the algorithm checks consecutive table positions.
The basic probe formula is (index + attempt) % tableSize.
Linear probing stores entries directly inside the hash table.
Searching follows the same probe sequence used during insertion.
Deletion commonly requires a tombstone so that search sequences remain valid.
Linear probing can suffer from primary clustering.
High load factors generally increase probe lengths.
Resizing requires existing entries to be rehashed.
With suitable hashing and load management, operations are commonly O(1) expected.
In the worst case, search, insertion, or deletion can require O(n) work.

Topics

Linear Probing in Hash Tables