Python Dictionary Internals: Hashing, Collisions, O(1) Lookup and Hashable Keys

Explain how a Python dictionary stores and looks up values, and which objects are allowed to be dictionary keys. The questions came as a fast oral sequence in the fundamentals half of a technical screen for a junior quantitative developer role; each answer drew an immediate "why" follow-up, so the goal is precise mechanics rather than definitions.

limits = {"alpha": 100, "beta": 250}
limits["beta"] # how is this value found?
hash("beta") # what is hashed, and what is the result used for?
{[1, 2]: "x"} # what happens here, and why?

Clarifying Questions

• Should the answer describe CPython's implementation, or only the behavior the language guarantees?
• How deep should the collision discussion go: the general technique, or the exact probing scheme CPython uses?
• Do keys include instances of user-defined classes, or only built-in types?

Part 1 — How a dictionary stores and finds a value

Answer in order:

1. How does a dictionary store a key-value pair, and how does it find the value for a given key?
2. What does the hash function take as input, and what does the dictionary do with its output?
3. Can two different keys have the same hash?
4. How are hash collisions handled?
5. Why is dictionary lookup O(1) on average?

What This Part Should Cover

• The path from key to hash to table slot, and the equality check that confirms a match
• Why collisions cannot be avoided, and one concrete way to resolve them
• What keeps the average cost constant, and when the cost degrades

Part 2 — Which objects can be keys

1. Can a list be used as a dictionary key?
2. Why not?
3. Which objects can be keys?

What This Part Should Cover

• What happens when a list is used as a key, and the reason
• The rule that ties a key's hash to its equality
• Which built-in types qualify, including the tuple caveat, and how user-defined classes behave