Hash Table

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.

Implementation

Hash tables are implemented in many different programming languages such as Java (as a HashMap) or JavaScript as a HashTable or Python (as a dictionary). Hash table implementations typically allow the modification, insertion, and deletion of the contained key-value pairs.

Efficiency

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.