# Quadratic Probing Search

# Quadratic Probing Search

Quadratic probing improves upon linear probing by spreading out probe sequences. Instead of stepping one slot at a time, it uses a quadratic function of the probe number. This reduces primary clustering and improves distribution under moderate load.

You search by following the same quadratic probe sequence used during insertion.

## Problem

Given a hash table using quadratic probing and a key $k$, return the associated value if it exists.

## Model

* Table $T$ has size $m$
* Hash function $h(k)$
* Probe sequence:

$$
i_t = \big(h(k) + c_1 t + c_2 t^2\big) \bmod m
$$

for constants $c_1, c_2$ and $t = 0, 1, 2, \dots$

## Algorithm

```text id="z7m2pl"
quadratic_probing_search(T, k):
    i0 = h(k)
    for t from 0 to m - 1:
        i = (i0 + c1*t + c2*t*t) mod m
        if T[i] is empty:
            return NOT_FOUND
        if T[i].key == k:
            return T[i].value
    return NOT_FOUND
```

## Example

Let:

* $m = 7$
* $h(k) = k \bmod 7$
* $c_1 = 0$, $c_2 = 1$

Insert keys:

$$
[10, 17, 24]
$$

All hash to index 3. Probe sequence:

* $t=0$: index 3 → 10
* $t=1$: index 4 → 17
* $t=2$: index 0 → 24

Search for $k = 24$:

* check index 3 → no
* check index 4 → no
* check index 0 → match

## Correctness

Each key follows a deterministic probe sequence derived from its hash. Lookup uses the same sequence. If the key exists, it must appear at one of these probe positions.

If an empty slot appears before a match, the key was never inserted, so it does not exist.

## Complexity

Let $\alpha = n/m$.

| case    | time   |
| ------- | ------ |
| average | $O(1)$ |
| worst   | $O(n)$ |

Quadratic probing reduces primary clustering compared to linear probing but still suffers from secondary clustering.

## Space

$$
O(m)
$$

## When to Use

Quadratic probing is appropriate when:

* clustering from linear probing becomes a problem
* memory locality is still desired
* load factor remains moderate

It requires careful choice of $m$, $c_1$, and $c_2$ to ensure full table coverage.

## Implementation

```python id="k1v9op"
class HashTable:
    def __init__(self, m=8):
        self.m = m
        self.table = [None] * m

    def _hash(self, key):
        return hash(key) % self.m

    def get(self, key):
        i0 = self._hash(key)

        for t in range(self.m):
            i = (i0 + t*t) % self.m
            if self.table[i] is None:
                return None
            k, v = self.table[i]
            if k == key:
                return v

        return None
```

```go id="m4x8qe"
type Entry[K comparable, V any] struct {
	Key   K
	Value V
	Used  bool
}

type HashTable[K comparable, V any] struct {
	Table []Entry[K, V]
	M     int
}

func (h *HashTable[K, V]) hash(key K) int {
	return int(uintptr(any(key))) % h.M
}

func (h *HashTable[K, V]) Get(key K) (V, bool) {
	i0 := h.hash(key)

	for t := 0; t < h.M; t++ {
		i := (i0 + t*t) % h.M
		if !h.Table[i].Used {
			break
		}
		if h.Table[i].Key == key {
			return h.Table[i].Value, true
		}
	}

	var zero V
	return zero, false
}
```