A hash table is a data structure that maps a given key to a specific value. A hash table uses a hash function given a key to compute an index into either a regular array or an array of buckets. Hash tables provide incredibly quick accesses () at the cost of increased memory usage.

Collisions

A hash table collision is a collision in the hash of a key in a hash table.

Handling Collisions

• Open Addressing
• Separate Chaining

Load Factor

The load factor of a hash table refers to how "full" the table is and is calculated as

where is the number of elements in the hash table, and is the number of available slots for data.