[Data Structure] Hash Table - 2 | Linear Probing & Quadratic Probing

Linear Probing

 

A hash table with linear probing handles a collision by starting at the key's mapped bucket, and then linearly searches subsequent buckets until an empty bucket is found. 

Before Insert

 

After Insert

Item 124 should be inserted into bucket 4 since 124 % 10 = 4, but bucket 4 is already occupied, so it searched for next null (empty) bucket appearing linearly starting from the original bucket. 

Since bucket 5 was empty, item 124 is inserted into bucket 5. 

 

When searching for an item, it starts from the mapped bucket. 

Then it linearly searches for the item until it finds the item and returns it, or encounters an empty (null) bucket and returns null.

 

 

Empty Bucket Types

Actually, linear probing distinguishes two types of empty buckets.

An empty-since-start bucket has been empty since the hash table was created.

An empty-after-removal bucket had an item removed that caused the bucket to now be empty.

The distinction will be important during searches, since searching only stops for empty-since-start, not for empty-after-removal.

 

---

Quadratic Probing

 

A hash table with quadratic probing handles a collision by starting at the key's mapped bucket, and then quadratically searches subsequent buckets until an empty bucket is found. 

 

If an item's mapped bucket is H, the formula (H + cl * 𝑖 + c2 * 𝑖²) mod (tablesize) is used to determine the item's index in the hash table. 

c1 and c2 are progammer-defined constants for quadratic probing.

Inserting a key uses the formula, starting with 𝑖 = 0, to repeatedly search the hash table until an empty bucket is found. 

Each time an empty bucket is not found, 𝑖 is incremented by 1. 

Iterating through sequential 𝑖 values to obtain the desired table index is called the probing sequence. 

 

This is an example of inserting 3 items into a hash table with quadratic probing, using c1 = c2 = 1. 

quadratic probing with c1 = c2 = 1