Course contentsShow
← Computer Science
Lesson 423 of 2,87210. Hash TablesFree lesson

Linear Probing

Using linear probing to resolve collisions by checking consecutive slots sequentially.

Linear Probing

You'll learn how linear probing resolves hash table collisions by checking the next available slot in sequence.

The Core Idea

When two keys hash to the same index (a collision), linear probing handles it by simply looking at the next slot in the array. If that slot is occupied too, check the one after that, and so on—moving consecutively through the table until you find an empty spot.

Think of it like parking: if your preferred parking space is taken, you drive to the next one, then the next, until you find an empty spot. You're "probing" linearly through the lot.

How It Works

When inserting a key:

  1. Hash the key to get an index
  2. If that slot is empty, place the key there
  3. If occupied (collision!), check index + 1
  4. Still occupied? Try index + 2, then index + 3, and so on
  5. Wrap around to the beginning if you reach the end of the array

When searching:

  • Hash the key and start at that index
  • If the slot contains your key, found it!
  • If empty, the key doesn't exist
  • If it contains a different key, keep probing forward

Why "Linear"?

The probe sequence follows a simple arithmetic pattern: index, index + 1, index + 2, etc. Each step moves exactly one position forward—hence "linear."

This is the simplest form of open addressing you learned about previously.

Key Takeaway: Linear probing resolves collisions by checking consecutive slots one-by-one until finding an empty space, making it the most straightforward open addressing technique but prone to clustering issues.