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:

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.

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:

Their positions:

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

Average constant time holds when:

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

Space

The table size is typically chosen so that:

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

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

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
}