A hash table is a data structure that stores an arbitrary number of items, mapping keys to values, and uses a hash function to compute an index. The hash table relates the hashed keys to an array of buckets where the associated value can be found. When looking up a value, the provided key is hashed and the resulting hash is used to retrieve the corresponding value.
Hash tables are implemented in many different programming languages such as Java (as a
HashTable or Python (as a dictionary). Hash table implementations typically allow the modification, insertion, and deletion of the contained key-value pairs.
On average, hash tables prove to be more efficient than other table lookup structures. Because of this, they are widely used for things such as dictionaries, database indexing, and caching.