Hash Function

data-structures

Definition

Hash Function

A hash function $h:\mathcal{K}\to \mathbb{N}$ is a deterministic function used in computer systems to compute a position in a data structure from a key without the need to search.

Note that $h$ does not need to be surjective, see quality.

Quality

An hash function is called optimal if it has no collisions. However, since resources are limited, this is not always feasible for general domains.

Methods

Modulo Method

Let $m$ be the size of a data structure, e.g. an array and $k\in \mathbb{N}$ be a key, then a hash function ca be defined as:

$$h(k)=k\mathrm{mod}m$$

Multiplication Method

Let $k\in \mathbb{N}$ be a key and $A$ be an irrational number, then a hash function can be defined as:

$$h(k)=\lfloor m(\underset{\in [0,1)}{\underbrace{k\cdot A-\lfloor k\cdot A\rfloor }})\rfloor$$

However, a more optimal hash distribution can be achieved using the reciprocal of the golden ratio:

$$A={\phi }^{-1}=\frac{\sqrt{5}-1}{2}=0.6180339887\dots$$

Collision

Let $k_1\ne k_2$ be two different keys. Two keys are called colliding if:

$$h(k_1))=h(k_2)$$

meaning that both keys have the same hash values and thus same positions in e.g. an array.

This must be addressed by the data structure. For instance, an hash table achieves this by storing a singly linked list at each position of the array (separate chaining), meaning multiple values can be stored at each position.

See probing.