AI Glossary / Graphs and symbolic AI / Intermediate
Quadratic probing
Definition
Quadratic probing is a collision-resolution method for an open-addressed hash table. When a key's initial slot is occupied by another key, the table checks alternative slots using a quadratic function of the probe number. A common version examines (h(key) + i²) modulo the table size for i = 0, 1, 2, and so on.
What it means
A hash function maps many possible keys into a limited number of storage slots, so different keys can share the same home slot. Open addressing stores the records within the table itself and searches for an alternative slot when a collision occurs.
Quadratic probing changes the offsets from the home slot: 0, 1, 4, 9, 16, and so forth in the simple square-offset version. This avoids the consecutive-slot pattern of linear probing, but keys with the same home slot still follow the same sequence. Crucially, a quadratic sequence may not visit every table slot. The probe formula and table size must be designed together.
How it works
To insert a key, calculate its home slot and follow its probe sequence until finding the key already present or a usable slot, according to the table's duplicate and deletion rules. Lookup follows the same sequence and compares stored keys, not just their hash values.
For the square-offset version with a prime table size, at least half the slots are reached, giving an empty-slot guarantee when the table is less than half full under the usual insertion setting. Other formulas have different properties. For example, triangular offsets i(i + 1)/2 work with power-of-two sizes to visit every slot. An implementation must bound probing and handle resizing rather than loop forever.
Three practical examples
- A teaching hash table can store document identifiers while demonstrating how collisions affect insertion and lookup.
- An in-memory symbol table prototype can compare quadratic probing with linear probing under the same key workload.
- A data-structure test suite can exercise cases where many distinct keys deliberately share one home slot.
Think of it this way
Think of checking numbered lockers using an agreed sequence of jumps when the preferred locker is occupied. To find the item later, you repeat the same sequence. The analogy is limited because the jumps wrap around mathematically, and some jump patterns revisit only a subset of lockers even while others remain empty.
Worked example
Consider an invented table with 11 slots numbered 0 through 10. Use h(k) = k modulo 11 and square offsets i². Insert keys 14, 25, 36, and 47, all of which have home slot 3. Assume the table starts empty and contains no deletions.
Key 14 occupies slot 3. Key 25 finds 3 occupied and uses (3 + 1) modulo 11 = 4. Key 36 checks 3, 4, and then (3 + 4) modulo 11 = 7. Key 47 checks those slots and then (3 + 9) modulo 11 = 1. Looking up 47 must therefore inspect the sequence 3, 4, 7, 1 and compare keys at each occupied slot.
The full set of slots reached from home 3 is {3, 4, 7, 1, 8, 6}; subsequent square offsets repeat these locations. If all six are occupied, an additional key with that home slot cannot find an empty position using this sequence, despite five unused table slots elsewhere.
For contrast, square offsets modulo 8 reach only {0, 1, 4} from home 0. A power-of-two table does not by itself make this particular formula cover the table.
Illustrative case study
Fictional case: Fern Index implements a small lookup table and tests it only with well-spread identifiers. A stress test sends several distinct identifiers to the same home slot. The insertion routine keeps revisiting occupied locations instead of recognizing that its probe sequence is exhausted.
The team adds a bounded probing policy and resizes according to a documented formula-and-capacity rule. It also includes collision-heavy tests. This fictional case illustrates a structural correctness issue; it does not report real system throughput or claim that quadratic probing is the best table design for every workload.
Common misconceptions and mistakes
Do not assume “quadratic” means quadratic-time lookup. The name describes the offset formula, while performance depends on load, hashing, and implementation. Do not add each square offset to the previous slot when the chosen formula defines offsets from the original home slot; those are different sequences.
Prime size does not guarantee that square probing visits every slot. Deletion also requires care: simply marking an occupied slot as never used can make later lookups stop before a displaced key. Tombstone or rebuilding policies must preserve search paths. Finally, equal hash values do not make keys equal; the table still needs key comparison.
Business use
Quadratic probing is relevant when evaluating the design of a custom in-memory index or understanding why a table's performance changes as it fills. It offers a compact collision-handling mechanism, but its practical value must be judged with the actual key distribution and deletion workload.
For a prototype, record the exact probe formula, capacity rule, maximum probe count, and resizing behavior. Test lookup after deletion and after repeated collisions. Measure unsuccessful searches as well as successful ones, since they can expose long probe chains. Avoid transferring a load-factor guarantee from one quadratic variant to another without checking its conditions.
People also ask
Does quadratic probing eliminate collisions?
No. It supplies a sequence of alternative locations after a collision.
Can insertion fail while empty slots remain?
Yes. The probe sequence may cover only part of the table.
Must every quadratic-probing table use a prime size?
No. Requirements depend on the offset formula; some combinations, such as triangular offsets with power-of-two capacities, have different coverage guarantees.
Check your understanding
In the 11-slot example, why is the fourth key stored at slot 1 rather than slot 9?
Answer: Its fourth probe uses i = 3 and adds 3² = 9 to the home slot 3. Reducing 12 modulo 11 gives slot 1. The offset is measured from the home slot, not used as the slot number itself.
Related terms
- Linear probing
- Double hashing
- Hash table
- open addressing
- collision
- load factor
- tombstone
- rehashing
- secondary clustering
Learn next
Learn double hashing and deletion in open-addressed tables next. Trace a lookup for 47 after removing 25 from the worked table. Explain why a deletion marker must allow the search to continue through slot 4 rather than incorrectly reporting that 47 is absent.
More in Graphs and symbolic AI
- Pure Monte Carlo search - Pure Monte Carlo search evaluates candidate moves by running simulated continuations, or playouts, and comparing their average outcomes.
- Pure strategy - A pure strategy is a complete, deterministic plan specifying which action a player will choose at each of that player's decision situations in a game.
- Pure symbol - A pure symbol is a propositional variable that appears with only one polarity in the relevant clauses of a satisfiability problem: always unnegated or...
- Quadratic programming - Quadratic programming is optimization with a quadratic objective function and linear equality or inequality constraints.
- Qualification problem - The qualification problem is the difficulty of specifying all the conditions required for a real-world action to produce its intended result.
- Qualitative physics - Qualitative physics is an area of AI concerned with representing and reasoning about physical systems using meaningful qualitative distinctions, such as...
Sources
Clifford Shaffer, Virginia Tech, Hashing Tutorial, Quadratic Probing: https://research.cs.vt.edu/AVresearch/hashing/quadratic.php Harvey Mudd College, CS70, Quadratic Probing: https://www.cs.hmc.edu/cs70/lessons/week12/lesson2/quadraticprobing/
Previous: Quadratic function Next: Quadratic programming