Hash Table

A hash table (also called a hash map) is a data structure that stores key-value pairs and finds the value for a key very quickly. A hash function turns each key into an index in an internal array, so looking up, inserting and deleting take O(1) time on average, no matter how many items are stored.

When two keys hash to the same index, it is called a collision; it is handled by keeping a small list at each index (chaining) or by trying another slot (open addressing). Hash tables are built into most languages as HashMap in Java, dict in Python, Map and objects in JavaScript and Dictionary in C#.