Hash Table

data-structures

Definition

Hash Table

A hash table $T$ is an array of length $m$ where each element $T[i]$, $0\le i<m$, is a singly linked list.

Example:

Probing

There are multiple ways to deal with collisions.

Linear Probing

todo

Problem: Primary clustering todo

Quadratic Probing

Let $h^{\prime }:\mathcal{K}\to \{0,1,\dots ,m-1\}$ be a normal hash function. The probing function is then:

$$h(k,i)=(h^{\prime }(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$$

where $c_1,c_2$ are properly chosen constants.

Problem: Primary clustering is mitigated, but another phenomenon, secondary clustering, could occur.

Double Hashing

Let $h_1,h_2:\mathcal{K}\to \{0,1,\dots ,m-1\}$ be two hash functions. The probing function is then:

$$h(k,i)=(h_1(k)+i{h}_2(k))\mathrm{mod}m$$

with $0\le i<m$.

Choice of $h_2(k)$: For all keys $k$, the probing sequence must reach all slots $0,\dots ,m-1$. This means that $h_2(k)\ne 0$ must hold and it must not divide $m$. $m$ should be a prime number, $h_2$, should be chosen independently of $h_1$.

Brent’s Improvement

Idea: Whenever a key $k$ is inserted at a probed slot $j$ with $k^{\prime }=T[j].key$ (already occupied), set:

$$\begin{array}{rl}{j}_1& =(j+h_2(k))\mathrm{mod}m\\ j_2& =(j+h_2(k^{\prime }))\mathrm{mod}m\end{array}$$

If $j$ is occupied but $j_2$ is free, then move $k^{\prime }$ to $j_2$ to free the position $j$ for $k$.

Example:

Benefit: The average-case runtime of a successful search is in worst case $\alpha =1\in \Theta (1)$ .

Algorithm:

def insert_brent(T: HashTable, k: Key) -> None:
	j = h1(k)
	while T[j].status == "used":
		k_prime = T[j].key
		j1 = (j + h2(k)) % m
		j2 = (j + h2(k_prime)) % m
		if T[j1].status != "used" or T[j2].status == "used":
			j = j1
		else:
			T[j] = k
			k = k_prime
			j = j2
	T[j] = k
	T[j].status = "used"