🔷 QUADRATIC PROBING VISUALIZER

```

🔷 QUADRATIC PROBING VISUALIZER

Hashing • Collision Resolution • Quadratic Probing • Animation

```

```

📥 Hash Table Configuration

Table Size Value

```

```

🗂️ Hash Table

🔵 Current Probe

🟡 Collision

🟢 Found / Inserted

🔴 Deleted

```

```

📈 Live Statistics

Operation -

Hash Index -

Current Index -

Collisions 0

Probes 0

Enter a value and select an operation.

```

```

📝 Step-by-Step Explanation

1

Quadratic Probing resolves a collision by checking positions using the square of the probe number.

```

```

🧮 Quadratic Probing Formula

First calculate:
h(k) = k mod m

If collision occurs:
h<sub>i</sub>(k) = (h(k) + i²) mod m

Probe sequence:
h(k), h(k)+1², h(k)+2², h(k)+3², ...

where
k = key    m = table size    i = probe number

```

```

🔢 Complete Mathematical Example

Table Size = 10

Insert KEY = 25
h(25) = 25 mod 10
= 5

Therefore, try Index 5.

Suppose Index 5 is occupied.
Collision!

Probe 1:
(5 + 1²) mod 10 = 6

If Index 6 is occupied:
Probe 2:
(5 + 2²) mod 10 = 9

If Index 9 is occupied:
Probe 3:
(5 + 3²) mod 10 = 14 mod 10 = 4

So the probe sequence is:
5 → 6 → 9 → 4

```

```

💡 How Quadratic Probing Works

1

Calculate the initial hash position using h(k) = k mod m.

2

Check whether the calculated position is empty.

3

If it is occupied, a collision occurs.

4

Instead of checking the immediate next position, calculate the next position using i².

5

Continue with i = 1, 2, 3, 4... until an available position is found.

6

Insert the key into the first suitable position.

```

```

⚔️ Linear vs Quadratic Probing

Linear Probing
h<sub>i</sub>(k) = (h(k) + i) mod m

Checks positions:
5 → 6 → 7 → 8 → 9

---

Quadratic Probing
h<sub>i</sub>(k) = (h(k) + i²) mod m

Checks positions:
5 → 6 → 9 → 4 → ...

Quadratic probing spreads the probes farther apart and helps reduce primary clustering.

```

```

⚖️ Advantages & Disadvantages

+

Advantages
• Reduces primary clustering compared with linear probing.
• Does not require linked lists.
• Uses the same hash table structure.
• Generally provides efficient average-case operations when the load factor is controlled.

−

Disadvantages
• Secondary clustering can still occur.
• The probe sequence depends on the table size.
• Choosing a suitable table size is important.
• Performance decreases when the table becomes highly full.

```

```

⏱️ Complexity

Average Search O(1)

Average Insert O(1)

Worst Case O(n)

```

```

B.K. PAUL

Bhairab Ganguly College

Data Structures • Hashing • Quadratic Probing

```