Hash Index Probe

Hash index probe retrieves records from a table using a hash index. The index maps key values to locations of rows, enabling fast equality lookups.

You use it in databases and storage systems when queries involve exact key matches.

Problem

Given a table with a hash index on attribute $k$, and a query value $x$, retrieve all rows such that:

Model

A hash index consists of:

• a hash function $h(k)$
• an index table mapping hash buckets to row references

The index stores:

To query a key $x$, compute:

Then retrieve all row identifiers stored in bucket $I[i]$.

Algorithm

hash_index_probe(I, x):
    i = h(x)
    bucket = I[i]

    result = empty list
    for each rid in bucket:
        row = fetch(rid)
        if row.key == x:
            append row to result

    return result

The equality check is required because different keys may hash to the same bucket.

Example

Table:

Hash index on name:

Query:

Steps:

• compute $h("Ada")$
• retrieve bucket → [1, 4]
• fetch rows 1 and 4
• both match

Result:

Correctness

Every row with key value $k$ is inserted into the bucket corresponding to $h(k)$. Therefore, all rows with $k = x$ appear in bucket $h(x)$.

The probe scans that bucket and filters rows by exact comparison, ensuring that all matching rows are returned and no incorrect rows are included.

Complexity

Let $b$ be the bucket size.

Expected constant time when the hash function distributes keys uniformly and buckets remain small.

Worst case:

when all keys collide into one bucket.

Space

The index stores references to all rows.

When to Use

Hash index probe is appropriate when:

• queries use equality conditions
• fast point lookups are required
• data is not sorted
• range queries are not needed

It is widely used in database engines, key value stores, and indexing systems.

Implementation

from collections import defaultdict

class HashIndex:
    def __init__(self):
        self.index = defaultdict(list)
        self.rows = {}

    def insert(self, rid, row, key):
        self.rows[rid] = row
        self.index[row[key]].append(rid)

    def probe(self, key, value):
        result = []
        for rid in self.index.get(value, []):
            row = self.rows[rid]
            if row[key] == value:
                result.append(row)
        return result

type Row map[string]string

type HashIndex struct {
	Index map[string][]int
	Rows  map[int]Row
}

func (h *HashIndex) Insert(rid int, row Row, key string) {
	if h.Index == nil {
		h.Index = make(map[string][]int)
		h.Rows = make(map[int]Row)
	}
	h.Rows[rid] = row
	v := row[key]
	h.Index[v] = append(h.Index[v], rid)
}

func (h *HashIndex) Probe(key string, value string) []Row {
	var result []Row

	for _, rid := range h.Index[value] {
		row := h.Rows[rid]
		if row[key] == value {
			result = append(result, row)
		}
	}

	return result
}