Data Structures
What Is a Hash Table?
Also called: Hash map, Dictionary
A hash table stores key-value pairs and uses a hash function to find any value by its key in constant time on average.
Definition
A hash table is a data structure that maps keys to values, such as a username to a profile. Python’s dict, JavaScript’s Map and Java’s HashMap are all hash tables.
Lookups, inserts and deletes take O(1) time on average, which makes it one of the most used structures in software.
How it works
A hash function turns the key into a number, which picks a slot (bucket) in an internal array. To read the value, the table hashes the key again and goes straight to that slot.
Two keys can land in the same slot, which is called a collision. Tables handle it by chaining the items in a list or by probing for the next free slot, and they resize when they get too full.