Maps And Their Applications

This morning I was hanging out with my Hackbright mentee, and we discussed how one of her programming problems could be solved using a Python dictionary or JavaScript object. In fact, you can use a dictionary in lots of ways. Here are some:

For the rest of this post I’ll use the term map to refer to what various languages/APIs/sources in the literature call dictionaries, hashes, “objects” (only? in a JavaScript context), associative arrays, symbol tables, or tables. A map is any data structure that groups a dynamic number of key-value pairs together, and allows us to retrieve values by key, to insert new key-value pairs, and to update the values associated with keys. We almost always require that the data structure allow us to do these operations very quickly. (After all, we’re going to be using them all the time to solve lots of problems!)

Most, but not all, languages come with some kind of map interface built-in. Notably, the C language does not (but C++ does).

You can implement a map in many ways. Here are some examples:

Note that although a general-purpose map is useful for many problems, it is not always ideal for a particular problem. For example, although you can use a map as a set, it’s a bit of a waste of space — it’s a set of key-value pairs, but you only need the key. Similarly, maybe you need not only to take the unique elements from a group of elements, but also to print them out in sorted order. If your dictionary type is implemented as a hash table, you’ll have to sort the keys (at an additional cost of O(n lg n) plus the memory allocation to store the keys in an array). By contrast, if your dictionary is implemented as a binary search tree, after you are done inserting all the elements, they’ll already be sorted. (The trade-off is that it might have cost more to insert the elements. When in doubt, test!)

Because one size does not fit all, many languages provide a variety of map and set implementations. For example, C++ has map, set, unordered_map, and unordered_set. The Java Map interface has many implementations. Other languages, like Python, Perl, Ruby, and JavaScript, provide just one map implementation — usually a hash table of some kind. Some, like Python, also provide a distinct set type or API, and you should use it when it fits your needs.

It’s a good exercise to implement a map yourself, in at least one way, in at least one language. I recommend starting with a simple hash table, and then working up to a good binary search tree like a red-black tree.