Dictionary hashing
About this video
Dictionaries are stored in memory as a hash table: a list-like structure of slots where a hash function turns each key into a deterministic integer used as the slot index. The video traces a simplified length-based hash, uses modulo to fit hashes to the number of slots, and shows how collisions are handled.
You'll be able to
- explain how a hash function lets the computer find a key's slot in a dictionary.
- use modulo to turn a hash into a slot index for a table with a given number of slots.
- explain why dictionary keys must be immutable.
- describe what a collision is and one simple way to resolve it.
Key words
- hash function
- A function that turns a key into an integer, always giving the same integer for the same key.
- hash table
- A list-like structure of slots where each key-value pair is stored at the index given by hashing its key.
- deterministic
- Always producing the same output for the same input.
- modulo
- An operator (%) that gives the remainder of a division, used to scale a hash down to the number of slots.
- collision
- When two different keys hash to the same slot.
- immutable
- Cannot be changed after it is created, so its hash always stays the same.
Transcript
- [Instructor] How does the computer store a dictionary in memory? Here we have a dictionary where the keys are the names of files and the values are the sizes of those files in megabytes. With dictionaries, we know that we can look up a value using its key, but how does the computer represent that relationship?
In memory, the computer just stores the key value pairs in a list like structure. Each slot in the list is either empty or contains a matching key and value. For this to work, the computer just needs one thing, a deterministic way to know which key value pair is in which slot.
The solution is surprisingly simple. The computer uses a function that converts each key to a deterministic integer, and then it uses that integer as an index into the list. We call this a hash table, and the function a hash function. A hash function can be implemented using many different algorithms.
The important property is that for any given key, the function returns the same integer every time. This is why dictionary keys need to be immutable to guarantee that the keys hash is always the same. Now, Python of course, uses a sufficiently complex and well-studied algorithm for its hash function that works on any immutable data type.
But for now, let's assume something a bit simpler, so it's easier for us to trace. Let's say our simplified hash function that only works on strings just returns the length of the key. When we define a dictionary, the computer starts by allocating space and memory for that list.
Initially it allocates a small number of slots, let's say eight. Then it gets to work storing each item. For each item, it takes the key and passes it into the hash function. So for the key bot.py, we would get the hash six. So the computer finds a slot at index six, and then it stores both the key and the value here, and technically it also stores the hash.
And then we do the same thing for all of the other items. We hash the key to get the index, and then we store the key value pair in that slot. This might raise a few questions for you, like what if the hash is greater than the number of slots? The computer uses the modulo operator to scale the hash down to the number of slots.
The modulo operator remember takes the remainder of the division. So if we do 11 modulo eight, we get back three. So the flights CSV item goes in the slot at index three. Now that we have our dictionary defined, let's trace through a few accesses and updates. The right hand side of this assignment statement accesses the value associated with the key cat.jpg.
So the computer passes the key cat.jpg into the hash function, and then it takes modulo eight since there are eight slots, that gives us the index seven. So we go to slot seven, double check that the key matches, and since it does, we grab the value stored there, we substitute that back in, and then we store that float in a new variable called photo size.
This assignment statement reassigns the value associated with the key flights.csv. So again, we hash the key flights.csv, take modulo eight, which gives us three, go to the slot in index three and verify that the key matches. Since it does, the computer updates the item in the slot to have the value 5.3.
Now we add a new item to the dictionary, but do you see any problems with this key? Nda.pdf has the same hash as another one of our keys. We call this a collision. So what does the computer do? The algorithm for resolving collisions can vary. It just needs to be deterministic.
You could do something as simple as use the next empty slot. If we then access the key later, we would check in the original slot, see that that key doesn't match, and then search the subsequent slots until we find the one with our key. This of course is not the most efficient algorithm.
Python's actual collision handling algorithm is much more mathematically complex in order to minimize the number of slots we need to search. And unlike our simplified length algorithm, the actual Python hashing algorithm tries to minimize the number of collisions in the first place.
And on top of all that, if the list in memory starts to get somewhat full, the computer will allocate a new larger list and copy all of the items over, which gives it more space to spread out. Python makes a few other optimizations here and there, like it also stores some extra data to keep track of the order in which items were inserted.
But at its core, the magic of dictionaries comes from hashing. We have the power to look up a value using its key because we can hash the key to a deterministic index.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.