SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-hash-table-average-o1

On average, how long does looking up a key in a hash table (like a Python dict) take?

O(1) on average, assuming the hash function keeps collisions uncommon.

Start playing free

  1. O(log n)
  2. O(n)
  3. O(1) ✔

Why: A hash function turns the key straight into a slot number, so the table jumps right to where the item should be instead of searching. Bad luck with many collisions can make the worst case O(n).

Huh, didn't know that: Python's own complexity notes list dict get item as O(1) average but O(n) amortized worst case.

The dad joke
A hash table never searches for its keys. It just knows where it put them, unlike me.
Like this card?
Play the game

References

Answer: O(1). A hash function turns the key straight into a slot number, so the table jumps right to where the item should be instead of searching. Bad luck with many collisions can make the worst case O(n).

  1. Python Wiki: TimeComplexity wiki.python.org/moin/TimeComplexity
    Get Item O(1) O(n)
    Checked 2026-10-11.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsWhy is inserting at the front of a Python list slow when appending at the end is fast?Tech & GadgetsWhy does Python report 0.1 + 0.2 == 0.3 as false?Tech & GadgetsWhen small rounding errors are acceptable, how should two floating point results be compared?

That's stuff everyone should know.