What are hash functions, and how do hash tables use them?

In this article

1. Before you start
2. Why interviewers ask this
3. Hash functions from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview patterns learning path.

Why interviewers ask this

A hash table sits under a large share of coding-round solutions. The subarray sum equals k answer and the longest substring without repeating characters answer both lean on a hash map, so a candidate who says "I will use a map" is expected to know what that costs.

A weak answer says "a hash map is O(1)" and stops. A strong answer says why lookups are fast only when the hash function spreads keys well, what a collision is, and how the table still returns the right value when two keys share a bucket. A Staff-level answer adds the failure modes: keys that change after insertion, hash values that differ between program runs, and inputs chosen by an attacker to force collisions.

Hash functions from first principles

Hash table

A hash table is a data structure that stores key-value pairs in an array of buckets and uses a hash function to turn each key into the number of the bucket where its pair lives, so a lookup goes straight to one bucket instead of scanning every pair.

Collision

A collision is an event in which two different inputs get the same hash result. In a hash table the usual meaning is two different keys that land in the same bucket, which the table must handle without losing either pair.

In plain words

Picture a coat check. The clerk turns your name into a hook number by a fixed rule, hangs your coat there, and later uses the same rule to find it. The rule is the hash function, and the hooks are the table. Two names can map to one hook; that is a collision. The analogy breaks in one place: a real table cannot ask you for a ticket, so it must compare the stored key with the key you ask for.

In one precise sentence, a hash table computes hash(key), reduces it to a bucket number, and then checks the keys in that one bucket.

Step 1: A hash function turns a key into a fixed-size number

A hash function reads the whole key and produces one number from it. The number has a fixed size however long the key is. NIST Special Publication (SP) 800-107 Rev. 1 defines it as "a function that maps a bit string of arbitrary length to a fixed-length bit string" and uses "hash algorithm" and "hash function" interchangeably.

Take a toy rule: add up the character codes of the key. The codes of c, a and t are 99, 97 and 116, so the sum hash of cat is 312.¹ Input: the key. Output: one number. Real functions mix the characters far more thoroughly, but the shape is the same.

You now know what goes in and what comes out. The next step is the rule that makes the function usable as an index.

Step 2: Equal keys must hash equally, but equal hashes do not mean equal keys

The same key must give the same hash every time, or a stored pair could never be found again. That is the contract Python states for its hashable objects: as quoted from the Python glossary by Invent with Python, "Hashable objects which compare equal must have the same hash value." One result follows: 1, 1.0 and True are equal in Python, so they have the same hash and d[1.0] finds the entry stored under 1.

The reverse is not promised. Under the sum hash, cat and act are different strings with the same hash, 312.¹ So after a table finds a bucket, it must still compare keys with equality. Equal hash means "maybe the same key", never "the same key".

The contract also explains why a Python list cannot be a key. The glossary requires a hash value that never changes while the object lives, and a list can change.

Step 3: The hash number picks a bucket

A table has a fixed number of slots, called buckets, so the hash is reduced with modulo. With 8 buckets, the bucket of cat is 312 mod 8, which is 0, shared by cat, act and tac.¹ The keys dog and god sum to 314 and share bucket 2, and bee sums to 300 and goes to bucket 4.¹

Sharing is unavoidable. A hash function has unbounded inputs and fixed-size outputs, so by the pigeonhole principle (more items than boxes forces a shared box) some inputs must collide. A good function cannot remove collisions; it makes them rare and evenly spread. The sum hash is bad because every anagram collides.

Step 4: Collisions are resolved and the table grows

The usual fix is chaining: each bucket holds a short list of pairs. A lookup hashes the key, goes to its bucket and compares the keys there. Another design, open addressing, stores the pair in the next free slot after the collision.

Tables also grow. The load factor is the number of entries divided by the number of buckets. The Java HashMap documentation gives a default of 16 buckets and a load factor of 0.75, so the threshold is 12 entries, and a 13th entry pushes the count past it.¹ The same page calls 0.75 "a good tradeoff between time and space costs" and says higher values "increase the lookup cost".

1 · Key in2 · Hash value3 · Bucket4 · CollisionReplay

Step-by-step description

1. The key goes into the hash function.
2. Equal keys always give the same value.
3. Modulo turns the value into a bucket.
4. Different keys can share a bucket.

• The sum hash of cat is 312.
• 312 mod 8 is bucket 0, shared by cat, act and tac.

Worked example

Six keys go into 8 buckets. The first hash is the sum of character codes. The second is order-sensitive: it multiplies the running total by 31 before adding each character code (the multiplier is illustrative). For cat that gives 98262, and 98262 mod 8 is 6.¹

With the sum hash the longest chain holds 3 keys. With the order-sensitive hash the longest chain holds 2 keys.¹ The load factor of this toy table is 6 / 8, which is 0.75, so even a better function collides here.¹ Chance explains why: if six keys were placed uniformly at random in 8 buckets, the probability that at least two share a bucket is 0.9231.¹

