Hash Table

In Turkish: Hash Tablosu

Updated September 30, 20263 min read

In short

A hash table is a data structure that stores key-value pairs and uses a hash function to find the value for any key in constant time on average.

What is a hash table?

A hash table stores data as key-value pairs, such as a username mapped to a user profile. Internally it keeps an array of slots, often called buckets. When you insert a pair, a hash function turns the key into a number, and that number, taken modulo the array size (the remainder after dividing by it), decides which bucket the pair goes into.

To look up a key later, the table hashes it again and jumps straight to the right bucket instead of scanning every entry, so lookups, inserts, and deletes take O(1) time on average. Sometimes two different keys land in the same bucket, which is called a collision. Tables handle collisions by keeping a small list per bucket (chaining) or by probing for the next free slot (open addressing), and they grow and rehash all entries when they get too full so that buckets stay short. In the rare worst case, when many keys collide, a single operation can degrade to O(n).

A library is a good analogy: instead of checking every shelf, you use a book's call number to walk directly to the right spot. Hash tables are among the most widely used data structures, and Python's dict and set and JavaScript's Map and Set are built on them. They power caches, counting and deduplication, hash indexes in databases, and the symbol tables compilers use to track variable names.

A hash table is not the same as hashing for security. A hash table needs a hash function that is fast and spreads keys evenly, while password storage needs a deliberately slow cryptographic hash that is hard to reverse. Hash tables are also compared with balanced search trees: a hash table is faster for exact-key lookups, but it does not keep keys in sorted order, so a tree is the better choice for range queries such as finding all names between A and F.

At a glance

The hash picks the bucket directly, so a lookup skips every other entry. Keys that collide share a bucket's chain.

Key takeaways

A hash table maps keys to values using a hash function.
Lookup, insert, and delete are O(1) on average and O(n) in the worst case.
A collision happens when two keys map to the same bucket; chaining and open addressing resolve it.
Python's dict and JavaScript's Map are hash tables.
Hash tables don't keep keys in sorted order, so they are a poor fit for range queries.

Example

Counting words with a Python dictpython

# A dict is Python's built-in hash table
text = "the cat sat on the mat by the door"
counts = {}

for word in text.split():
    counts[word] = counts.get(word, 0) + 1  # lookup and insert: O(1) on average

print(counts["the"])    # 3
print("dog" in counts)  # False: membership checks are also O(1) on average

Readers ask

What is the difference between a hash table and a hash map?

In most contexts they mean the same thing: a key-value structure built on hashing. Some languages use the names for specific classes, such as Java's Hashtable and HashMap, which differ in details like thread safety.

Why is a hash table lookup O(1)?

The hash function computes where a key belongs directly, so the table can jump to that bucket instead of searching through every entry. This stays O(1) on average as long as the hash function spreads keys evenly and the table grows before it gets too full.

Can any value be used as a hash table key?

Keys must be hashable and must not change while stored, because a changed key would hash to a different bucket and could no longer be found. That is why Python accepts strings, numbers, and tuples of hashable values as dict keys, but not lists.