A hash table is a table of key, value pairs. Basic operations include return the associated value for a specified key, insert a key and delete a key. The built in [[dictionary]] in [[Python]] is an example of a hash table. Hash tables rely on a [[hash function]] to allocate keys to slots. To grow a hash table is called **rehashing**. The complexity of rehashing is $O(m + n)$ where $m$ is the number of slots and $n$ is the number of elements. Typically, rehash to a new hash table of size $m = 2n$.