Hash Tables

Basic idea

Map keys to slots via a hash function. With a good hash, lookups average $O(1)$ . Collision handling (chaining, open addressing) and load factor determine performance.

Key formulas

Load factor: $\lambda = n/m$
Expected chain length (chaining): $\lambda$
Open addressing probe count (uniform hashing): $\approx \dfrac{1}{1-\lambda}$ (successful), $\dfrac{1}{(1-\lambda)^2}$ (unsuccessful)

Poisson distribution

Consider a hash table with m slots and n elements in it. Denote the load factor by λ=(n/m). The probability that a given slot has k elements is given by

$P(k; \lambda) = \frac{e^{-\lambda} \lambda^k}{k!}$

Hash Tables

Basic idea

Key formulas

Poisson distribution

Siblings