What Is a Hash Table?

A hash table (also called a hash map) is a data structure that stores key-value pairs and retrieves them very quickly. It uses a hash function to convert each key into an array index, so that finding, inserting, or deleting a value takes average O(1) time — effectively constant, regardless of how many entries the table holds.

How a Hash Table Works

Internally, a hash table is backed by an array of slots called buckets. When you store a key-value pair, the hash function turns the key into an integer, and that integer (reduced modulo the array size) picks the bucket where the value is placed. To look the value up later, the table hashes the same key again and jumps straight to that bucket — there is no scanning through every element, which is why lookups are so fast.

Handling Collisions

Because many possible keys map into a limited number of buckets, two different keys can land in the same bucket — a collision. There are two common strategies for resolving them:

• Chaining: each bucket holds a small list of entries, so colliding keys simply join the list.
• Open addressing: if a bucket is taken, the table probes for the next free slot (linear probing, quadratic probing, or double hashing).

Load Factor and Resizing

The load factor is the ratio of stored entries to buckets. As it climbs, collisions become more frequent and operations slow down. To stay fast, a hash table resizes once the load factor passes a threshold — allocating a larger array and rehashing every existing key into it. This resize is occasional and amortized, so average performance stays near O(1).

Time Complexity

Lookup, insertion, and deletion are all average O(1). The worst case is O(n), which happens when a poor hash function (or deliberately crafted keys) funnels many entries into the same bucket. In practice, a good hash function spreads keys evenly and keeps performance close to constant time.

Where Hash Tables Are Used

Hash tables are everywhere: they power dictionaries and sets, in-memory caches, symbol tables in compilers, and fast deduplication. They are so fundamental that every major language ships one built in — Python's dict, JavaScript's Map and plain objects, Java's HashMap, C++'s std::unordered_map, and Go's built-in map. When you need to look something up by an arbitrary key rather than a numeric position, a hash table is usually the right tool.

A hash table is one of the core data structures — compare it with a linked list (which often forms its collision chains) and a stack, see how binary search achieves fast lookups on sorted data, and how a database index applies the same idea on disk.

Frequently Asked Questions