Essentially, a Dictionary connects pairs of values, called “Key-Value Pairs” such that, when given a key as a reference, the above operations are possible in the specified times. This is possible by the following (simplified) process:<\/p>\n
- \n
- A Hash function transforms the Key into an integer value (Hash-Key).<\/li>\n
- The Hash-Key serves as an index into an Array where Values are stored.<\/li>\n
- Searching is done by using the Hash-Key as an index into the underlying Array.<\/li>\n<\/ol>\n
In the illustration below, we can see a string value
Hello, Hash Map<\/code> being transformed by the hash function, into an integer value (hexadecimal in this case) which then serves as the index into the underlying Array data structure into which values are stored.<\/p>\n![\"hash](\"https:\/\/www.alpharithms.com\/wp-content\/uploads\/3556\/hash-mapping.jpg\" "\\"hash-mapping\\"")
Figure 1:<\/strong> Hash Maps use hashing functions to get an index value used to store\/access data into an underlying array.<\/figcaption><\/figure>\n Hash Maps like the one illustrated here allow object access like one was indexing into an array rather than searching<\/em> for an object in a list. The same goes for insertions and deletions: there is no searching for an item, or array sorting, or tree re-balancing for the average case. The hash function essentially provides a way to determine the index.<\/p>\n
There are a\u00a0lot<\/em> more details to understand about hash mappings than what we just described. However, the concept of a Key being\u00a0mapped<\/em> to a Value is enough for our conversation here. For a more complete discussion of Hash Maps, including concerns such as the underlying implementation details, handling collisions, and applications, check out this video by Gayle Laakman<\/a> — author of the infamous Cracking the Coding Interview<\/em><\/a> book.<\/p>\n
Default Dicts: Sprinkling on Some Syntactic Sugar<\/h2>\n
Python’s DefaultDict class is part of the broader Collections framework. This module provides extended versions of standard data structures to help provide simpler workflows for common use cases. The DefaultDict is designed such that one doesn’t need to check if a value exists before altering it<\/strong>. Let’s see an example of when that might be useful.<\/p>\n
Let’s say we have a list of orders placed at the deli. The deli offers several different types of meats and customers can order different sizes or each. At the end of the day, the deli manager would like to know several essential things:<\/p>\n
- \n
- How many total orders?<\/li>\n
- Average Order Size.<\/li>\n
- Total amount of each product sold.<\/li>\n<\/ol>\n
If we used a list, we might have to iterate over every item for each unique product. However, a hash mapping would help isolate just the products we wanted like this:<\/p>\n
![\"order](\"https:\/\/www.alpharithms.com\/wp-content\/uploads\/3556\/order-mapping-alpharithms.jpg\" "\\"order-mapping-alpharithms\\"")
Figure 2:<\/strong> The order data is structured into a Mapping of Order types and lists of order amounts.<\/figcaption><\/figure>\n This transformation creates a Hash Mapping (Dictionary) of the orders and their amounts such that, for any single order type, the amounts are easily accessed as
Mapping[order_type]<\/code> such that the search, insert, and delete operations are possible in constant time for the average case. This\u00a0could<\/em> be implemented in vanilla Python using the standarddict<\/code> data structure as follows:<\/p>\n# list of deli orders\r\norders = [\r\n (\"fish\", 1),\r\n (\"beef\", 2),\r\n (\"chicken\", 1),\r\n (\"fish\", 5),\r\n (\"beef\", 4),\r\n (\"beef\", 2),\r\n (\"chicken\", 7)\r\n]\r\n\r\n# create a dictionary object\r\nmapping = {}\r\n\r\n# loop through all orders\r\nfor item, amount in orders:\r\n \r\n # add to existing list\r\n if item in mapping:\r\n mapping[item].append(amount)\r\n \r\n # start a new list\r\n else:\r\n mapping[item] = [amount]<\/pre>\nThis works fine — there’s no doubt about it. However, for those of us who use Python
dict<\/code> objects often, this syntax becomes cumbersome quickly. Python’s DefaultDict can help achieve the same end result without the conditional statements as such:<\/p>\nfrom collections import defaultdict\r\n\r\n# list of deli orders\r\norders = [\r\n (\"fish\", 1),\r\n (\"beef\", 2),\r\n (\"chicken\", 1),\r\n (\"fish\", 5),\r\n (\"beef\", 4),\r\n (\"beef\", 2),\r\n (\"chicken\", 7)\r\n]\r\n\r\n# create a dictionary object\r\nmapping = defaultdict(list)\r\n\r\n# loop through all orders\r\nfor item, amount in orders:\r\n\r\n # default dict magic\r\n mapping[item].append(amount)<\/pre>\n
Here we see the line
mapping[item].append(amount)<\/code> without any conditional statements to handle the case where that item might not already be in thedict<\/code> object. Normally, this would raise anKeyError<\/code> exception. However, Python’s DefaultDict will do the equivalent\u00a0 conditional check for us and, in the case where there isn’t a key, will create a new key entry that maps to the data type provided in the instantiation statement — alist<\/code> in this case.<\/p>\nFinal Thoughts<\/h2>\n
The DefaultDict class in Python exemplifies how the language cuts down on development time. Its easy yet powerful interface provides a simple, no-nonsense extension of the basic
dict<\/code> class to help optimize and reduce the syntactic burden of common use cases. Is it entirely necessary for the example here? No. A very similar workflow could be achieved by using the following assignment statement:<\/p>\nmapping[item] = mapping.get(item, []) + [amount]<\/pre>\n
However, this would have to change slightly based on the data type, isn’t completely clear to the untrained eye, and leaves more room for potential errors. At the very least, it’s still more characters than the use of
defaultdict<\/code>.<\/p>\n","protected":false},"excerpt":{"rendered":"The DefaultDict class in Python operates much like the regular Dictionary class. However, it extends functionality to reduce the syntactic burden of several common dictionary-based operations. Namely, it allows for lighter syntax when adding potentially new key-value pairs to the dictionary object. Quick Intro: Dictionaries & Common Operations The Python Dictionary data structure is akin […]<\/p>\n","protected":false},"author":2,"featured_media":3559,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"categories":[186,655],"tags":[683],"acf":[],"_links":{"self":[{"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/posts\/3556"}],"collection":[{"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/comments?post=3556"}],"version-history":[{"count":1,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/posts\/3556\/revisions"}],"predecessor-version":[{"id":3560,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/posts\/3556\/revisions\/3560"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/media\/3559"}],"wp:attachment":[{"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/media?parent=3556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/categories?post=3556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.alpharithms.com\/wp-json\/wp\/v2\/tags?post=3556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}