Hash Table

data-structures algorithms

Definition

Hash Table

A hash table (or hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index (or hash code) into an array of buckets or slots, from which the desired value can be found.

Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ some form of collision resolution.

Collision Resolution

Separate Chaining

In this implementation, each cell of the array points to a singly linked list (or other dynamic collection) of records that have the same hash function value.

Open Addressing

In open addressing, all entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found.

Linear Probing

The interval between probes is fixed—often at 1.

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

Primary Clustering

Linear probing is subject to primary clustering, where long runs of occupied slots build up, increasing the average search time.

Quadratic Probing

The interval between probes is increased by adding the successive outputs of a quadratic polynomial to the starting value given by the original hash.

$$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.

Secondary Clustering

Primary clustering is mitigated, but another phenomenon, secondary clustering, could occur (where keys that hash to the same initial position follow the same probe sequence).

Double Hashing

The interval between probes is computed by a second hash function.

$$h(k,i)=(h\ast 1(k)+ih\ast 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$. Usually,$m$ is chosen as a prime number, and $h_2(k)$ is chosen independently of $h_1(k)$.

Brent’s Improvement

Idea: Whenever a key $k$ is inserted at a probed slot $j$ with $k^{\prime }=T[j].key$(already occupied), check if moving $k^{\prime }$ to its next position in its own probe sequence is more beneficial than continuing to probe for $k$.

Specifically, 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_1$ is occupied but $j_2$ is free, then move $k^{\prime }$ to $j_2$ to free the position $j$ for $k$.

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

 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"

Complexity

The following table outlines the time complexity (assuming a good hash function and uniform hashing):

Operation	Average Case	Worst Case
Search	$O(1)$	$O(n)$
Insertion	$O(1)$	$O(n)$
Deletion	$O(1)$	$O(n)$