The last row of the next table uses the Secure Hash Algorithm (SHA) family, whose 256-bit member is called SHA-256.

The Java rule behind the 134: the documentation says no rehash happens if the initial capacity exceeds the maximum number of entries divided by the load factor.¹ The SHA-256 size comes from the Federal Information Processing Standards (FIPS) publication FIPS 180-4, which says the final result is a 256-bit message digest; a digest is the fixed-size output of a hash function. At 4 bits per hex character that is 64 characters.¹

Text description of the diagram

• Under the sum hash the longest chain holds 3 keys.
• Under the order-sensitive hash the longest chain holds 2 keys.

Trade-offs and edge cases

Constant time is conditional. The Java documentation promises constant-time get and put only "assuming the hash function disperses the elements properly among the buckets". With a bad function, every key lands in one chain and lookup becomes a scan.

Attackers can pick inputs. The Python 3.3 documentation says hash randomization is on by default from that version, to protect against "carefully-chosen inputs" that force the worst case, O(n^2), when building a dict. String and bytes hashes stay constant within one process but differ between runs, and setting the environment variable PYTHONHASHSEED (the hash seed) to 0 turns the randomization off. Python Enhancement Proposal (PEP) PEP 456 later made SipHash the default string hash, noting that "only a proper cryptographic hash function prevents the extraction of secret randomization keys".

Cryptographic hashes are a different tool. NIST lists three expected properties: collision resistance, preimage resistance and second preimage resistance. The Secure Hash Standard specifies seven approved algorithms, including Secure Hash Algorithm 256.

Text description of the diagram

• A table hash picks a bucket and expects collisions.
• A cryptographic hash makes collisions infeasible to find.

A table hash picks a bucket and expects collisions. A cryptographic hash makes collisions infeasible to find. Neither is encryption: a hash has no key and no way back, and preimage resistance is the property that makes finding an input from a digest infeasible.

Other edge cases. Mutable keys break lookups, because a changed hash points to the wrong bucket. Java's documentation says the class makes no promise about the order of the map, so never print results in map order. Many dictionary helpers, such as defaultdict, rely on the same hashing rules.

How to answer it in an interview

The spoken structure: define the function, say how a bucket is chosen, name collisions and how they are handled, then state the condition on constant time.

Common mistakes

• "A good hash function never collides." (wrong) Collisions are unavoidable when inputs outnumber outputs. (right) "A good function makes collisions rare and even, and the table resolves them."
• "If two hashes are equal, the keys are equal." (wrong) Only equal keys must give equal hashes. (right) "Equal hashes send me to a bucket; I still compare the keys."
• "Python's hash() gives the same value every run." (wrong) For strings and bytes it is randomized per process. (right) "It is stable within a run, so never store it or rely on it across runs."
• "Hash table lookup is always O(1)." (wrong) It depends on dispersion. (right) "Average O(1) with a well-spread hash; worst case linear."
• "Hashing is encryption and can be reversed." (wrong) Hashes have no decryption. (right) "Hashing is one-way; encryption is reversible with a key."

Follow-up questions

What makes a good hash function?

It is deterministic, fast, and spreads keys evenly over the buckets so chains stay short. For security use, it must also resist finding collisions on purpose, which is the job of the cryptographic functions NIST approves.

What is a collision in a hash table, and how is it handled?

A collision is two different keys landing in the same bucket. Chaining keeps a short list per bucket; open addressing probes for the next free slot. Either way the table compares the actual keys.

Is hashing the same as encryption?

No. A hash maps input to a fixed-size digest and cannot be undone; encryption is reversible with a key. Secure Hash Algorithm 256 is a hash, with a 256-bit digest.

Why does Python's hash() change between runs?

Python randomizes str and bytes hashes per process to block denial-of-service attacks that build colliding keys. Within one run they are constant; see the Python interview questions for related dict behavior.

Why can't a list be a dictionary key in Python?

A key's hash must never change while the object lives, and a list can change, which would leave its pair in the wrong bucket. Tuples of immutable items and strings are hashable.

Is hash table lookup always O(1)?

No. It is constant time on average when the hash function disperses keys well. A poor function or crafted inputs can force long chains and O(n) lookups.

Sources

1. NIST SP 800-107 Rev. 1: Recommendation for Applications Using Approved Hash Algorithms — NIST, 1 Aug 2012
2. FIPS PUB 180-4: Secure Hash Standard — NIST, 1 Aug 2015
3. HashMap (Java SE 27 and JDK 27 documentation) — Oracle, 26 Oct 2026
4. Command line and environment (Python 3.3 documentation, PYTHONHASHSEED) — Python Software Foundation, 19 Sep 2017
5. PEP 456: Secure and interchangeable hash algorithm — Python Software Foundation, 27 Sep 2013
6. Hashable objects must be immutable (quotes the Python glossary) — Invent with Python (Al Sweigart), 26 Oct 2026