Original article was published on Artificial Intelligence on Medium
3. Value Retrieval — Dictionaries
sets as discussed above, another import built-in data type,
dict, requires its keys to be hashable.
The hashability of the keys implies that the data stored in a
dict involves the implementation of a hash table — which is the case. Like other mainstream languages (e.g., Java, Swift, Kotlin), Python operates dictionaries using hash tables under the hood. However, unlike sets, dictionaries store key-value pairs, and the requirement of hashable keys is the foundation to build the hash table.
With the hash mechanism, the time needed to retrieve a particular key-value pair is constant at a temporal complexity of
O(1) — using the Big-O notation. This
O(1) time complexity means that no matter how many elements the
dict has, the time to retrieve a particular item always stay at the same magnitude. We can see a quick comparison below:
Suppose we need to store the scores for a group of students. Using lists, we’ll have one list storing student ID numbers and the other for scores at the corresponding position. To find out a particular student’s score, I’ll first find out the index of the student and using the index to get the score. By contrast, using dictionaries, we’ll just store all these
student_id-score pairs with the student ID numbers as the keys. As shown above, between these two approaches, the dictionary outperforms the list approach more when the number of records is higher.
However, one thing to note is that because dictionaries store key-value pairs, your data model should have meaningful pieces of information to identify the values. In addition, the keys in a dictionary have to be unique, although the values can be the same.