Hash table

Definition

A data structure used to implement a Map ADT (dictionary) (keys to values). It uses a hash function to map keys to corresponding indices in an Array

Mathematical definition

A hash table for a given key type $K$ consists of:

• Hash function $h:K\to [0,N-1]$
• An array $A$ (aka table) of size $N$ Ideally, an item $(x,o)$ will therefore be stored at $A[h(x)]$

Hash function

A hash function should:

• Give the same result for any particular key
• Be efficient to compute - $O(1)$

Designing hash functions

Usually, an efficient hash function is composed of two functions (noting that keys can be of different types):

• Hash code: $h_1:\text{keys}\to \text{integers}$
  • Disperses the keys in an approximately random way to integers, attempting to avoid collisions
• Compression function: $h_2:\text{integers}\to [0,N-1]$
  • Compresses back to ‘allowed range’ for the final array index

Thus the final function would be in the form: $h(x)=h_2(h_1(x))$

Approaches

There are two general approaches that one can take:

• View the key $k$ as a tuple of integers $(x_1,x_2,...,x_d)$ with each being an integer in the range $[0,M-1]$ for some $M$
• View the key $k$ as (possibly very large) nonnegative integer

Performance

Algorithm	Average	Worst case
Space	Θ(n)	O(n)
Search get	Θ(1)	O(n)
Insert put	Θ(1)	O(n)
Delete remove	Θ(1)	O(n)

---

• task Complete section on designing hash functions and collisions