# Hash Table Lookup

# Hash Table Lookup

Hash table lookup retrieves a value associated with a key by computing a hash and using it to index into a table. It provides constant expected time for search under standard assumptions.

You use it when fast membership or key value access is required, especially for repeated queries over large datasets.

## Problem

Given a hash table storing key value pairs and a query key $k$, return the associated value if it exists, otherwise report failure.

## Model

A hash table consists of:

* an array $T$ of size $m$
* a hash function $h: \text{Keys} \to {0, \dots, m-1}$

The index is computed as:

$$
i = h(k)
$$

Collisions occur when multiple keys map to the same index.

## Algorithm

Compute the hash index and probe the table according to the collision resolution strategy.

```text
hash_lookup(T, k):
    i = h(k)
    while T[i] is occupied:
        if T[i].key == k:
            return T[i].value
        i = next_probe(i)
    return NOT_FOUND
```

The function `next_probe` depends on the method:

* separate chaining: follow linked list
* linear probing: $i = (i + 1) \bmod m$
* quadratic probing: $i = (i + c_1 + c_2 t^2) \bmod m$
* double hashing: $i = (i + h_2(k)) \bmod m$

## Example

Let:

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

Insert keys:

$$
[10, 20, 15]
$$

Their positions:

| key | hash | index |
| --- | ---- | ----- |
| 10  | 3    | 3     |
| 20  | 6    | 6     |
| 15  | 1    | 1     |

Lookup $k = 20$:

* compute $h(20) = 6$
* check $T[6]$
* match found

## Correctness

If a key exists in the table, it must appear in the probe sequence defined by the collision strategy starting from $h(k)$. The algorithm follows exactly that sequence, so it finds the key if present.

If it reaches an empty slot that terminates the probe sequence, no such key exists.

## Complexity

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

Average constant time holds when:

* the load factor $\alpha = n/m$ remains bounded
* the hash function distributes keys uniformly

## Space

$$
O(m)
$$

The table size is typically chosen so that:

$$
\alpha = \frac{n}{m} \le 0.7
$$

for open addressing methods.

## When to Use

Hash table lookup is appropriate when:

* fast key based access is required
* order of elements does not matter
* frequent insert and lookup operations occur

It performs poorly when many collisions occur or when ordered traversal is required.

## Implementation

```python
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
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
}
```