DSA · Patterns, not puzzles
What is the time complexity of a hash table?
Short answer
Hash tables give average O(1) lookup, insertion and deletion. Worst case is O(n) when many keys collide into the same bucket, which is why a good hash function and resizing matter.
A hash table computes a hash from a key, maps it to a bucket, and stores the entry there. With a good hash and a bounded load factor, buckets hold few entries, so operations are constant time on average. Collisions are handled by chaining or open addressing.
function twoSum(values, target) {
const seen = new Map();
for (let i = 0; i < values.length; i++) {
const need = target - values[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(values[i], i);
}
return [];
}What affects performance
- A poor hash function sends many keys to the same bucket
- A high load factor increases collisions, so implementations resize
- Resizing is O(n) but happens rarely, giving amortized O(1) inserts
- Worst case is O(n) when every key collides
- Average O(1) assumes keys are distributed reasonably
In JavaScript, Map and Set use hash-based lookup. Object property access is also fast but has prototype and key-coercion caveats, so Map is usually clearer for interview code.
Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1What is the worst-case complexity of a hash table?
- 2How are collisions resolved?
- 3Why is insertion amortized O(1)?
- 4When would you choose a sorted array over a hash table?
Say it in the interview
A hash table hashes the key to a bucket, so average lookup, insert and delete are O(1), while the worst case is O(n) if every key collides. A good hash function and resizing keep the load factor low, which is why the average holds. In JavaScript I use Map or Set, and I always say average constant time rather than promising it unconditionally.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.