Open addressing: linear probing, quadratic probing, double hashing

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Expected keys examined in an unsuccessful chained search? from Lesson 2.2.1
• First-occurrence binary search: what happens on equality? from Lesson 2.1.2
• Average comparisons of linear search (present, uniform)? from Lesson 1.3.1

1 · The Hook

🎣

Chaining needs extra lists. Open addressing stores every key inside the table: if the home slot is taken, try another slot, then another, following a fixed probe sequence. GATE's classic question gives keys and a probing rule and asks where a key ends up. You must trace carefully, slot by slot.

2 · Predict First

🤔

m = 10, h(k) = k mod 10, linear probing (try h, h + 1, h + 2, … mod 10). Insert 43, 165, 62, 123, 142. Where does 142 go?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

43 → 3, 165 → 5, 62 → 2, 123 → 3 taken → 4. 142 → 2 taken, 3 taken, 4 taken, 5 taken, 6.

Probe sequences

For the i-th attempt (i = 0, 1, 2, …):

Insert at the first empty slot. Search follows the same sequence until it finds the key (success) or an empty slot (failure).

Clustering

• Primary clustering (linear probing): occupied runs grow, and any key landing in a run extends it. Long runs → long searches.
• Secondary clustering (quadratic probing): keys with the same home slot follow the same sequence.
• Double hashing avoids both (the step depends on the key). Choose h₂(k) relatively prime to m (e.g. m prime).

Deletion

Simply emptying a slot would break searches that probed past it. Mark it deleted (a tombstone): searches continue past it; inserts may reuse it.

Worked traces (m = 10, h(k) = k mod 10, keys 12, 18, 13, 2, 3, 23, 5, 15)

Linear: 2 → 2, 3, 4; 3 → 3, 4, 5; 23 → 3, 4, 5, 6; 5 → 5, 6, 7; 15 → 5, 6, 7, 8, 9. Quadratic: 2 → 2, 3, 6 (2 + 4); 3 → 3, 4; 23 → 3, 4, 7 (3 + 4); 5 → 5; 15 → 5, 6 (5 + 1), 9 (5 + 4).

Double hashing example

m = 13, h₁(k) = k mod 13, h₂(k) = 7 − (k mod 7). Insert 25, 37, 18, 55, 22, 35, 50, 63: 25 → 12; 37 → 11; 18 → 5; 55 → 3; 22 → 9; 35 → 9, step 7 → 3, → 10; 50 → 11, step 6 → 4; 63 → 11, step 7 → 5, → 12, → 6.

4 · Visual

Linear probing, m = 10: inserting 15 (home slot 5)

slot: 0  1  2   3   4  5  6   7  8   9
      -  -  12  13  2  3  23  5  18  [15]
                       ^  ^   ^  ^   ^
                       5  6   7  8   9     5 probes: a primary cluster from 2 to 8

5 · Worked Examples

Example 1 Easy

m = 11, h(k) = k mod 11, linear probing. Keys 10, 22, 31, 4, 15, 28, 17, 88, 59. Where does 59 go?

Solution

59 mod 11 = 4: slots 4, 5, 6, 7 are taken (4, 15, 28, 17), 8 is free → slot 8 (5 probes).

Example 2 Medium

Same keys with double hashing, h₂(k) = 1 + (k mod 10). Where does 88 go?

Solution

88 mod 11 = 0, taken by 22; step 1 + 8 = 9: slot 9 taken by 31; slot 18 mod 11 = 7.

Example 3 GATE

m = 10, linear probing, h(k) = k mod 10. After inserting 43, 165, 62, 123, 142, how many probes does a search for 172 (absent) make?

Solution

Home slot 2; slots 2, 3, 4, 5, 6 are full, slot 7 empty: 6 probes.

6 · GATE Traps

⚠️

• Count the home slot as probe 1.
• Wrap around with mod m.
• Quadratic probing may fail to find a free slot even when one exists (if m is not prime / load > 1/2).
• An unsuccessful search stops at an empty slot, not at a deleted one.

7 · Memory Hook

🧠

"Linear steps 1, quadratic steps squares, double hashing steps by a second hash."

8 · Connect the Dots

You can place keys with any probing rule. Next: how many probes to expect as the table fills up, and the probabilities behind collisions.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markLinear probing

m = 10, h(k) = k mod 10, linear probing. Insert 43, 165, 62, 123, 142. In which slot is 123?

Numerical answer: ________

Q2NAT2 marksLinear probing trace

m = 10, h(k) = k mod 10, linear probing; keys 12, 18, 13, 2, 3, 23, 5, 15 in that order. How many probes does inserting 15 take?

Numerical answer: ________

Q3NAT2 marksQuadratic probing

m = 10, h(k) = k mod 10, quadratic probing (h + i²); keys 12, 18, 13, 2, 3, 23, 5, 15. In which slot is 23?

Numerical answer: ________

Q4NAT2 marksDouble hashing

m = 13, h₁(k) = k mod 13, h₂(k) = 7 − (k mod 7). After 25, 37, 18, 55, 22, 35, 50, which slot does 63 occupy?

Numerical answer: ________

Q5MCQ1 markClustering

Primary clustering is a problem of:

• (A) double hashing
• (B) binary search
• (C) linear probing
• (D) chaining

10 · Rule Card

• Linear: (h + i) mod m; quadratic: (h + c₁i + c₂i²) mod m; double: (h₁ + i·h₂) mod m.
• Insert at the first empty slot; search until key or empty slot; deletion uses tombstones.
• Linear → primary clustering; quadratic → secondary; double hashing avoids both (h₂ coprime to m).
• Probe count includes the home slot.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

open addressingprobe sequencelinear probingquadratic probingdouble hashingprimary clusteringsecondary clusteringtombstone deletionprobe count

12 · Answer Vault