Quadratic Probing Collision Technique

Quadratic probing is a collision resolution technique used in open addressing for hash tables.

It is an improvement over linear probing that helps reduce the issue of primary clustering by using a quadratic function to determine the probe sequence.

How Quadratic Probing Works

Hash Function

A hash function h(k) maps a key k to an index in the hash table.

index = h(k) mod  m

where m is the size of the hash table.

Collision Resolution

If a collision occurs (the calculated slot is occupied), quadratic probing uses a quadratic function to find the next available slot.

The sequence of probes is determined by.

index = ( h (k) + c1​ * i + c2 ​* i² ) mod m

Here,

• i = 0, 1, 2,… represents the probe number.
• c1​ and c2​ are constants (typically c1=0 and c2=1 are used for simplicity).
• The probing continues until an empty slot is found or the entire table is searched.

Features of Quadratic Probing

Reduction of Primary Clustering

Keys with the same initial hash index follow different probing sequences, reducing clustering.

Secondary Clustering

Quadratic probing still suffers from secondary clustering, where keys that hash to the same index follow the same probing sequence.

Table Size

To ensure that quadratic probing finds an empty slot, m (the table size) is typically chosen to be a prime number.

Steps for Quadratic Probing

Insert Operation

• Compute the hash index using h(k).
• If the slot is empty, insert the key.
• If not, use the quadratic probe sequence until an empty slot is found.

Search Operation

• Compute the hash index using h(k).
• If the slot contains the key, return its position.
• If not, follow the same quadratic probe sequence until:
  • The key is found, or
  • An empty slot is encountered (indicating the key is not in the table).

Delete Operation

• Mark the slot as "deleted" (special marker) rather than clearing it, to preserve the search chain.

Example of Quadratic Probing

Hash table size m=7, hash function h(k)=k mod  7 and keys 50,700,76,85,92,73.

Solution:

50: h(50) = 50 mod  7 = 1 → Insert at index 1.

700: h(700) = 700 mod  7 = 0 → Insert at index 0.

76: h(76) = 76 mod  7 = 6 → Insert at index 6.

85: h(85) =85 mod  7 = 1 → Collision, Probe (1+1²) mod  7 = 2 mod 7 = 2 → Insert at index 2.

92: h(92) = 92 mod  7 = 1 → Collision, Probe (1+1²) mod  7 = 2 mod 7 = 2 → Collision, Probe (1+2²) mod  7 = 5 mod 7 = 5 → Insert at index 5.

73: h(73) =73 mod  7 = 3 → Insert at index 3.

Resulting Table:

Advantages of Quadratic Probing

Reduction of Primary Clustering

Keys that hash to the same region are dispersed more evenly compared to linear probing.

Better Utilization

Fewer probe attempts are required on average compared to linear probing.

Disadvantages of Quadratic Probing

Secondary Clustering

Keys that hash to the same index follow the same probing sequence.

Table Size Limitation

To ensure that all slots can be visited, the table size mmm must be a prime number or a power of 2.

Increased Complexity

The calculation of i² in the probe sequence is more computationally expensive than linear probing.

Numerical Question for Quadratic Probing

1. Insert the following keys into a hash table of size 10 using quadratic probing 45, 25, 35, 15, 55
   1. Use the hash function: h(key) = key % 10
   2. Show the status of the hash table after each insertion.
2. Given the following keys: 17, 29, 41, 55, 68
   1. Use a hash table of size 11
   2. Hash function: h(key) = key % 11
   3. Use quadratic probing to resolve collisions
   4. Show final hash table and explain steps.
3. A hash table has size 13 and uses quadratic probing. Insert the following keys: 18, 41, 22, 44, 59, 32
   1. Use hash function: h(key) = key % 13
   2. What index does each key go into?
   3. Are there any keys that cannot be inserted if the table is half full? Why?