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. ```python 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? ```hint From key to slot Follow one lookup step by step: what number is computed from the key, how that number becomes a position in a table, and what still has to be checked once you reach that position. ``` #### 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? ```hint Change the key after storing it Suppose a key's contents change after it has been inserted. Where would the next lookup for it go, and what would it find there? ``` #### 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 ### What a Strong Answer Covers - A correct lookup sequence: hash, slot index, probing, equality comparison - Correct claims about collisions: they always exist, they cost extra probes, and they never return a wrong value - Average versus worst-case cost, with the reason for each - Hashability rules explained from how lookup works rather than recited as a list - Short, precise answers that hold up under rapid follow-ups ### Follow-up Questions - A class defines `__eq__` but not `__hash__`. What happens when its instances are used as keys, and why? - How many entries does `{1: "a", 1.0: "b", True: "c"}` contain, and what are their keys and values? - Can crafted input make dictionary lookups slow, and what does Python do about it? - Dictionaries have preserved insertion order since Python 3.7. How does a hash table do that without slowing lookups?