# Linear Probing Search

# Linear Probing Search

Linear probing resolves collisions in an open addressing hash table by scanning forward one slot at a time. All keys are stored directly inside the table, and probing follows a contiguous sequence.

You search by computing the hash index and walking forward until you either find the key or reach an empty slot.

## Problem

Given a hash table using linear 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 = (h(k) + t) \bmod m
$$

for $t = 0, 1, 2, \dots$

## Algorithm

```text id="z1c9pq"
linear_probing_search(T, k):
    i = h(k)
    start = i
    while T[i] is occupied:
        if T[i].key == k:
            return T[i].value
        i = (i + 1) mod m
        if i == start:
            break
    return NOT_FOUND
```

## Example

Let:

* $m = 7$
* $h(k) = k \bmod 7$

Insert:

$$
[10, 17, 24]
$$

All hash to index $3$, so they occupy:

| index | value |
| ----- | ----- |
| 3     | 10    |
| 4     | 17    |
| 5     | 24    |

Search for $k = 24$:

* start at index 3
* check 10, then 17, then 24
* match found

## Correctness

Linear probing guarantees that every key is placed somewhere along its probe sequence. The lookup follows exactly the same sequence, so it will encounter the key if it exists.

An empty slot terminates the search, proving that the key does not exist.

## Complexity

Let $\alpha = n/m$ be the load factor.

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

Performance degrades as $\alpha$ approaches 1 due to clustering.

## Space

$$
O(m)
$$

All elements are stored directly in the table.

## When to Use

Linear probing is appropriate when:

* memory locality is important
* cache performance matters
* implementation simplicity is desired

It performs poorly under high load due to primary clustering.

## Implementation

```python id="n3z1qp"
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):
        i = self._hash(key)
        start = i

        while self.table[i] is not None:
            k, v = self.table[i]
            if k == key:
                return v
            i = (i + 1) % self.m
            if i == start:
                break

        return None
```

```go id="u8k2ds"
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) {
	i := h.hash(key)
	start := i

	for h.Table[i].Used {
		if h.Table[i].Key == key {
			return h.Table[i].Value, true
		}
		i = (i + 1) % h.M
		if i == start {
			break
		}
	}

	var zero V
	return zero, false
}
```