Hashing Fundamentals #2: Open Addressing — Linear Probing

Photo by Anoushka Puri on Unsplash

Linear probing is one of the simplest ways to implement Open Addressing, a method to resolve hashing collisions. The main idea of linear probing is that we perform a linear search to locate the next available slot in the hash table when a collision happens.

Insert:

Steps of inserting a key:

• Step 1: Compute the slot index by using the hash function on the key
• Step 2: If the slot is empty, insert the value into that slot. Otherwise, linearly search for the next available slot. The search ends when the entire table has been traversed.

Linear probing insertion illustration

Search:

Steps of searching for a key:

• Step 1: Locate the slot index by using hash function on the key
• Step 2: Compare the value at the slot index with the key. If matched, return the key. If not match, run a loop through the hash table, starting from the slot index to find the key. The loop ends when an empty slot is encountered, or when traversed the entire table.

Delete: