hash table

A data structure that stores key-value pairs in an array and uses a hash of each key to jump almost directly to its slot.

In more detail

Lookup, insert and delete are O(1) on average, because the hash tells you where to look instead of searching. Two keys can land in the same slot, a collision, which is handled by chaining or open addressing. A hash table has no useful order, so it cannot answer range questions such as "all keys between 10 and 20".

Related terms

Taught in

References