Hashing

Overview

A hash table T[0:m-1] uses a hash function to map a universe of keys into slots of the hash table. It can be seen as a generalization of direct addressing (which has "hash function" $h(k)=k$).

Load Factor

Consider hash table $T$ with $m$ slots that stores $n$ entries. Then the load factor $\alpha$ for $T$ is defined to be $n/m$, i.e. the average number of entries that map to the same slot.

Static Hashing

Static hashing refers to providing a single fixed hash function intended to work well on any data. Generally speaking, this should not be favored over random hashing.

Division Method

The division method for creating hash functions maps a key $k$ into one of $m$ slots by taking the remainder of $k$ divided by $m$. That is, $h(k)=kmodm$.

Multiplication Method

The multiplication method for creating hash functions first multiples a key $k$ by a constant $0<A<1$ and extracts the fractional part of $kA$. Then it multiplies this value by $m$ and takes the floor of the result. That is, $h(k)=\lfloor m(kAmod1)\rfloor$.

Random Hashing

Random hashing refers to choosing a hash function randomly in a way that is independent of the keys being stored.

Universal Hashing

Let $\mathcal{H}$ be a finite family of hash functions that map a given universe $U$ of keys into range $\{0,1,\dots ,m-1\}$. Such a family is said to be universal if for all distinct $x,y\in U$,