Or a million?Traversing the list index by index to search for the person that you want might take a long, long time.
This would be a great use case for a dictionary like this:numbers_and_people = {5551212: "lily", 5551234: "john}Photo by Romain Vignes on UnsplashPython dictionaries are dynamic like lists.
They can be made dynamically bigger as you add more items.
But unlike lists they have a super speedy lookup time.
All you need to know to get the value (e.
g.
the person) is the key (e.
g.
the phone number).
We’ll talk more about why dictionaries are so fast and when you should use them in this article.
What’s a Python Dictionary?Image from http://www.
trytoprogram.
com/python-programming/python-dictionaryFirst, let’s dig into the docs to understand what a dictionary is.
When you look for dictionaries in Python’s documentation, you’ll find them listed alongside lists, sets and tuples under the data structures section.
The Python dictionary can also be called a “mapping” because you use it to map key-value pairs (like our phone numbers and people from the first example).
In other words, at every spot in a dictionary you have a value which is assigned to a key.
Keys are the way that you look up items in a dictionary.
They are required to be unique so that you find the correct value when you use them for lookup.
Values can be duplicated like in the above example since you don’t use them for lookup.
Photo by dylan nolte on UnsplashLet’s use a scenario to help us understand why lookup with dictionaries is fast.
Imagine that you are working in a large office building.
You know the names of the people who work there and you generally recognize each person when you see them, but you don’t know who works in which office.
If you’re looking for Josefina, you could start at the bottom floor and knock on every door until you find her.
In terms of Big O notation, this would be an O(n) operation with ‘n’ being the number of doors in the building.
Maybe you’ll get lucky and she’s in the very first office.
This would be a best case scenario with a Big O notation of O(1).
Maybe it’s the worst case O(n) situation and and she’s all the way at the end of the 10th floor.
Even though you have the key (her name) and you know the value that you want (Josefina, the person) you still need something else to speed up this process.
It would be great to have her office number!Then you could just take the elevator to the right floor and walk right up to her door.
The first door you try would be the right one and this would make this an O(1) scenario again.
The office number that speeds this up is our hash value.
We’ll talk more about that a little bit later.
How do Python dictionaries work behind the scenes?Photo by CMDR Shane on UnsplashDictionary keys have to be an object that can be assigned a hash value.
These are objects immutable ones like tuples or strings which cannot be changed after the fact.
Mutable objects like lists, sets and dictionaries cannot be assigned as a key because they can be changed without creating a copy of themselves.
If you could set a list as a key, there would be no way to guarantee that it is unique.
You could create the key as a unique list that isn’t like any other list….
and then go back and make it just like another list-key later.
If you were using these lists to find a specific value, now you don’t know which value you’ll end up with.
Now, if you use [1, 2, 3] as the key you could get back "a_value" or you could get "another_value".
This would be like having a bunch of Josefinas in the same office.
When you get the office number for one Josefina (key) you don’t know if you’ll get the right person (value).
This is why we require keys to be unique and immutable.
Immutable objects like integers, floats, strings, tuples and even frozen sets cannot be changed without copying the whole object and creating a new object ID.
This creates consistency in knowing that when you use that object as a lookup, you’ll get the same result every time.
For this reason, these objects can be used to create a consistent hash value and locate the key-value pair.
Photo by Markus Spiske on UnsplashNow I mentioned before that keys are “hashed.
” Python dictionaries are implemented as a hash table behind the scenes.
The dictionary uses each key’s hash function to change some of the key’s information into an integer known as a hash value.
The hash value tells you which bucket that key-value pair should be placed in.
This way every time you need to lookup or find that key-value pair, you know exactly which bucket to search.
That is how keys save you time when trying to lookup a value.
When should I use a dictionary?Dictionaries are useful for speedy lookup and for storing unique keys with their respective values.
So when might you run into a dictionary in a real codebase?.If you are creating a datastore or a database in vanilla Python, then a dictionary might be really useful.
In the above example, we’re creating a datastore of all the students in the classroom and their stuff.
Notice that the values are all lists here.
If we expanded our dictionary to the whole school, we could still look stuff up really fast.
We could also use dictionaries as values if the students needed to have more categories for their stuff.
How will you use dictionaries in your code?.What else would you like to understand about them?.Please let me know in the comments below!.