# Perfect Hashing Lookup

# Perfect Hashing Lookup

Perfect hashing uses a hash function that maps a fixed set of keys to distinct table positions. Because no two stored keys collide, lookup checks one computed position and compares the stored key with the query key.

This method is useful for static dictionaries. The table is built once, then used for many fast lookups.

## Problem

Given a static set of keys $S$ and a query key $k$, determine whether $k$ exists in $S$ and return its associated value if present.

## Model

A perfect hash function for $S$ is a function $h$ such that for any two distinct keys $a, b \in S$:

$$
h(a) \neq h(b)
$$

The table stores each key $k \in S$ at position:

$$
T[h(k)]
$$

## Algorithm

```text id="v6ijcv"
perfect_hash_lookup(T, k):
    i = h(k)

    if T[i] is occupied and T[i].key == k:
        return T[i].value

    return NOT_FOUND
```

## Example

Suppose the stored keys are:

$$
S = {12, 25, 31, 44}
$$

A perfect hash function maps them as follows:

| key | hash index |
| --: | ---------: |
|  12 |          0 |
|  25 |          3 |
|  31 |          1 |
|  44 |          2 |

Lookup for $31$:

* compute $h(31) = 1$
* check $T[1]$
* stored key is $31$
* return its value

Lookup for $18$:

* compute $h(18)$
* check that position
* if the stored key differs from $18$, return not found

The final key comparison is still required because a perfect hash function only guarantees collision freedom for the stored set $S$, not for every possible query key.

## Correctness

For every stored key $k \in S$, the perfect hash function places it at exactly one unique position $T[h(k)]$. Therefore, if the query key exists, lookup will compute the same index and find it there.

If the computed slot is empty or contains a different key, then the query key is not in the stored set.

## Complexity

| case         | time   |
| ------------ | ------ |
| lookup       | $O(1)$ |
| worst lookup | $O(1)$ |

The construction cost depends on the perfect hashing scheme. Lookup itself performs a constant number of hash computations and table accesses.

## Space

$$
O(m)
$$

For ordinary perfect hashing, $m$ may be larger than $n$. Minimal perfect hashing improves this by using exactly $n$ slots.

## When to Use

Perfect hashing is appropriate when:

* the key set is fixed
* lookups are frequent
* insertions and deletions are rare or absent
* worst case constant lookup is desired

It is less suitable for dynamic tables because changing the key set may require rebuilding the hash function.

## Implementation

```python id="effyrn"
class PerfectHashTable:
    def __init__(self, table, hash_func):
        self.table = table
        self.hash_func = hash_func

    def get(self, key):
        i = self.hash_func(key)

        if i < 0 or i >= len(self.table):
            return None

        entry = self.table[i]
        if entry is None:
            return None

        k, v = entry
        if k == key:
            return v

        return None
```

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

type PerfectHashTable[K comparable, V any] struct {
	Table []Entry[K, V]
	Hash  func(K) int
}

func (h *PerfectHashTable[K, V]) Get(key K) (V, bool) {
	i := h.Hash(key)

	if i < 0 || i >= len(h.Table) {
		var zero V
		return zero, false
	}

	e := h.Table[i]
	if e.Used && e.Key == key {
		return e.Value, true
	}

	var zero V
	return zero, false
}
```